?

??????? “樹”是一種重要的數(shù)據(jù)結(jié)構(gòu)，本文淺談二叉樹的遍歷問題，採用C語言描寫敘述。

?

一、二叉樹基礎(chǔ)

1）定義：有且僅有一個(gè)根結(jié)點(diǎn)，除根節(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)僅僅有一個(gè)父結(jié)點(diǎn)，最多含有兩個(gè)子節(jié)點(diǎn)，子節(jié)點(diǎn)有左右之分。
2）存儲(chǔ)結(jié)構(gòu)

????????二叉樹的存儲(chǔ)結(jié)構(gòu)能夠採用順序存儲(chǔ)，也能夠採用鏈?zhǔn)酱鎯?chǔ)，當(dāng)中鏈?zhǔn)酱鎯?chǔ)更加靈活。

??????? 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，與線性鏈表類似，二叉樹的每一個(gè)結(jié)點(diǎn)採用結(jié)構(gòu)體表示，結(jié)構(gòu)體包括三個(gè)域：數(shù)據(jù)域、左指針、右指針。

??????? 二叉樹在C語言中的定義例如以下：???????

struct BiTreeNode{int c;struct BiTreeNode *left;struct BiTreeNode *right; };

?

二、二叉樹的遍歷

??????? “遍歷”是二叉樹各種操作的基礎(chǔ)。二叉樹是一種非線性結(jié)構(gòu)，其遍歷不像線性鏈表那樣easy，無法通過簡單的循環(huán)實(shí)現(xiàn)。

??????? 二叉樹是一種樹形結(jié)構(gòu)，遍歷就是要讓樹中的全部節(jié)點(diǎn)被且僅被訪問一次，即按一定規(guī)律排列成一個(gè)線性隊(duì)列。二叉（子）樹是一種遞歸定義的結(jié)構(gòu)，包括三個(gè)部分：根結(jié)點(diǎn)（N）、左子樹（L）、右子樹（R）。依據(jù)這三個(gè)部分的訪問次序?qū)Χ鏄涞谋闅v進(jìn)行分類，總共同擁有6種遍歷方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉樹的遍歷就是研究這6種詳細(xì)的遍歷方案，顯然依據(jù)簡單的對稱性，左子樹和右子樹的遍歷可互換，即NLR與NRL、LNR與RNL、LRN與RLN，分別相類似，因而僅僅需研究NLR、LNR和LRN三種就可以，分別稱為“先序遍歷”、“中序遍歷”和“后序遍歷”。

??????? 二叉樹遍歷通常借用“?！边@樣的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，有兩種方式：遞歸方式及非遞歸方式。

??????? 在遞歸方式中，棧是由操作系統(tǒng)維護(hù)的，用戶不必關(guān)心棧的細(xì)節(jié)操作，用戶僅僅需關(guān)心“訪問順序”就可以。因而，採用遞歸方式實(shí)現(xiàn)二叉樹的遍歷比較easy理解，算法簡單，easy實(shí)現(xiàn)。

??????? 遞歸方式實(shí)現(xiàn)二叉樹遍歷的C語言代碼例如以下：

//先序遍歷--遞歸 int traverseBiTreePreOrder(BiTreeNode *ptree,int (*visit)(int)) {if(ptree){if(visit(ptree->c))if(traverseBiTreePreOrder(ptree->left,visit))if(traverseBiTreePreOrder(ptree->right,visit))return 1; //正常返回return 0; //錯(cuò)誤返回}else return 1; //正常返回 } //中序遍歷--遞歸 int traverseBiTreeInOrder(BiTreeNode *ptree,int (*visit)(int)) {if(ptree){if(traverseBiTreeInOrder(ptree->left,visit))if(visit(ptree->c))if(traverseBiTreeInOrder(ptree->right,visit))return 1;return 0;}else return 1; } //后序遍歷--遞歸 int traverseBiTreePostOrder(BiTreeNode *ptree,int (*visit)(int)) {if(ptree){if(traverseBiTreePostOrder(ptree->left,visit))if(traverseBiTreePostOrder(ptree->right,visit))if(visit(ptree->c))return 1;return 0;}else return 1; }

??????? 以上代碼中，visit為一函數(shù)指針，用于傳遞二叉樹中對結(jié)點(diǎn)的操作方式，其原型為：int (*visit)(char)。

??????? 大家知道，函數(shù)在調(diào)用時(shí)，會(huì)自己主動(dòng)進(jìn)行棧的push，調(diào)用返回時(shí)，則會(huì)自己主動(dòng)進(jìn)行棧的pop。函數(shù)遞歸調(diào)用無非是對一個(gè)棧進(jìn)行返回的push與pop，既然遞歸方式能夠?qū)崿F(xiàn)二叉樹的遍歷，那么借用“?！睊裼梅沁f歸方式，也能實(shí)現(xiàn)遍歷?？墒?#xff0c;這時(shí)的棧操作（push、pop等）是由用戶進(jìn)行的，因而實(shí)現(xiàn)起來會(huì)復(fù)雜一些，并且也不easy理解，但有助于我們對樹結(jié)構(gòu)的遍歷有一個(gè)深刻、清晰的理解。

