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

1、-作者xxxx-日期xxxx(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))二叉樹【精品文檔】甘肅政法學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 二叉樹遍歷計(jì)算機(jī)科學(xué) 學(xué)院 信息管理與信息系統(tǒng) 專業(yè) 09 級信息管理與信息系統(tǒng) 班學(xué) 號：_200981020116姓 名：_唐占紅_指導(dǎo)教師：_金 濤_成 績：_完成時(shí)間：_2010 年 12 月摘 要二叉樹是樹形結(jié)構(gòu)的一個(gè)重要的類型，二叉樹是n（n=0）個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者由個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。二叉樹的存儲(chǔ)結(jié)構(gòu)和算法比較簡單，特別適合計(jì)算機(jī)處理。即使一般形式的樹也可簡單的轉(zhuǎn)換為二叉樹。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是把二叉

2、樹的所有結(jié)點(diǎn)，按照一定的次序順序，存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。遍歷二叉樹就是沿某有前序遍歷、中條搜索路徑周游二叉樹，對樹中每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。在遍歷方案中主要序遍歷、后序遍歷。 現(xiàn)實(shí)中有許多應(yīng)用到二叉樹的例子，所以我們要把理論與現(xiàn)實(shí)結(jié)合起來。在學(xué)習(xí)中主要掌握怎么求二叉樹的高度、葉子結(jié)點(diǎn)個(gè)數(shù)、總結(jié)點(diǎn)個(gè)數(shù)以及熟練三種遍歷的方法。關(guān)鍵詞 二叉樹 遍歷 深度目 錄第一章 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目及解析3&1.1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目3 設(shè)計(jì)題目解析3第二章 程序設(shè)計(jì)的目的和基本要求3&2.1 程序設(shè)計(jì)的目的3&2.2 程序設(shè)計(jì)的基本要求3第三章 程序設(shè)計(jì)的內(nèi)容3算法設(shè)計(jì)的思想3&3.3.程序數(shù)據(jù)

3、類型4程序模塊分析5主要的算法源代碼8程序設(shè)計(jì)的結(jié)果14第四章 程序設(shè)計(jì)的優(yōu)缺點(diǎn)及遇到問題14程序設(shè)計(jì)的優(yōu)缺點(diǎn)14程序設(shè)計(jì)遇到的問題14第五章 程序設(shè)計(jì)的總結(jié)15心的總結(jié)15第六章 參考文獻(xiàn)15 第一章 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目及解析&1.1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目題目：二叉樹的建立&1.2 設(shè)計(jì)題目解析通過這個(gè)程序主要掌握三種遍歷方案，包括前序遍歷、中序遍歷、后序遍歷，以及怎么求二叉樹的高度、總結(jié)點(diǎn)數(shù)、葉子總個(gè)數(shù)。并會(huì)將理論與現(xiàn)實(shí)結(jié)合在一起。第二章 程序設(shè)計(jì)的目的和基本要求&2.1 程序設(shè)計(jì)的目的掌握二叉樹的概念和性質(zhì)、任意二叉樹存儲(chǔ)結(jié)構(gòu)和任意二叉樹的基本操作，并會(huì)求二叉樹的高度、二叉樹總結(jié)點(diǎn)個(gè)數(shù)

4、、二叉樹葉子結(jié)點(diǎn)，以及熟練掌握三種遍歷，包括前序遍歷、中序遍歷、后序遍歷。&2.2 程序設(shè)計(jì)的基本要求在設(shè)計(jì)程序時(shí)，一定要簡單明了，程序設(shè)計(jì)的思想要完善，算法要清晰，能給其他讀者一目了然的感覺。實(shí)現(xiàn)二叉樹的建立；前序、中序和后序遍歷；高度、總結(jié)點(diǎn)數(shù)、葉子結(jié)點(diǎn)數(shù)。第三章 程序設(shè)計(jì)的內(nèi)容二叉樹的建立基本思想是：依次輸入的結(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í)為止。可設(shè)置一個(gè)指針類型的數(shù)組隊(duì)列，保存已輸入結(jié)點(diǎn)的地址。由于是按層次自左至右輸入結(jié)點(diǎn)的，所以先輸入的結(jié)點(diǎn)的孩子必定比

5、后輸入結(jié)點(diǎn)的孩子先進(jìn)入隊(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)編號是偶數(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)，則無須鏈接。若雙親結(jié)點(diǎn)與其兩個(gè)孩子鏈接完畢，則做出隊(duì)操作，使隊(duì)頭指針指向下一個(gè)等待鏈接的雙親結(jié)點(diǎn)。遍歷二叉樹是二叉樹的一種重要的運(yùn)算，所謂遍歷是指沿某條搜索路徑周游二叉樹，對數(shù)中每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。二叉樹的定義是遞歸的，所以主要由三種遍歷方案：

