二叉樹的建立與遍歷

1、實踐考核題第二題設計報告書學生姓名XXX學生學號09XXX所在地區(qū)XXX提交日期（年/月）2014/6實踐題目實現(xiàn)二叉樹的建立與遍歷需求分析（1）以二叉鏈表作為存儲結構，定義二叉樹類型 Bitree 定義二叉鏈表的存儲結構，可以更好地對二叉表的操作，在二叉鏈表中，data域用于存儲二叉樹節(jié)點中的數(shù)據(jù)信息；lchild是指向左孩子的指針（左指針）。類似的，rchild是指向右孩子的指針（右指針）。此外，每個二叉鏈表還必須有一個指向根節(jié)點的指針，該指針稱為根指針。與鏈表頭指針類似，根指針具有標識二叉鏈表的作用，對二叉鏈表的訪問只能從根指針開始。若果某個節(jié)點的右孩子或者左孩子不存在時，則相應指針數(shù)據(jù)

2、域為空（#）。由此可知葉節(jié)點的左右指針必為空（#）。（2）實現(xiàn)二叉樹的以下運算 建立 void CreateBiTree(BiTree *T) 輸入二叉樹的結點元素，建立二叉鏈表 建立void CreateBiTree(BiTree *T)函數(shù)可以往二叉鏈表中輸入數(shù)據(jù)和向左右指針的指向是否為#，只有建立了二叉鏈表才能通過調用先序遍歷、中序遍歷和后序遍歷的函數(shù)遍歷出二叉樹中的數(shù)據(jù)。 選擇一種遍歷方式（先序、中序、后序）遍歷這棵二叉樹 通過選擇遍歷方式，遍歷同一顆二叉樹，遍歷的次序是不同的，遍歷的方法也是不一樣的，通過不同的遍歷方式的得到二叉樹的順序是不一樣，但是都是為了得到二叉樹最后的排序。通過

3、先序遍歷，先訪問的是根節(jié)點，然后是左子樹，最后是右子樹。中序遍歷，先遍歷左子樹，在訪問根節(jié)點，最后遍歷右子樹。后序遍歷，先遍歷左子樹，在遍歷右子樹，左后訪問根節(jié)點。通過不同的排序方式可以確定一棵唯一的二叉樹。概要設計（1） 建立二叉鏈表： void CreateBiTree(BiTree *T) 首先，定義一個結構體，存儲每個節(jié)點的信息，并給這個結構體定義別名為Bittree；這個結構體中的數(shù)據(jù)元素有，保存數(shù)據(jù)的類型，還有指向左右孩子的指針它的類型和結構體的類型一樣。（2） 實現(xiàn)二叉樹的以下運算 選擇一種遍歷方式（先序、中序、后序）遍歷這棵二叉樹 先序遍歷：void PreOrder(BiTr

4、ee T)若被遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作： 訪問根節(jié)點； 先序遍歷左子樹； 先序遍歷右子樹。中序遍歷：void InOrder(BiTree T若被遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：中序遍歷左子樹；訪問根節(jié)點；中序遍歷右子樹。后序遍歷：void PostOrder(BiTree T)若被遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：后序遍歷左子樹；后序遍歷右子樹；訪問根節(jié)點。 上面給出的先序遍歷、中序遍歷和后序遍歷的定義都是遞歸的，因而根據(jù)定義很容易得到相應遍歷的遞歸算法。詳細設計#include#include#includetypede

5、f char TElemType;typedef struct SBiTNode TElemType data; struct SBiTNode *lchild,*rchild;BiTNode,*BiTree;/采用左序遍歷創(chuàng)建二叉樹，用到的是遞歸算法，參數(shù)指針T有點晦澀難懂。void CreateBiTree(BiTree *T) TElemType ch; scanf(%c,&ch); if(ch=#) *T=NULL; else *T=(BiTree)malloc( sizeof(BiTNode) ); if(!*T) exit(-1); (*T)-data=ch; CreateBiTr

6、ee(&(*T)-lchild); CreateBiTree(&(*T)-rchild); /輸出函數(shù)void Visit(BiTree T)if(T-data != #)printf(%c ,T-data);/先序遍歷void PreOrder(BiTree T)if(T != NULL)/訪問根節(jié)點Visit(T);/訪問左子結點PreOrder(T-lchild);/訪問右子結點PreOrder(T-rchild);/中序遍歷void InOrder(BiTree T) /判斷是否為空 if(T!=NULL) /中序訪問左子樹 InOrder(T-lchild); /訪問根節(jié)點 Visi

7、t(T); /中序訪問右子樹 InOrder(T-rchild); /后序遍歷void PostOrder(BiTree T) /判斷是否為空 if(T!=NULL) /后序訪問左子樹 PostOrder(T-lchild); /后序訪問右子樹 PostOrder(T-rchild); /訪問根節(jié)點 Visit(T); /主函數(shù) int main() BiTree T; printf(清數(shù)據(jù)數(shù)據(jù)（#代表空數(shù)據(jù)位，結束前不要使用回車鍵）：n); CreateBiTree(&T); /創(chuàng)建二叉樹 if(T!=NULL) printf(前序遍歷n); PreOrder(T); /先序遍歷 print

8、f(n); printf(中序遍歷n); InOrder(T); /中序遍歷 printf(n); printf(后序遍歷n); PostOrder(T); /后序遍歷 printf(n); elseprintf(二叉樹為空！);getch(); return 0;調試分析輸入數(shù)據(jù)6253檢查程序執(zhí)行是否正確：輸入數(shù)據(jù)為空時，檢查程序的執(zhí)行：設計總結在二叉樹上無論采用哪種遍歷方法，都能夠訪問遍樹中的所有結點。由于訪問結點的順序不同，前序遍歷和中序遍歷都很難達到設計的要求（求路徑）；但采用后序遍歷二叉樹是可行的，因為后序遍歷是最后訪問根結點，按這個順序將訪問過的結點存儲到一個順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹T，