??????? 在討論非遞歸遍歷之前，我們先定義棧及各種須要用到的棧操作：

//棧的定義，棧的數(shù)據(jù)是“樹結(jié)點(diǎn)的指針” struct Stack{BiTreeNode **top;BiTreeNode **base;int size; }; #define STACK_INIT_SIZE 100 #define STACK_INC_SIZE 10 //初始化空棧，預(yù)分配存儲(chǔ)空間 Stack* initStack() {Stack *qs=NULL;qs=(Stack *)malloc(sizeof(Stack));qs->base=(BiTreeNode **)calloc(STACK_INIT_SIZE,sizeof(BiTreeNode *));qs->top=qs->base;qs->size=STACK_INIT_SIZE;return qs; } //取棧頂數(shù)據(jù) BiTreeNode* getTop(Stack *qs) {BiTreeNode *ptree=NULL;if(qs->top==qs->base)return NULL;ptree=*(qs->top-1);return ptree; } //入棧操作 int push(Stack *qs,BiTreeNode *ptree) {if(qs->top-qs->base>=qs->size){qs->base=(BiTreeNode **)realloc(qs->base,(qs->size+STACK_INC_SIZE)*sizeof(BiTreeNode *));qs->top=qs->base+qs->size;qs->size+=STACK_INC_SIZE;}*qs->top++=ptree;return 1; } //出棧操作 BiTreeNode* pop(Stack *qs) {if(qs->top==qs->base)return NULL;return *--qs->top; } //推斷棧是否為空 int isEmpty(Stack *qs) {return qs->top==qs->base; }

????????首先考慮非遞歸先序遍歷（NLR）。在遍歷某一個(gè)二叉（子）樹時(shí)，以一當(dāng)前指針記錄當(dāng)前要處理的二叉（左子）樹，以一個(gè)棧保存當(dāng)前樹之后處理的右子樹。首先訪問當(dāng)前樹的根結(jié)點(diǎn)數(shù)據(jù)，接下來應(yīng)該依次遍歷其左子樹和右子樹，然而程序的控制流僅僅能處理其一，所以考慮將右子樹的根保存在棧里面，當(dāng)前指針則指向需先處理的左子樹，為下次循環(huán)做準(zhǔn)備；若當(dāng)前指針指向的樹為空，說明當(dāng)前樹為空樹，不須要做不論什么處理，直接彈出棧頂?shù)淖訕?#xff0c;為下次循環(huán)做準(zhǔn)備。對應(yīng)的C語言代碼例如以下：

//先序遍歷--非遞歸 int traverseBiTreePreOrder2(BiTreeNode *ptree,int (*visit)(int)) {Stack *qs=NULL;BiTreeNode *pt=NULL;qs=initStack();pt=ptree;while(pt || !isEmpty(qs)){if(pt){if(!visit(pt->c)) return 0; //錯(cuò)誤返回push(qs,pt->right);pt=pt->left;}else pt=pop(qs);}return 1; //正常返回 }

??????? 相對于非遞歸先序遍歷，非遞歸的中序/后序遍歷稍復(fù)雜一點(diǎn)。

??????? 對于非遞歸中序遍歷，若當(dāng)前樹不為空樹，則訪問其根結(jié)點(diǎn)之前應(yīng)先訪問其左子樹，因而先將當(dāng)前根節(jié)點(diǎn)入棧，然后考慮其左子樹，不斷將非空的根節(jié)點(diǎn)入棧，直到左子樹為一空樹；當(dāng)左子樹為空時(shí)，不須要做不論什么處理，彈出并訪問棧頂結(jié)點(diǎn)，然后指向其右子樹，為下次循環(huán)做準(zhǔn)備。

//中序遍歷--非遞歸 int traverseBiTreeInOrder2(BiTreeNode *ptree,int (*visit)(int)) {Stack *qs=NULL;BiTreeNode *pt=NULL;qs=initStack();pt=ptree;while(pt || !isEmpty(qs)){if(pt){push(qs,pt);pt=pt->left;}else{pt=pop(qs);if(!visit(pt->c)) return 0;pt=pt->right;}}return 1; } //中序遍歷--非遞歸--還有一種實(shí)現(xiàn)方式 int traverseBiTreeInOrder3(BiTreeNode *ptree,int (*visit)(int)) {Stack *qs=NULL;BiTreeNode *pt=NULL;qs=initStack();push(qs,ptree);while(!isEmpty(qs)){while(pt=getTop(qs)) push(qs,pt->left);pt=pop(qs);if(!isEmpty(qs)){pt=pop(qs);if(!visit(pt->c)) return 0;push(qs,pt->right);}}return 1; }

