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