(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))二叉樹(shù).doc

甘肅政法學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 二叉樹(shù)遍歷計(jì)算機(jī)科學(xué) 學(xué)院 信息管理與信息系統(tǒng) 專(zhuān)業(yè) 09 級(jí)信息管理與信息系統(tǒng) 班學(xué) 號(hào)：_200981020116姓 名：_唐占紅_指導(dǎo)教師：_金 濤_成 績(jī)：_完成時(shí)間：_2010 年 12 月摘 要二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一個(gè)重要的類(lèi)型，二叉樹(shù)是n（n=0）個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者由個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱(chēng)作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和算法比較簡(jiǎn)單，特別適合計(jì)算機(jī)處理。即使一般形式的樹(shù)也可簡(jiǎn)單的轉(zhuǎn)換為二叉樹(shù)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是把二叉樹(shù)的所有結(jié)點(diǎn)，按照一定的次序順序，存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。遍歷二叉樹(shù)就是沿某有前序遍歷、中條搜索路徑周游二叉樹(shù)，對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。在遍歷方案中主要序遍歷、后序遍歷。 現(xiàn)實(shí)中有許多應(yīng)用到二叉樹(shù)的例子，所以我們要把理論與現(xiàn)實(shí)結(jié)合起來(lái)。在學(xué)習(xí)中主要掌握怎么求二叉樹(shù)的高度、葉子結(jié)點(diǎn)個(gè)數(shù)、總結(jié)點(diǎn)個(gè)數(shù)以及熟練三種遍歷的方法。關(guān)鍵詞 二叉樹(shù) 遍歷 深度目 錄第一章 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目及解析3&1.1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目3&1.2 設(shè)計(jì)題目解析3第二章 程序設(shè)計(jì)的目的和基本要求3&2.1 程序設(shè)計(jì)的目的3&2.2 程序設(shè)計(jì)的基本要求3第三章 程序設(shè)計(jì)的內(nèi)容3&3.1算法設(shè)計(jì)的思想3&3.3.程序數(shù)據(jù)類(lèi)型4&3.4程序模塊分析5&3.3主要的算法源代碼8&3.4程序設(shè)計(jì)的結(jié)果14第四章 程序設(shè)計(jì)的優(yōu)缺點(diǎn)及遇到問(wèn)題14&4.1程序設(shè)計(jì)的優(yōu)缺點(diǎn)14&4.2程序設(shè)計(jì)遇到的問(wèn)題14第五章 程序設(shè)計(jì)的總結(jié)15&5.1心的總結(jié)15第六章 參考文獻(xiàn)15 第一章 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目及解析&1.1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目題目：二叉樹(shù)的建立&1.2 設(shè)計(jì)題目解析通過(guò)這個(gè)程序主要掌握三種遍歷方案，包括前序遍歷、中序遍歷、后序遍歷，以及怎么求二叉樹(shù)的高度、總結(jié)點(diǎn)數(shù)、葉子總個(gè)數(shù)。并會(huì)將理論與現(xiàn)實(shí)結(jié)合在一起。第二章 程序設(shè)計(jì)的目的和基本要求&2.1 程序設(shè)計(jì)的目的掌握二叉樹(shù)的概念和性質(zhì)、任意二叉樹(shù)存儲(chǔ)結(jié)構(gòu)和任意二叉樹(shù)的基本操作，并會(huì)求二叉樹(shù)的高度、二叉樹(shù)總結(jié)點(diǎn)個(gè)數(shù)、二叉樹(shù)葉子結(jié)點(diǎn)，以及熟練掌握三種遍歷，包括前序遍歷、中序遍歷、后序遍歷。&2.2 程序設(shè)計(jì)的基本要求在設(shè)計(jì)程序時(shí)，一定要簡(jiǎn)單明了，程序設(shè)計(jì)的思想要完善，算法要清晰，能給其他讀者一目了然的感覺(jué)。實(shí)現(xiàn)二叉樹(shù)的建立；前序、中序和后序遍歷；高度、總結(jié)點(diǎn)數(shù)、葉子結(jié)點(diǎn)數(shù)。第三章 程序設(shè)計(jì)的內(nèi)容&3.1算法設(shè)計(jì)的思想二叉樹(shù)的建立基本思想是：依次輸入的結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)。若新結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)；否則將新結(jié)點(diǎn)作為孩子鏈接到它的雙親結(jié)點(diǎn)上。如此重復(fù)下去，直至輸入“00”時(shí)為止?？稍O(shè)置一個(gè)指針類(lèi)型的數(shù)組隊(duì)列，保存已輸入結(jié)點(diǎn)的地址。由于是按層次自左至右輸入結(jié)點(diǎn)的，所以先輸入的結(jié)點(diǎn)的孩子必定比后輸入結(jié)點(diǎn)的孩子先進(jìn)入隊(duì)列，因此可利用對(duì)頭指針指向當(dāng)前必須與其孩子結(jié)點(diǎn)必定建立鏈接的雙親結(jié)點(diǎn)，利用隊(duì)尾指針指向當(dāng)前的結(jié)點(diǎn)，即是當(dāng)前必須與其雙親建立鏈接的雙親結(jié)點(diǎn)。若隊(duì)尾指針為偶數(shù)，則表示當(dāng)前輸入的結(jié)點(diǎn)編號(hào)是偶數(shù)，隊(duì)尾指針?biāo)赶虻慕Y(jié)點(diǎn)應(yīng)作為左孩子與其雙親鏈接；否則隊(duì)尾指針?biāo)傅慕Y(jié)點(diǎn)應(yīng)作為右孩子與其雙親鏈接。若雙親結(jié)點(diǎn)或孩子結(jié)點(diǎn)或孩子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無(wú)須鏈接。若雙親結(jié)點(diǎn)與其兩個(gè)孩子鏈接完畢，則做出隊(duì)操作，使隊(duì)頭指針指向下一個(gè)等待鏈接的雙親結(jié)點(diǎn)。遍歷二叉樹(shù)是二叉樹(shù)的一種重要的運(yùn)算，所謂遍歷是指沿某條搜索路徑周游二叉樹(shù)，對(duì)數(shù)中每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。二叉樹(shù)的定義是遞歸的，所以主要由三種遍歷方案：1. 前序遍歷二叉樹(shù)若二叉樹(shù)非空，則依次進(jìn)行如下操作：（1） 訪問(wèn)根結(jié)點(diǎn)；（2） 前序遍歷左子數(shù)；（3） 前序遍歷右子樹(shù)。2. 中序遍歷二叉樹(shù)若二叉樹(shù)非空，則依次進(jìn)行如下操作：（1） 中序遍歷左子樹(shù)；（2） 訪問(wèn)根結(jié)點(diǎn)；（3） 中序遍歷右子樹(shù)。3. 后序遍歷二叉樹(shù)若二叉樹(shù)非空，則依次進(jìn)行如下操作：（1） 后序遍歷左子樹(shù)；（2） 后序遍歷右子樹(shù)；（3） 訪問(wèn)根結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。一顆樹(shù)的度是該樹(shù)中結(jié)點(diǎn)的最大度數(shù)。度為零的結(jié)點(diǎn)稱(chēng)為葉子，二叉樹(shù)結(jié)點(diǎn)的層數(shù)是從根開(kāi)始算起的，樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的高度或深度。&3.3.程序數(shù)據(jù)類(lèi)型typedef int datatype; /* datatype可以為任何類(lèi)型，這里假設(shè)為int*/# define max 60 /*二叉樹(shù)可能的最大長(zhǎng)度，這里假設(shè)為60*/typedef struct node /*結(jié)構(gòu)體*/char data; /*數(shù)據(jù)域*/struct node *lchild,*rchild; /*左右孩子指針*/bitree;&3.4程序模塊分析（1） 二叉樹(shù)的建立 bitree *creat() /*二叉樹(shù)的建立*/int i,j;bitree *root,*s,*Qmax; char ch; printf(請(qǐng)輸入要建立的樹(shù)的下標(biāo)和數(shù)值：);scanf(%d%c,&i,&ch);while(i!=0&ch!=0)s=(bitree *)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL;s-rchild=NULL;Qi=s;if(i=1) root=s;elsej=i/2;if(i%2=0) Qj-lchild=s;else Qj-rchild=s;scanf(%d%c,&i,&ch);return root;（2）二叉樹(shù)的三種遍歷void preorder(bitree *t) /*前序遍歷*/if(t)printf(%c,t-data);preorder(t-lchild);preorder(t-rchild);void inorder(bitree *t) /*中序遍歷*/if(t)inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);void postorder(bitree *t) /*后序遍歷*/if(t)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);（3）求二叉樹(shù)的高度 int high(bitree *t) /*求二叉樹(shù)的高度*/int l,r;if(t=NULL) return 0;elsel=high(t-lchild);r=high(t-rchild);return (lr?l:r)+1;（4）求二叉樹(shù)的總結(jié)點(diǎn)數(shù)int nodes(bitree *a) /*求總結(jié)點(diǎn)數(shù)*/int num1,num2;if(a=NULL) return 0;elsenum1=nodes(a-lchild);num2=nodes(a-rchild);return num1+num2+1;（5）求葉子結(jié)點(diǎn)數(shù)int leafs(bitree *b) /*求葉子結(jié)點(diǎn)數(shù)*/int n,m;if(b=NULL) return 0;else if(b-lchild=NULL&b-rchild=NULL) return 1;elsen=leafs(b-lchild);m=leafs(b-rchild);return n+m;（6）主函數(shù) main(),功能是給出測(cè)試數(shù)據(jù)值，建立測(cè)試數(shù)據(jù)值的順序表，調(diào)用creat函數(shù)、preorder函數(shù)、inorder函數(shù)、postorder函數(shù)high、函數(shù)nodes函數(shù)、leafs函數(shù)實(shí)現(xiàn)問(wèn)題要求。&3.3主要的算法源代碼# includestdio.h /*頭文件*/# includetypedef int datatype;# define max 60typedef struct node /*結(jié)構(gòu)體*/char data;struct node *lchild,*rchild;bitree;bitree *creat() /*二叉樹(shù)的建立*/int i,j;bitree *root,*s,*Qmax; char ch; printf( 請(qǐng)輸入要建立的樹(shù)的下標(biāo)和數(shù)值：);scanf(%d%c,&i,&ch);while(i!=0&ch!=0)s=(bitree *)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL;s-rchild=NULL;Qi=s;if(i=1) root=s;elsej=i/2;if(i%2=0) Qj-lchild=s;else Qj-rchild=s;scanf(%d%c,&i,&ch);return root;void preorder(bitree *t) /*前序遍歷*/if(t)printf(%c,t-data);preorder(t-lchild);preorder(t-rchild);void inorder(bitree *t) /*中序遍歷*/if(t)inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);void postorder(bitree *t) /*后序遍歷*/if(t)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);int high(bitree *t) /*求二叉樹(shù)的高度*/int l,r;if(t=NULL) return 0;elsel=high(t-lchild);r=high(t-rchild);return (lr?l:r)+1;int nodes(bitree *a) /*求總結(jié)點(diǎn)數(shù)*/int num1,num2;if(a=NULL) return 0;elsenum1=nodes(a-lchild);num2=nodes(a-rchild);return num1+num2+1;int leafs(bitree *b) /*求葉子結(jié)點(diǎn)數(shù)*/int n,m;if(b=NULL) return 0;else if(b-lchild=NULL&b-rchild=NULL) return 1;elsen=leafs(b-lchild);m=leafs(b-rchild);return n+m;void main()int a,j,h,g;bitree *b;b=creat();while(1)printf( 選擇 1 前序遍歷n 選擇 2 中序遍歷n選擇 3 后序遍歷n 選擇 4 求高度n 選擇 5 求總結(jié)點(diǎn)數(shù)n 選擇 6 求葉子結(jié)點(diǎn)個(gè)數(shù)n 選擇 0 退出: );scanf(%d,&a);switch(a)case 1:printf( 該二叉樹(shù)的前序遍歷是：); preorder(b); printf(n); break;case 2:printf( 該二叉樹(shù)的中序遍歷是：); inorder(b); printf(n); break;case 3:printf( 該二叉樹(shù)的后序遍歷是：); postorder(b); printf(n); break;case 4:printf( 該二叉樹(shù)的高度j=%dn,j);j=high(b); break;case 5:h=nodes(b); printf( 該二叉樹(shù)的總結(jié)點(diǎn)數(shù)h=%dn,h); break; case 0:exit(0);&3.4程序設(shè)計(jì)的結(jié)果第四章 程序設(shè)計(jì)的優(yōu)缺點(diǎn)及遇到問(wèn)題&4.1程序設(shè)計(jì)的優(yōu)缺點(diǎn)這個(gè)程序設(shè)計(jì)的算法清晰，思想明了，能清楚的實(shí)現(xiàn)二叉樹(shù)的建立、三種遍歷、高度、總結(jié)點(diǎn)數(shù)以及葉子結(jié)點(diǎn)數(shù)的運(yùn)算。但是這個(gè)程序在設(shè)計(jì)過(guò)程時(shí)有些麻煩，而且三種遍歷的算法自己不是太清楚，不能很清楚的描述三種遍歷。&4.2程序設(shè)計(jì)遇到的問(wèn)題在設(shè)計(jì)時(shí)主要三種遍歷不是很清楚，所以還是很模糊，剛開(kāi)始不能很準(zhǔn)確的把三種遍歷的算法寫(xiě)出來(lái)，所以在這個(gè)問(wèn)題上還要繼續(xù)思考。在寫(xiě)菜單時(shí)不是很了解，后來(lái)在同學(xué)的幫助下把程序的菜單寫(xiě)出來(lái)了，自己還要努力學(xué)習(xí)寫(xiě)菜單。第五章 程序設(shè)計(jì)的總結(jié)&5.1心的總結(jié) 通過(guò)這次做數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我發(fā)現(xiàn)真正掌握一個(gè)知識(shí)點(diǎn)并不只是要從書(shū)上看，還要查一些相關(guān)資料，并且理論與現(xiàn)實(shí)結(jié)合在一起。這次做的是關(guān)于二叉樹(shù)的課程設(shè)計(jì)，剛開(kāi)始以為并