数据结构考研分类复习真题 第六章 答案 (五)[16]

[题目分析] 本题使用的存储结构是一种双亲表示法对每个结点直接给出其双亲（的下标）而且用正或负表示该结点是双亲的右子女或左子女该类结构不适于直接进行前序遍历（即若直接前序遍历算法要很复杂）较好的办法是将这类结构转为结点及其左右子女的顺序存储结构即

Tree=ARRAY[max] OF RECORD data: char; //结点数据

lcrc: integer; END;//结点的左右子女在数组中的下标

void Change (Tree t Tree bt int *root) //先将t转为如上定义类型的变量bt;

{for(i=;i<=max;i++) {bt[i]lc=bt[i]rc=;} //先将结点的左右子女初始化为

for(i=;i<=max;i++) //填入结点数据和结点左右子女的信息

{bt[i]data=t[i]data;

if(t[i]parent<) bt[t[i]parent]lc=i; //左子女

else if(t[i]parent>) bt[t[i]parent]rc=i; //右子女

else *root=i; //root记住根结点

} }//change

void PreOrder(Tree bt) //对二叉树进行前序遍历

{int *roottop=; int s[]; //s是栈

change(tbtroot); int i=*root;

while(i!=||top>)

{while (i!=)

{printf (bt[i]data)if(bt[i]rc!=) s[++top]=bt[i]rc; //右子女进栈

i=bt[i]lc;

}

if (top>) i=s[top];

} }//结束preorder

[算法讨论]本题的前序递归算法如下

void PreOrder(int root)//root是二叉树根结点在顺序存储中的下标本算法前序遍历二叉树bt

{if(root!=){printf(bt[root]data);//访问根结点

PreOrder(bt[root]lc);//前序遍历左子树

PreOrder(bt[root]rc);//前序遍历右子树

} }//结束preorder初始调用时root是根结点的下标

这类问题的求解方法值得注意当给定数据存储结构不合适时可由已给结构来构造好的数据结构以便于运算象上面第题也是这样先根据L和R数组构造一个结点的双亲的数组T

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []