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

《二叉树的非递归和递归遍历C语言详解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最易懂的二叉树的递归和非递归实验代码创建一颗用作实验的二叉树1先根（序）遍历2中根（序）遍历4后根（序）遍历5测试主函数7创建一颗用作实验的二叉树//当然，你要先定义一个节点类型typedefstructNODE{intval;structNODE*left;structNODE*right;}node_t,*node_p;/*从根节点开始依次安装图解完成树的创建，叶子节点两个子树为空(null)*/node_t*CreatExTree(){node_proot;root=malloc(sizeof(node_t));if(root==NULL)exit(1);root->val='

2、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-

3、>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;returnroot;}当然，这是最笨的一种生成特定二叉树的方法先根（序）遍历所谓先根遍历，也就是从先遍历根节点，然后遍历左子树，最后右子树。递归的代码

4、非常简单：voidRootFirstTrav(node_proot){/*递归的出口*/if(root==NULL)return;/*处理根节点*/printf("%c",root->val);/*处理左右子树*/RootFirstTrav(root->left);RootFirstTrav(root->right);}/*主函数调用测试*/intmain(){node_ps;s=CreatExTree();RootFirstTrav(s);return0;}递归调用看起来并没什么难点，接下来就看看非递归调用的style：在给出代码之前，先分析一下我们的循环。为了再访问完左子树后，还

5、能倒回去访问右子树，我们不得不保存当前的节点。这里用到一个叫做堆栈的数据结构，当然这里我们用数组模拟它。定义一个数组：#defineMAX_NODE100Node_pstac[MAX_NODE]={0};Inttopele=-1//定义一个索引下标过程描述：我们遇到第一个根节点，处理，保存第一个节点数组情况为A00000topele=0;我们访问A的左子树，不为空，处理，入栈AB0000topele=1再继续访问左子树，不为空，处理，入栈ABD000topele=2再继续访问左子树，为空，出栈，取出栈顶元素B；AB0000topele=0处理B的右子树E，E的左子树不为空，不入栈，处

6、理右子树，为空，不入栈。再出栈，取元素A，处理A的右子树C，C的左子树不为空，入栈，处理C。然后，处理C的左子树F，F的左右子树为空，去栈顶元素C，处理C的右子树，在取栈顶元素，栈为空，遍历结束。代码描述：voidRootFirstTrav_(node_proot){node_pstac[MAX_NODE];inttopele=-1;if(root==NULL)exit(1);node_pp1;p1=root;//循环出口，堆栈为空while(p1!=NULL

7、

8、topele!=-1){while(p1!=NULL){/*处理数据*/printf("%c",p1->val);stac

9、[++topele]=p1;p1=p1->left;}if(topele!=-1){p1=stac[topele--]->right;}}}中根（序）遍历递归比较简单就直接上递归的代码了voidRootSecondTrav(node_proot){if(root==NULL)return;RootSecondTrav(root->left);printf("%c",root->val);RootSecondTrav(root->right);}非递归调用与