二叉树的遍历学习心得VIP专享VIP免费

二叉树的遍历学习心得二叉树的非递归遍历学习心得对于学习数据结构的新手来说，二叉树应该是遇到的一个比较大的难题。对于二叉树的遍历，如果使用递归的方法，代码非常简单，但是有些程序语言不支持递归，而且递归的执行效率偏低，使许多程序设计人员望而却步下面我将与大家分享我在学习二叉树的非递归遍历的过程中遇到的困惑与解答，以供学习和交流。鉴于有些数据结构资料中没有介绍树的结点的栈的结点的构造，首先向大家介绍结点的构造。typedefstructbitnode{chardata;\树的结点的数据域（以字符型数据为\树的结点的结构例）structbitnode*lchild，*rchild;\树的子树指针}bitnode，*bittree;typedefstructnode{bitnodestack;\栈的数据域类型为树的结点\栈的结点结构structnode*next;}linkstack;遍历的前提当然是二叉树存在，下面为大家介绍树的建立。bittreecreat_bittree{bittreebt;\树的根结点charx;scanf（"%c"，x）;\树的建立的子函数类型为树的指针类型}if（x=='X'）bt=null;else{}returnbt;\如果输入为’X’，则返回空结点bt=（bittree）malloc（sizeof（bitnode））;\若输入有效，则申请结点空间bt->data=x;\装填结点\插入左子树\插入右子树bt->lchild=creat_bittree;bt->rchild=creat_bittree;第1页共5页建立二叉树的过程使用了递归，如果理解不了，可以自己画图助于理解，建立决定了二叉树的形状，一定要弄清楚。如所要建立的二叉树的形状为那么输入应该为abdXXeg。接下来是栈的一些操作，因为任何一本数据结构的资料都会在栈和队列的章节说得很清楚，下面只是做了一些比较小的改动，请读者自行体会。intinit_stack（linkstack**s）{}intpush_stack（linkstack*s，bitnode*x）*s=（linkstack*）malloc（sizeof（linkstack））;（*s）->next=null;return1;{}intpop_stack（linkstack*s，bitnode*e）{return0;}}intempty_stack（linkstack*s）{}if（s->next==null）return1;return0;linkstack*p;if（empty_stack（s））{printf（"stackisnull\n"）;p=s->next;s->next=p->next;*e=p->stack;free（p）;return1;linkstack*p;p=（linkstack*）malloc（sizeof（linkstack））;p->stack=*x;p->next=s->next;s->next=p;return1;先介绍先序遍历的算法，先建立根结点，再建立左子树再到右子树，遍历是相对于每一棵子树来说的，这一点要格外注意。最重要的是要在脑海里建立模型，在后面的后序遍历中尤显模型的重要性。voidpre_order（bittreet）{}以下是主函数。intmain{bittreet;printf（"\n\t********************欢迎来到二叉linkstack*s;bittreep;p=t;init_stack（s）;push_stack（s，p）;while（。empty_s第2页共5页tack（s））{pop_stack（s，p）;printf（"\t[%c]"，p->data）;if（p->rchild）push_stack（s，p->rchild）;if（p->lchild）push_stack（s，p->lchild）;}树世界********************\n"）;printf（"\n\t请输入二叉树结点，"X"为空树\n\t"）;t=creat_bittree;printf（"\n"）;printf（"\t先序遍历二叉树如下："）;printf（"\n"）;}pre_order（t）;printf（"\n\t"）;getch;以下是二叉树的中序遍历的算法，先从左子树入栈到底，然后访问栈顶元素，同时栈顶出栈，再检测是否存在右子树，如果存在，从它的右子树的左子树入栈到底，如果不存在，访问栈顶元素，同时栈顶出栈，如此循环，直到栈空。voidin_order（bittreet）{}linkstack*s;bittreep，q;q=（bittree）malloc（sizeof（bitnode））;p=t;init_stack（s）;while（p||。empty_stack（s））{if（p）{}else{}}pop_stack（s，q）;printf（"\t[%c]"，q->data）;p=q->rchild;push_stack（s，p）;p=p->lchild;二叉树的遍历中要数后序遍历最为复杂，它的栈的构造与前面两种遍历方法有所不同，在栈里加了一个标记元素rvisited用来标记其结点的右子树是否被访问过，由此来达到最后才访问根结点的效果。由于程序比较复杂，下面为大家一步步分析。typedefstructnode{}linkstack;intpush_stack（linkstack*s，bitnode*x）{第3页共5页}voidpost_order（bittreet）{bittreep，q;linkstack*s，*top;init_stack（s）;p=t;q=（b...