6、1. 前序遍歷二叉樹若二叉樹非空，則依次進(jìn)行如下操作：（1） 訪問根結(jié)點(diǎn)；（2） 前序遍歷左子數(shù)；（3） 前序遍歷右子樹。2. 中序遍歷二叉樹若二叉樹非空，則依次進(jìn)行如下操作：（1） 中序遍歷左子樹；（2） 訪問根結(jié)點(diǎn)；（3） 中序遍歷右子樹。3. 后序遍歷二叉樹若二叉樹非空，則依次進(jìn)行如下操作：（1） 后序遍歷左子樹；（2） 后序遍歷右子樹；（3） 訪問根結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為該結(jié)點(diǎn)的度。一顆樹的度是該樹中結(jié)點(diǎn)的最大度數(shù)。度為零的結(jié)點(diǎn)稱為葉子，二叉樹結(jié)點(diǎn)的層數(shù)是從根開始算起的，樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度或深度。typedef int datatype; /* datatype可以為

7、任何類型，這里假設(shè)為int*/# define max 60 /*二叉樹可能的最大長度，這里假設(shè)為60*/typedef struct node /*結(jié)構(gòu)體*/char data; /*數(shù)據(jù)域*/struct node *lchild,*rchild; /*左右孩子指針*/bitree;（1） 二叉樹的建立 bitree *creat() /*二叉樹的建立*/int i,j;bitree *root,*s,*Qmax; char ch; printf(請輸入要建立的樹的下標(biāo)和數(shù)值：);scanf(%d%c,&i,&ch);while(i!=0&ch!=0)s=(bitree *)malloc(

8、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）二叉樹的三種遍歷void preorder(bitree *t) /*前序遍歷*/if(t)printf(%c,t-data);preorder(t-lchild);preorder(t-rchild);void inorder(bitree *t) /*中序遍歷*/if(t)inord

9、er(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）求二叉樹的高度 int high(bitree *t) /*求二叉樹的高度*/int l,r;if(t=NULL) return 0;elsel=high(t-lchild);r=high(t-rchild);return (lr?l:r)+1;（4）求二叉樹的總結(jié)點(diǎn)數(shù)int nodes(bitree

10、 *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(),功能是給出測試數(shù)

11、據(jù)值，建立測試數(shù)據(jù)值的順序表，調(diào)用creat函數(shù)、preorder函數(shù)、inorder函數(shù)、postorder函數(shù)high、函數(shù)nodes函數(shù)、leafs函數(shù)實(shí)現(xiàn)問題要求。# includestdio.h /*頭文件*/# includetypedef int datatype;# define max 60typedef struct node /*結(jié)構(gòu)體*/char data;struct node *lchild,*rchild;bitree;bitree *creat() /*二叉樹的建立*/int i,j;bitree *root,*s,*Qmax; char ch; printf(

12、 請輸入要建立的樹的下標(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)

13、;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) /*求二叉樹的高度*/int l,r;if(t=NULL) return 0;elsel=high(t-lchild);r=high(t-rch

14、ild);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);ret

15、urn 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( 該二叉樹的前序遍歷是：); preorder(b); printf(n); break;case 2:printf( 該二叉樹的中序遍歷是：); inorder(b); printf(n); break;case 3:printf(

16、該二叉樹的后序遍歷是：); postorder(b); printf(n); break;case 4:printf( 該二叉樹的高度j=%dn,j);j=high(b); break;case 5:h=nodes(b); printf( 該二叉樹的總結(jié)點(diǎn)數(shù)h=%dn,h); break; case 0:exit(0);第四章 程序設(shè)計(jì)的優(yōu)缺點(diǎn)及遇到問題這個(gè)程序設(shè)計(jì)的算法清晰，思想明了，能清楚的實(shí)現(xiàn)二叉樹的建立、三種遍歷、高度、總結(jié)點(diǎn)數(shù)以及葉子結(jié)點(diǎn)數(shù)的運(yùn)算。但是這個(gè)程序在設(shè)計(jì)過程時(shí)有些麻煩，而且三種遍歷的算法自己不是太清楚，不能很清楚的描述三種遍歷。在設(shè)計(jì)時(shí)主要三種遍歷不是很清楚，所以還是很模糊，剛開始不能很準(zhǔn)確的把三種遍歷的算法寫出來，所以在這個(gè)問題上還要繼續(xù)思考。在寫菜單時(shí)不是很了解，后來在同學(xué)的幫助下把程序的菜單寫出來了，自己還要努力學(xué)習(xí)寫菜單。第五章 程序設(shè)計(jì)的總結(jié) 通過這次做數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我發(fā)現(xiàn)真正掌握一個(gè)知識點(diǎn)并不只是要從書上看，還要查一些相關(guān)資料，并且理論與現(xiàn)實(shí)結(jié)合在一起。這次做的是關(guān)于二叉樹的課程設(shè)計(jì)，剛開始以為并不是很難，但真正