二叉樹遍歷課程設(shè)計

.數(shù)據(jù)結(jié)構(gòu)程序設(shè)計報告學(xué)院：班級：學(xué)號： 姓名：實驗名稱：二叉樹的建立與遍歷一、 實驗?zāi)康模?.掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)；2.掌握二叉樹創(chuàng)建方法；3.掌握二叉樹的先序、中序、后序的遞歸實現(xiàn)方法。二、實驗內(nèi)容和要求：創(chuàng)建二叉樹，分別對該二叉樹進行先序、中序、后序遍歷，并輸出遍歷結(jié)果。三、叉樹的建立與遍歷代碼如下：#include #include struct tnode/結(jié)點結(jié)構(gòu)體char data;struct tnode *lchild,*rchild;typedef struct tnode TNODE;TNODE *creat(void)TNODE *root,*p;TNODE *queue50; int front=0,rear=-1,counter=0;/初始隊列中需要的變量front、rear和計數(shù)器counterchar ch;printf(建立二叉樹，請輸入結(jié)點:（#表示虛節(jié)點,!表示結(jié)束)n); ch=getchar();while(ch!=!)if(ch!=#) p=(TNODE *)malloc(sizeof(TNODE); p-data=ch; p-lchild=NULL; p-rchild=NULL;rear+; queuerear=p;/把非#的元素入隊if(rear=0)/如果是第一個元素，則作為根節(jié)點root=p;counter+;elseif(counter%2=1)/奇數(shù)時與其雙親的左子樹連接queuefront-lchild=p;if(counter%2=0)/偶數(shù)時與其雙親的右子樹連接queuefront-rchild=p;front+;counter+; else/為#時，計數(shù)，但不連接結(jié)點if(counter%2=0)front+;counter+;ch=getchar();return root;void preorder(TNODE *bt)/先序遍歷if(bt!=NULL)printf(%c ,bt-data);preorder(bt-lchild);preorder(bt-rchild); void inorder(TNODE *bt)/中序遍歷if(bt!=NULL)inorder(bt-lchild);printf(%c ,bt-data);inorder(bt-rchild); void postorder(TNODE *bt)/后序遍歷if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild);printf(%c ,bt-data); int main() TNODE *root; root=creat();printf(遞歸先序遍歷是:); preorder(root);printf(n);printf(遞歸中序遍歷是：);inorder(root);printf(n);printf(遞歸后序遍歷是：);postorder(root);printf(n);return 0;四、程序運行結(jié)果：五、程序設(shè)計指導(dǎo)：1.創(chuàng)建二叉樹的算法：首先對一般的二叉樹，添加若干個虛結(jié)點使其成為完全二叉樹，然后依次輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點，若是第一個，則令其為根結(jié)點，否則將新結(jié)點鏈接至它的雙親結(jié)點上。如此重復(fù)下去，直至遇到輸入結(jié)束符（自定）為止。為了使新結(jié)點能夠與雙親結(jié)點正確相連，并考慮到這種方法中先建立的結(jié)點其孩子結(jié)點也一定先建立的特點，可以設(shè)置一個指針類型的數(shù)組構(gòu)成的隊列來保存已輸入結(jié)點的地址，并使隊尾(rear)指向當(dāng)前輸入的結(jié)點，隊頭(front)指向這個結(jié)點的雙親結(jié)點的前一個位置。由于根結(jié)點的地址放在隊列的第一個單元里，所以當(dāng)rear為奇數(shù)時，則rear所指的結(jié)點應(yīng)作為左孩子與其雙親鏈接，否則rear所指的結(jié)點應(yīng)作為右孩子與其雙親鏈接。若雙親結(jié)點或孩子結(jié)點為虛結(jié)點，則無須鏈接。若一個雙親結(jié)點與兩個孩子鏈接完畢，則進行出隊操作，使隊頭指針指向下一個待鏈接的雙親結(jié)點。2. void preorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先讀取，再進行進入下一個遞歸循環(huán)中。3.void inorder(TNODE *bt)函數(shù) ：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先左子樹，再讀取結(jié)點元素，再進行進入下一個遞歸循環(huán)中。4.void postorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先分別進入左右子樹，再進行讀取，再進行進入下一個遞歸循環(huán)中。六、心得體會：本次數(shù)據(jù)結(jié)構(gòu)程序設(shè)計對我有一定的幫助。通過這次的實踐，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更深入地了解。在寫程序的過程中，我重復(fù)地讀課