二叉树的非递归和递归遍历C语言详解

最易懂的二叉树的递归和非递归实验代码 创建一颗用作实验的二叉树    1 先根（序）遍历    2 中根（序）遍历    4 后根（序）遍历    5 测试主数    7 创建一颗用作实验的二叉树 //当然，你要先定义一个节点类型 typedefstruct NODE{ intval; struct NODE* left; struct NODE* right; }node_t,*node_p; /*从根节点开始依次安装图解完成树的创建，叶子节点两个子树为空(null)*/ node_t* CreatExTree() { node_p root; root=malloc(sizeof(node_t)); if(root==NULL) exit(1); root->val='A'; root->left=malloc(sizeof(node_t)); root->left->val='B'; root->left->left=malloc(sizeof(node_t)); root->left->left->val='D'; root->left->left->left=NULL; root->left->left->right=NULL; root->left->right=malloc(sizeof(node_t)); root->left->right->val='E'; root->left->right->left=NULL; root->left->right->right=NULL; root->right=malloc(sizeof(node_t)); root->right->val='C'; root->right->right=NULL; root->right->left=malloc(sizeof(node_t)); root->right->left->val='F'; root->right->left->left=NULL; root->right->left->right=NULL; return root; }   当然，这是最笨的一种生成特定二叉树的方法 先根（序）遍历 所谓先根遍历，也就是从先遍历根节点，然后遍历左子树，最后右子树。递归的代码非常简单： void RootFirstTrav(node_p root) { /*递归的出口*/ if(root==NULL) return; /*处理根节点*/ printf("%c ",root->val); /*处理左右子树*/ RootFirstTrav(root->left); RootFirstTrav(root->right); }   /*主函数调用测试*/ int main() { node_p s; s=CreatExTree(); RootFirstTrav(s); return 0; }   递归调用看起来并没什么难点，接下来就看看非递归调用的style： 在给出代码之前，先一下我们的循环。为了再访问完左子树后，还能倒回去访问右子树，我们不得不保存当前的节点。这里用到一个叫做堆栈的数据结构，当然这里我们用数组模拟它。 定义一个数组： #define MAX_NODE 100 Node_pstac[MAX_NODE]={0}; Inttopele=-1 //定义一个索引下标     过程描述： 我们遇到第一个根节点，处理，保存第一个节点数组情况为 A 0 0 0 0 0             topele=0; 我们访问A的左子树，不为空，处理，入栈 A B 0 0 0 0             topele=1 再继续访问左子树，不为空，处理，入栈 A B D 0 0 0             topele=2 再继续访问左子树，为空，出栈，取出栈顶元素B； A B 0 0 0 0             topele=0 处理B的右子树E，E的左子树不为空，不入栈，处理右子树，为空，不入栈。再出栈，取元素A，处理A的右子树C，C的左子树不为空，入栈，处理C。然后，处理C的左子树F，F的左右子树为空，去栈顶元素C，处理C的右子树，在取栈顶元素，栈为空，遍历结束。 代码描述： void RootFirstTrav_(node_p root) { node_pstac[MAX_NODE]; inttopele=-1; if(root==NULL) exit(1); node_p p1; p1=root; //循环出口，堆栈为空 while(p1!=NULL||topele!=-1) { while(p1!=NULL) { /*处理数据*/ printf("%c ",p1->val); stac[++topele]=p1; p1=p1->left; } if(topele!=-1) { p1=stac[topele--]->right; } } }   中根（序）遍历 递归比较简单就直接上递归的代码了 void RootSecondTrav(node_p root) { if(root==NULL) return; RootSecondTrav(root->left); printf("%c ",root->val); RootSecondTrav(root->right); }   非递归调用与先根不同的是根节点的处理时机； 也就是说入栈的时候不处理，等出栈的时候在处理： void RootSecondTrav_(node_p root) { node_pstac[MAX_NODE]; inttopele=-1; if(root==NULL) exit(1); while(root!=NULL || topele!=-1) { while(root!=NULL) { stac[++topele]=root; root=root->left; } if(topele!=-1) { root=stac[topele--]; printf("%c ",root->val); root=root->right; } } }   后根（序）遍历 依然先上递归代码： void RootLastTrav(node_p root) { if(root==NULL) return; RootLastTrav(root->left); RootLastTrav(root->right); printf("%c ",root->val); }   非递归代码： 后序遍历的非递归代码实现起来最为复杂。后序遍历的顺序是，左子树，右子树，根节点。如何从右子树到根节点，是一个难点。这里采用一个标志位flag，来标识访问的次数，来区分是从左子树，还是右边子树返回的。 下面的表格表示一个堆栈的结构，第一列表示stac元素，第二列表示flag元素 A 1                         A 1 B 1                     A 1 B 1 D 1                 topele=2 A 1 B 1 D 2                 A 1 B 1   2                 A 1 B 2                     A 1 B 2 E 1->2                 A 2 C 1 F 1->2                 A 2 C 2                     依次输出 void RootLastTrav_(node_p root) { /*定义一个结构体，即带标志位的堆栈*/ typedefstruct STAC{ node_pstac; int flag; }stac_f; /*定义堆栈数组*/ stac_fStac[MAX_NODE]; inttopele=-1; if(root==NULL) exit(1); while(root!=NULL||topele!=-1) { while(root!=NULL) { /*第一次遍历根节点*/ topele++; Stac[topele].stac=root; Stac[topele].flag=1; root=root->left; } /*如果元素不为空，且是第二次遍历，则处理元素*/ while(topele!=-1&&Stac[topele].flag==2) { root=Stac[topele--].stac; printf("%c ",root->val); } if(topele!=-1) { Stac[topele].flag=2; root=Stac[topele].stac->right; } } }   测试主函数 int main() { node_p s; printf("创建实验二叉树\n"); s=CreatExTree(); printf("\n"); printf("先序遍历\n"); RootFirstTrav(s); putchar(10); RootFirstTrav_(s); putchar(10); printf("中序遍历\n"); RootSecondTrav(s); putchar(10); RootSecondTrav_(s); putchar(10); printf("后序遍历\n"); RootLastTrav(s); putchar(10); RootLastTrav(s); return 0; }   测试结果： 结语 在完全掌握二叉树的遍历后，反过来就可以通过递归来创建二叉树了。这个问会在我的下一篇关于二叉树的文档中详细讲到。