2. 自考
  3. 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

admin2010-04-24  106
问题 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。
选项
答案要解答该题必须分析结点所在的状态，这可以通过结点的标志域来进行。对一个结点来说，当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历结束转换；(3)其右子树遍历结束转换。所以算法主要执行按这三种状态进行处理或处理当前结点切换结点的状态。从而可将算法描述为： void postorder(r)/*后序遍历此二叉树*/ bitree*t/*设为bitree类型的结点含四个域：flag，parent，lchild，rehild，其中flag的域初值为0，指针t指向根结点*/ { bitree * P; P=t; while(p!=Null) switch(—＞flag) { case 0:p—＞flag=1; if(p—＞lchild!=Null) p=p—＞lehild; break; case 1:p—＞flag=2 if(jp—＞rchild!=Null) p=p—＞rchild; break; case 2:p—＞flag=0; printf(p—＞data); p=jp—＞parent; break; default; } } /*postorder*/
解析
转载请注明原文地址:https://kaotiyun.com/show/CrAx777K
本试题收录于： 数据结构题库理工类分类
0

数据结构

理工类

相关试题推荐
随机试题
最新回复(0)