二叉樹的遞歸遍歷

二叉樹的遞歸遍歷算法，寫法很簡單，比如說前序遍歷樹，如下：

//前序遍歷 void PreOrderTraverse(BiTree tree) {if (NULL != tree){VisitNode(tree->data);PreOrderTraverse(tree->lchild);PreOrderTraverse(tree->rchild);} }
遞歸算法 就幾行代碼也很好理解。

二叉樹的非遞歸遍歷

我們知道遞歸遍歷算法也是有缺點的，就是當遞歸的深度很深的時候，會銷毀大量的內存而且不被釋放，只有在最里層的函數返回是才開始釋放資源，這就存在許多的函數的壓棧出棧開銷，會影響效率。所有當樹的度非常深的時候，用遞歸遍歷不是最好的選擇。下面我們介紹一種非遞歸遍歷樹的方式。使用棧來實現非遞歸遍歷，這里我們使用企業級的鏈棧，就是企業級鏈表構成的棧，如果不知道企業級鏈表請看：數據結構與算法：企業級鏈表實現（超詳細）。主要是使用到一個標志位，當標志位為false時將它的孩子結點入棧 ，然后將其標志位改為true ，當標志位true 時訪問結點。 二叉樹的非遞歸遍歷算法如下：

//非遞歸方式遍歷樹 void nonrecursionPreTraverse(BiTree tree) {LinkStack* stack = Create_LinkStack();_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));bNode->flag = 0;bNode->tree = tree;Push_LinkStack(stack, (StackNode*)bNode);while (stack->size!=0){_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);if (NULL == node->tree){continue;}if (node->flag == 1){//訪問結點printf("%c ", node->tree->data);}else{_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode)); _BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));lNode->flag = 0;lNode->tree = node->tree->lchild;rNode->flag = 0;rNode->tree = node->tree->rchild;//非遞歸前序遍歷---------//前序遍歷是 根 左 右 ，那么他們的壓棧順序是 右 左 根Push_LinkStack(stack, (StackNode*)rNode);Push_LinkStack(stack, (StackNode*)lNode);node->flag = 1;Push_LinkStack(stack, (StackNode*)node);非遞歸中序遍歷----------中序遍歷是 左 根 右 ，那么他們的壓棧順序是 右 根 左//Push_LinkStack(stack, (StackNode*)rNode);//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//Push_LinkStack(stack, (StackNode*)lNode);非遞歸后序遍歷----------后序遍歷是 左 右 根，那么他們的壓棧順序是 根 右 左//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//Push_LinkStack(stack, (StackNode*)rNode);//Push_LinkStack(stack, (StackNode*)lNode);}}printf("\n");return; }

完整代碼

CompanyLinkStack.h

#pragma once #ifndef __COMPANY_LINKSTACK_H__ #define __COMPANY_LINKSTACK_H__ typedef enum { ERROR, OK } STATUS; //狀態信息 ERROR 發生錯誤 OK 一切正常 //棧結點 結構體 typedef struct StackNode {struct StackNode* next; }StackNode; //棧 結構體 typedef struct LinkStack {StackNode* top;//棧頂指針int size;//棧結點元素個數 }LinkStack;//創建鏈棧 并初始化 LinkStack* Create_LinkStack();//壓棧 int Push_LinkStack(LinkStack* stack, StackNode* node);//彈棧 StackNode* Pop_LinkStack(LinkStack* stack);//棧元素個數 int Length_LinkStack(LinkStack* stack);#endif // !__COMPANY_LINKSTACK_H__

CompanyLinkStack.c

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "CompanyLinkStack.h"//創建鏈棧 并初始化 LinkStack* Create_LinkStack() {LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));stack->size = 0;stack->top = NULL;return stack; }//壓棧 int Push_LinkStack(LinkStack* stack,StackNode* node) {if (NULL == stack || NULL == node){return ERROR;}node->next = stack->top;stack->top = node;stack->size++;return OK; }//彈棧 StackNode* Pop_LinkStack(LinkStack* stack) {if (NULL == stack || stack->size == 0){return NULL;}StackNode* top = stack->top;stack->top = stack->top->next;stack->size--;return top; }//棧元素個數 int Length_LinkStack(LinkStack* stack) {if (NULL == stack){return ERROR;}return stack->size; }

