二叉樹結好資料

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

2、子樹CreateBiTree(T-rchild);return 0;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é)點Visit(T);訪問右子結點InOrder(T-rchild);后序遍歷vo

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

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

5、stack.empty()if(p != NULL)存入棧中stack.push(p);遍歷左子樹p = p-lchild;else退棧，訪問根節(jié)點p = stack.top();printf(%c ,p-data);stack.pop();訪問右子樹p = p-rchild;/while后序遍歷【思路】：T是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判 斷根結點的左右子樹是否均遍歷過。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不空時循環(huán)while(p != NULL II !stack.empty()遍歷左子樹while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;訪問過左子樹BT-tag = L; stack.push(BT);p = p-lchild;左右子樹訪問完畢訪問根節(jié)點while(!stack.empty() & (stack.

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

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

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

10、a;構造左子樹CreateBiTree(T-lchild);構造右子樹CreateBiTree(T-rchild);return 0;輸出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

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

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

13、p = T;棧不空或者p不空時循環(huán)while(p II !stack.empty()if(p != NULL)存入棧中stack.push(p);遍歷左子樹p = p-lchild;else退棧，訪問根節(jié)點p = stack.top();printf(%c ,p-data);stack.pop();訪問右子樹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不空時循環(huán)while(p != NULL II !stack.empty()遍歷左子樹while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;訪問過左子樹BT-tag = L;stack.push(BT);p = p-lchild;左右子樹訪問完畢訪問根節(jié)點 while(!stack.empty() & (stack.top()-tag = R) BT = stack.top();退棧stack.pop();BT-b

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