??????? 最后談?wù)劮沁f歸后序遍歷。因?yàn)樵谠L問當(dāng)前樹的根結(jié)點(diǎn)時(shí)，應(yīng)先訪問其左、右子樹，因而先將根結(jié)點(diǎn)入棧，接著將右子樹也入棧，然后考慮左子樹，反復(fù)這一過程直到某一左子樹為空；假設(shè)當(dāng)前考慮的子樹為空，若棧頂不為空，說明第二棧頂相應(yīng)的樹的右子樹未處理，則彈出棧頂，下次循環(huán)處理，并將一空指針入棧以表示其還有一子樹已做處理；若棧頂也為空樹，說明第二棧頂相應(yīng)的樹的左右子樹或者為空，或者均已做處理，直接訪問第二棧頂?shù)慕Y(jié)點(diǎn)，訪問完結(jié)點(diǎn)后，若棧仍為非空，說明整棵樹尚未遍歷完，則彈出棧頂，并入棧一空指針表示第二棧頂?shù)淖訕渲械囊粋€(gè)已被處理。

//后序遍歷--非遞歸 int traverseBiTreePostOrder2(BiTreeNode *ptree,int (*visit)(int)) {Stack *qs=NULL;BiTreeNode *pt=NULL;qs=initStack();pt=ptree;while(1) //循環(huán)條件恒“真”{if(pt){push(qs,pt);push(qs,pt->right);pt=pt->left;}else if(!pt){pt=pop(qs);if(!pt){pt=pop(qs);if(!visit(pt->c)) return 0;if(isEmpty(qs)) return 1;pt=pop(qs);}push(qs,NULL);}}return 1; }

三、二叉樹的創(chuàng)建

??????? 談完二叉樹的遍歷之后，再來談?wù)劧鏄涞膭?chuàng)建，這里所說的創(chuàng)建是指從控制臺(tái)依次（先/中/后序）輸入二叉樹的各個(gè)結(jié)點(diǎn)元素（此處為字符），用“空格”表示空樹。

??????? 因?yàn)榭刂婆_(tái)輸入是保存在輸入緩沖區(qū)內(nèi)，因此遍歷的“順序”就反映在讀取輸入字符的次序上。

??????? 下面是遞歸方式實(shí)現(xiàn)的先序創(chuàng)建二叉樹的C代碼。

//創(chuàng)建二叉樹--先序輸入--遞歸 BiTreeNode* createBiTreePreOrder() {BiTreeNode *ptree=NULL;char ch;ch=getchar();if(ch==' ')ptree=NULL;else{ptree=(struct BiTreeNode *)malloc(sizeof(BiTreeNode));ptree->c=ch;ptree->left=createBiTreePreOrder();ptree->right=createBiTreePreOrder();}return ptree; }

??????? 對于空樹，函數(shù)直接返回就可以；對于非空樹，先讀取字符并賦值給當(dāng)前根結(jié)點(diǎn)，然后創(chuàng)建左子樹，最后創(chuàng)建右子樹。因此，要先知道當(dāng)前要?jiǎng)?chuàng)建的樹是否為空，才干做對應(yīng)處理，“先序”遍歷方式非常好地符合了這一點(diǎn)。可是中序或后序就不一樣了，更重要的是，中序或后序方式輸入的字符序列無法唯一確定一個(gè)二叉樹。我還沒有找到中序/后序?qū)崿F(xiàn)二叉樹的創(chuàng)建（控制臺(tái)輸入）的類似簡單的方法，希望各位同仁網(wǎng)友指教哈！

?

四、執(zhí)行及結(jié)果

??????? 採用例如以下的二叉樹進(jìn)行測試，首先先序輸入創(chuàng)建二叉樹，然后依次調(diào)用各個(gè)遍歷函數(shù)。

??????? 先序輸入的格式：ABC ^ ^ D E ^ G ^ ^ F ^ ^ ^???? （當(dāng)中， ^? 表示空格字符）

??????? 遍歷操作採用標(biāo)準(zhǔn)I/O庫中的putchar函數(shù)，其原型為：int putchar(int);

??????? 各種形式遍歷輸出的結(jié)果為：

??????????????? 先序：ABCDEGF

??????????????? 中序：CBEGDFA

??????????????? 后序：CGEFDBA

??????? 測試程序的主函數(shù)例如以下：

int main(int argc, char* argv[]) {BiTreeNode *proot=NULL;printf("InOrder input chars to create a BiTree: ");proot=createBiTreePreOrder(); //輸入(ABC DE G F )printf("PreOrder Output the BiTree recursively: ");traverseBiTreePreOrder(proot,putchar);printf("\n");printf("PreOrder Output the BiTree non-recursively: ");traverseBiTreePreOrder2(proot,putchar);printf("\n");printf("InOrder Output the BiTree recursively: ");traverseBiTreeInOrder(proot,putchar);printf("\n");printf("InOrder Output the BiTree non-recursively(1): ");traverseBiTreeInOrder2(proot,putchar);printf("\n");printf("InOrder Output the BiTree non-recursively(2): ");traverseBiTreeInOrder3(proot,putchar);printf("\n");printf("PostOrder Output the BiTree non-recursively: ");traverseBiTreePostOrder(proot,putchar);printf("\n");printf("PostOrder Output the BiTree recursively: ");traverseBiTreePostOrder2(proot,putchar);printf("\n");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的数据结构——二叉树的遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。