BiTree.c

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "CompanyLinkStack.h" typedef char EleType; typedef struct BiTNode {EleType data;//數據結點數據域struct BiTNode *lchild, *rchild;//左孩子，右孩子結點指針域 }BiTNode,*BiTree;//棧結點 結構體，將樹結點包起來使用企業級鏈棧 typedef struct _BiTNode {StackNode node;BiTNode* tree;int flag; }_BiTNode;//約定通過前序遍歷創建結點 //每個結點都有左右孩子，孩子不存在為NULL void CreatBiTree(BiTree* tree) {char c;scanf("%c",&c);if (' '== c){*tree = NULL;}else{*tree = (BiTNode*)malloc(sizeof(BiTNode));(*tree)->data = c;CreatBiTree(&(*tree)->lchild);//創建左子樹CreatBiTree(&(*tree)->rchild);//創建右子樹} } void VisitNode(EleType data) {printf("%c ", data);return; } //前序遍歷 void PreOrderTraverse(BiTree tree) {if (NULL != tree){VisitNode(tree->data);PreOrderTraverse(tree->lchild);PreOrderTraverse(tree->rchild);} } //中序遍歷 void MidOrderTraverse(BiTree tree) {if (NULL != tree){MidOrderTraverse(tree->lchild);VisitNode(tree->data);MidOrderTraverse(tree->rchild);} } //后序遍歷 void PostOrderTraverse(BiTree tree) {if (NULL != tree){PostOrderTraverse(tree->lchild);PostOrderTraverse(tree->rchild);VisitNode(tree->data);} } //非遞歸方式遍歷樹 void nonrecursionPreTraverse(BiTree tree) {LinkStack* stack = Create_LinkStack();_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));bNode->flag = 0;bNode->tree = tree;Push_LinkStack(stack, (StackNode*)bNode);while (stack->size!=0){_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);if (NULL == node->tree){continue;}if (node->flag == 1){//訪問結點printf("%c ", node->tree->data);}else{_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode)); _BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));lNode->flag = 0;lNode->tree = node->tree->lchild;rNode->flag = 0;rNode->tree = node->tree->rchild;//非遞歸前序遍歷---------//前序遍歷是 根 左 右 ，那么他們的壓棧順序是 右 左 根Push_LinkStack(stack, (StackNode*)rNode);Push_LinkStack(stack, (StackNode*)lNode);node->flag = 1;Push_LinkStack(stack, (StackNode*)node);非遞歸中序遍歷----------中序遍歷是 左 根 右 ，那么他們的壓棧順序是 右 根 左//Push_LinkStack(stack, (StackNode*)rNode);//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//Push_LinkStack(stack, (StackNode*)lNode);非遞歸后序遍歷----------后序遍歷是 左 右 根，那么他們的壓棧順序是 根 右 左//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//Push_LinkStack(stack, (StackNode*)rNode);//Push_LinkStack(stack, (StackNode*)lNode);}}return; } //非遞歸方式遍歷樹 void nonrecursionMidTraverse(BiTree tree) {LinkStack* stack = Create_LinkStack();_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));bNode->flag = 0;bNode->tree = tree;Push_LinkStack(stack, (StackNode*)bNode);while (stack->size != 0){_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);if (NULL == node->tree){continue;}if (node->flag == 1){//訪問結點printf("%c ", node->tree->data);}else{_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode));_BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));lNode->flag = 0;lNode->tree = node->tree->lchild;rNode->flag = 0;rNode->tree = node->tree->rchild;非遞歸前序遍歷---------前序遍歷是 根 左 右 ，那么他們的壓棧順序是 右 左 根//Push_LinkStack(stack, (StackNode*)rNode);//Push_LinkStack(stack, (StackNode*)lNode);//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//非遞歸中序遍歷----------//中序遍歷是 左 根 右 ，那么他們的壓棧順序是 右 根 左Push_LinkStack(stack, (StackNode*)rNode);node->flag = 1;Push_LinkStack(stack, (StackNode*)node);Push_LinkStack(stack, (StackNode*)lNode);非遞歸后序遍歷----------后序遍歷是 左 右 根，那么他們的壓棧順序是 根 右 左//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//Push_LinkStack(stack, (StackNode*)rNode);//Push_LinkStack(stack, (StackNode*)lNode);}}return; } //非遞歸方式遍歷樹 void nonrecursionPostTraverse(BiTree tree) {LinkStack* stack = Create_LinkStack();_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));bNode->flag = 0;bNode->tree = tree;Push_LinkStack(stack, (StackNode*)bNode);while (stack->size != 0){_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);if (NULL == node->tree){continue;}if (node->flag == 1){//訪問結點printf("%c ", node->tree->data);}else{_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode));_BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));lNode->flag = 0;lNode->tree = node->tree->lchild;rNode->flag = 0;rNode->tree = node->tree->rchild;非遞歸前序遍歷---------前序遍歷是 根 左 右 ，那么他們的壓棧順序是 右 左 根//Push_LinkStack(stack, (StackNode*)rNode);//Push_LinkStack(stack, (StackNode*)lNode);//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);非遞歸中序遍歷----------中序遍歷是 左 根 右 ，那么他們的壓棧順序是 右 根 左//Push_LinkStack(stack, (StackNode*)rNode);//node->flag = 1;//Push_LinkStack(stack, (StackNode*)node);//Push_LinkStack(stack, (StackNode*)lNode);//非遞歸后序遍歷----------//后序遍歷是 左 右 根，那么他們的壓棧順序是 根 右 左node->flag = 1;Push_LinkStack(stack, (StackNode*)node);Push_LinkStack(stack, (StackNode*)rNode);Push_LinkStack(stack, (StackNode*)lNode);}}return; }int main(int argc, char *argv[]) {BiTree tree = NULL;printf("請按前序遍歷的方式輸入結點數據，沒有結點不存在請使用空格代替：");CreatBiTree(&tree);printf("前序遍歷：");PreOrderTraverse(tree);printf("\n中序遍歷：");MidOrderTraverse(tree);printf("\n后序遍歷：");PostOrderTraverse(tree);printf("\n非遞歸前序遍歷：");nonrecursionPreTraverse(tree);printf("\n非遞歸中序遍歷：");nonrecursionMidTraverse(tree);printf("\n非遞歸后序遍歷：");nonrecursionPostTraverse(tree);printf("\n");return 0; }

代碼運行檢測

我們來遍歷如下圖的二叉樹：

注意：我們創建結點時的前序輸入:ABC__D__EF__G__，一個_表示一個空格喲。

下面是運行結果，和原來遞歸遍歷結果是一樣的。

總結

以上是生活随笔為你收集整理的树：二叉树的非递归遍历算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。