二叉樹(shù)結(jié)好資料

1、二叉樹(shù)結(jié)點(diǎn)typedef struct BiTNode數(shù)據(jù)char data;左右孩子指針struct BiTNode *lchild,*rchild;BiTNode,*BiTree;按先序序列創(chuàng)建二叉樹(shù)int CreateBiTree(BiTree & T)char data;，表示空樹(shù)按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值(一個(gè)字符), scanf(%c,&data);，表示空樹(shù)if(data = #)T = NULL; elseT = (BiTree)malloc(sizeof(BiTNode);生成根結(jié)點(diǎn)T-data = data;構(gòu)造左子樹(shù)CreateBiTree(T-lchild);構(gòu)造右

2、子樹(shù)CreateBiTree(T-rchild);return 0;void Visit(BiTree T) if(T-data != #)printf(%c ,T-data);先序遍歷void PreOrder(BiTree T)if(T != NULL)訪問(wèn)根節(jié)點(diǎn)Visit(T);訪問(wèn)左子結(jié)點(diǎn)PreOrder(T-lchild);訪問(wèn)右子結(jié)點(diǎn)PreOrder(T-rchild);中序遍歷void InOrder(BiTree T)if(T != NULL)訪問(wèn)左子結(jié)點(diǎn)InOrder(T-lchild);訪問(wèn)根節(jié)點(diǎn)Visit(T);訪問(wèn)右子結(jié)點(diǎn)InOrder(T-rchild);后序遍歷vo

3、id PostOrder(BiTree T)if(T != NULL)訪問(wèn)左子結(jié)點(diǎn)PostOrder(T-lchild);訪問(wèn)右子結(jié)點(diǎn)PostOrder(T-rchild);訪問(wèn)根節(jié)點(diǎn)Visit(T);/*先序遍歷(非遞歸)思路：訪問(wèn)T-data后，將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén), 出棧，再先序遍歷T的右子樹(shù)。*/void PreOrder2(BiTree T) stackvBiTree stack;p是遍歷指針BiTree p = T;棧不空或者p不空時(shí)循環(huán)while(p II !stack.empty()if(p != NULL)存入棧中stack.push(p)

4、;訪問(wèn)根節(jié)點(diǎn)printf(%c ,p-data);遍歷左子樹(shù)p = p-lchild;else退棧p = stack.top();stack.pop();訪問(wèn)右子樹(shù)p = p-rchild;/whilev2中序遍歷【思路】：T是要遍歷樹(shù)的根指針，中序遍歷要求在遍歷完左子樹(shù)后，訪問(wèn)根，再遍歷右子 樹(shù)。先將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén),出棧，訪問(wèn) T-data,再中序遍歷T的右子樹(shù)。cpp view plaincopyvoid InOrder2(BiTree T)stack stack;/p是遍歷指針BiTree p = T;棧不空或者p不空時(shí)循環(huán)while(p II !

5、stack.empty()if(p != NULL)存入棧中stack.push(p);遍歷左子樹(shù)p = p-lchild;else退棧，訪問(wèn)根節(jié)點(diǎn)p = stack.top();printf(%c ,p-data);stack.pop();訪問(wèn)右子樹(shù)p = p-rchild;/while后序遍歷【思路】：T是要遍歷樹(shù)的根指針，后序遍歷要求在遍歷完左右子樹(shù)后，再訪問(wèn)根。需要判 斷根結(jié)點(diǎn)的左右子樹(shù)是否均遍歷過(guò)。cpp view plaincopy后序遍歷(非遞歸)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTre

6、ePost;void PostOrder2(BiTree T)stackvBiTreePost stack;/p是遍歷指針BiTree p = T;BiTreePost BT;棧不空或者p不空時(shí)循環(huán)while(p != NULL II !stack.empty()遍歷左子樹(shù)while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;訪問(wèn)過(guò)左子樹(shù)BT-tag = L; stack.push(BT);p = p-lchild;左右子樹(shù)訪問(wèn)完畢訪問(wèn)根節(jié)點(diǎn)while(!stack.empty() & (stack.

7、top()-tag = R)BT = stack.top();退棧stack.pop();BT-biTree;printf(%c ,BT-biTree-data);遍歷右子樹(shù)if(!stack.empty()BT = stack.top();訪問(wèn)過(guò)右子樹(shù)BT-tag = R;p = BT-biTree; p = p-rchild;/while層次遍歷【思路】：按從頂向下，從左至右的順序來(lái)逐層訪問(wèn)每個(gè)節(jié)點(diǎn)，層次遍歷的過(guò)程中需要用隊(duì) 列。cpp view plaincopy層次遍歷void LevelOrder(BiTree T)BiTree p = T;隊(duì)列queuevBiTree queue;

8、根節(jié)點(diǎn)入隊(duì)queue.push(p);隊(duì)列不空循環(huán)while(!queue.empty()對(duì)頭元素出隊(duì)p = queue.front();訪問(wèn)p指向的結(jié)點(diǎn)printf(%c ,p-data);退出隊(duì)列queue.pop();左子樹(shù)不空，將左子樹(shù)入隊(duì)if(p-lchild != NULL) queue.push(p-lchild);右子樹(shù)不空，將右子樹(shù)入隊(duì)if(p-rchild != NULL) queue.push(p-rchild);測(cè)試用例：輸入：ABC#DE#G#F# 輸出：代碼：cpp view plaincopy #includeviostream #includevstack #i

9、ncludevqueue using namespace std;二叉樹(shù)結(jié)點(diǎn)typedef struct BiTNode數(shù)據(jù)char data;左右孩子指針struct BiTNode *lchild,*rchild;BiTNode,*BiTree;按先序序列創(chuàng)建二叉樹(shù)int CreateBiTree(BiTree & T)char data;，表示空樹(shù)按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值(一個(gè)字符), scanf(%c,&data);，表示空樹(shù)if(data = #)T = NULL; elseT = (BiTree)malloc(sizeof(BiTNode);生成根結(jié)點(diǎn)T-data = dat

10、a;構(gòu)造左子樹(shù)CreateBiTree(T-lchild);構(gòu)造右子樹(shù)CreateBiTree(T-rchild);return 0;輸出void Visit(BiTree T) if(T-data != #)printf(%c ,T-data);先序遍歷void PreOrder(BiTree T)if(T != NULL)訪問(wèn)根節(jié)點(diǎn)Visit(T);訪問(wèn)左子結(jié)點(diǎn)PreOrder(T-lchild);訪問(wèn)右子結(jié)點(diǎn)PreOrder(T-rchild);中序遍歷void InOrder(BiTree T)if(T != NULL)訪問(wèn)左子結(jié)點(diǎn)InOrder(T-lchild);訪問(wèn)根節(jié)點(diǎn)Visi

11、t(T);訪問(wèn)右子結(jié)點(diǎn)InOrder(T-rchild);后序遍歷void PostOrder(BiTree T)if(T != NULL)訪問(wèn)左子結(jié)點(diǎn)PostOrder(T-lchild);訪問(wèn)右子結(jié)點(diǎn)PostOrder(T-rchild);訪問(wèn)根節(jié)點(diǎn)Visit(T);/*先序遍歷(非遞歸)思路：訪問(wèn)T-data后，將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén), 出棧，再先序遍歷T的右子樹(shù)。*/void PreOrder2(BiTree T)stackvBiTree stack;p是遍歷指針BiTree p = T;棧不空或者p不空時(shí)循環(huán)while(p II !stack.emp

12、ty()if(p != NULL)存入棧中stack.push(p);訪問(wèn)根節(jié)點(diǎn)printf(%c ,p-data);遍歷左子樹(shù)p = p-lchild;else退棧p = stack.top(); stack.pop();訪問(wèn)右子樹(shù)p = p-rchild;/while/*中序遍歷(非遞歸)思路：T是要遍歷樹(shù)的根指針，中序遍歷要求在遍歷完左子樹(shù)后，訪問(wèn)根，再遍歷右子 樹(shù)。先將T入棧，遍歷左子樹(shù)；遍歷完左子樹(shù)返回時(shí)，棧頂元素應(yīng)為T(mén),出棧，訪問(wèn) T-data,再中序遍歷T的右子樹(shù)。*/void InOrder2(BiTree T)stackvBiTree stack;/p是遍歷指針BiTree

13、p = T;棧不空或者p不空時(shí)循環(huán)while(p II !stack.empty()if(p != NULL)存入棧中stack.push(p);遍歷左子樹(shù)p = p-lchild;else退棧，訪問(wèn)根節(jié)點(diǎn)p = stack.top();printf(%c ,p-data);stack.pop();訪問(wèn)右子樹(shù)p = p-rchild;/while后序遍歷(非遞歸)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTreePost;void PostOrder2(BiTree T)stackvBiTreePost st

14、ack;/p是遍歷指針BiTree p = T;BiTreePost BT;棧不空或者p不空時(shí)循環(huán)while(p != NULL II !stack.empty()遍歷左子樹(shù)while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;訪問(wèn)過(guò)左子樹(shù)BT-tag = L;stack.push(BT);p = p-lchild;左右子樹(shù)訪問(wèn)完畢訪問(wèn)根節(jié)點(diǎn) while(!stack.empty() & (stack.top()-tag = R) BT = stack.top();退棧stack.pop();BT-b

15、iTree;printf(%c ,BT-biTree-data);遍歷右子樹(shù)if(!stack.empty()BT = stack.top();訪問(wèn)過(guò)右子樹(shù)BT-tag = R;p = BT-biTree;p = p-rchild;/while層次遍歷void LevelOrder(BiTree T)BiTree p = T;隊(duì)列queuevBiTree queue;根節(jié)點(diǎn)入隊(duì)queue.push(p);隊(duì)列不空循環(huán)while(!queue.empty()對(duì)頭元素出隊(duì)p = queue.front();訪問(wèn)p指向的結(jié)點(diǎn)printf(%c ,p-data);退出隊(duì)列queue.pop();左子樹(shù)不空，將左子樹(shù)入隊(duì) if(p-lchild != NULL) queue.push(p-lchild);右子樹(shù)不空，將右子樹(shù)入隊(duì) if(p-rchild != NULL) queue.push(p-rchild);int main()BiTree T;CreateBiTree(T); printf(先序遍歷：n); PreOrder(T);printf(n);printf(”先序