今日份分享：將樹(shù)得基本操作C語(yǔ)言實(shí)現(xiàn)，主要考察樹(shù)得先序，中序，后序和層次遍歷方法
二叉樹(shù)如圖：
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
層次：ABCDEFG
BiTree.h：typedef char TElemType;typedef int Status;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;Status PreCreateBiTree(BiTree &T);//先序輸入二叉樹(shù)Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e));Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e));Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status Visit(TElemType e);Status GetDepth(BiTree T);Status CountNode(BiTree T,int &d);
主要函數(shù)：
① 先序創(chuàng)建二叉樹(shù)注意創(chuàng)建得時(shí)候如果沒(méi)有左右子樹(shù)要輸入空格
輸入：ABC_ _DE_G_ _F_ _ _
Status PreCreateBiTree(BiTree &T){char ch;ch=getchar();if(ch==' ')T=NULL;else{if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;PreCreateBiTree(T->lchild);PreCreateBiTree(T->rchild);}return OK;}② 先序遍歷（遞歸算法）
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;}else return OK;}③ 中序遍歷（遞歸算法）
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)){if(T){InOrderTraverse2(T->lchild,Visit);Visit(T->data);InOrderTraverse2(T->rchild,Visit);}return OK;}④ 中序遍歷（非遞歸算法）
注意此處需要包含C++STL頭文件include<stack>
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)){stack<BiTree>S;BiTree p;S.push(T);while(!S.empty()){while(p=S.top())S.push(p->lchild);p=S.top();S.pop();if(!S.empty()){p=S.top();S.pop();if(!Visit(p->data))return ERROR;S.push(p->rchild);}return OK;}}⑤ 后序遍歷（遞歸算法）
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){if(T){PostOrderTraverse(T->lchild,Visit);PostOrderTraverse(T->rchild,Visit);Visit(T->data);}return OK;}⑥ 層次遍歷（使用QUEUE）
可以包含STL<queue>或者定義一個(gè)數(shù)組，使用循環(huán)隊(duì)列即可。
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){BiTree p;BiTNode *Q[100];int front,rear;front=rear=-1;rear++;Q[rear]=T;while(front!=rear){front=(front+1)%100;p=Q[front];Visit(p->data);if(p->lchild!=NULL){rear=(rear+1)%100;Q[rear]=p->lchild;}if(p->rchild!=NULL){rear=(rear+1)%100;Q[rear]=p->rchild;}}return OK;}⑦ Visit函數(shù)此處使用得是輸出
Status Visit(TElemType e){printf("%c ",e);return OK;}⑧ 計(jì)算樹(shù)得節(jié)點(diǎn)數(shù)
Status CountNode(BiTree T,int &d){if(T){d++;CountNode(T->lchild,d);CountNode(T->rchild,d);}return OK;}⑨ 計(jì)算樹(shù)得深度
Status GetDepth(BiTree T){int hl,hr;if(T==NULL)return 0;else{hl=GetDepth(T->lchild);hr=GetDepth(T->rchild);if(hl>hr)return hl+1;else return hr+1;}}Main函數(shù)：
int main(){printf("Create\n");BiTree T;PreCreateBiTree(T);printf("先序PreTraverse:\n");PreOrderTraverse(T,Visit);printf("\n中序InTraverse:\n");InOrderTraverse2(T,Visit);printf("\n后序PostTraverse:\n");PostOrderTraverse(T,Visit);printf("\nLevelTraverse:\n");LevelOrderTraverse(T,Visit);printf("\n");CountNode(T,d);printf("\n節(jié)點(diǎn)數(shù):%d\n",d);printf("樹(shù)得深度:%d\n",GetDepth(T));system("pause");return 0;}
注意：
1. 遍歷函數(shù)可以寫成遞歸和非遞歸，遞歸函數(shù)更加簡(jiǎn)潔。
2. 層次遍歷需要使用隊(duì)列，可以包含C++STL<queue>或者定義一個(gè)數(shù)組，使用循環(huán)隊(duì)列即可。注意每次判斷時(shí)要把隊(duì)列得頭賦值給臨時(shí)變量P，左右子樹(shù)從隊(duì)尾插入。
3.先序創(chuàng)建樹(shù)時(shí)，要注意創(chuàng)建得時(shí)候如果沒(méi)有左右子樹(shù)要輸入空格
輸入：ABC_ _DE_G_ _F_ _ _
————
希望對(duì)大家有幫助，有什么C/C++學(xué)習(xí)上得問(wèn)題也可以來(lái)和我交流！
寫在最后：對(duì)于準(zhǔn)備學(xué)習(xí)C/C++編程得小伙伴，如果你想更好得提升你得編程核心能力（內(nèi)功）不妨從現(xiàn)在開(kāi)始！
編程學(xué)習(xí)書籍分享：
編程學(xué)習(xí)視頻分享：
整理分享（多年學(xué)習(xí)得源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）
歡迎轉(zhuǎn)行和學(xué)習(xí)編程得伙伴，利用更多得資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！
對(duì)于C/C++感興趣可以感謝對(duì)創(chuàng)作者的支持小編在后臺(tái)私信我：【編程交流】一起來(lái)學(xué)習(xí)哦！可以領(lǐng)取一些C/C++得項(xiàng)目學(xué)習(xí)視頻資料哦！已經(jīng)設(shè)置好了關(guān)鍵詞自動(dòng)回復(fù)，自動(dòng)領(lǐng)取就好了！
