数据结构部分习题参考答案.ppt

练习题7 　　　7.1、7.2、7.3、7.4、7.5、7.7、7.9 7.1 设二叉树bt的一种存储结构如表7.1所示。其中，bt为树根节点指针，lchild、rchild分别为节点的左、右孩子指针域，在这里使用节点编号作为指针域值，0表示指针域值为空；data为节点的数据域。请完成下列各题： （1）画出二叉树bt的树形表示； （2）写出按先序、中序和后序遍历二叉树bt所得到的节点序列； （3）画出二叉树bt的后序线索树。 表7.1 二叉树bt的一种存储结构 1 2 3 4 5 6 7 8 9 10 lchild 0 0 2 3 7 5 8 0 10 1 data j h f d b a c e g i rchild 0 0 0 9 4 0 0 0 0 0 答：（1）二叉树bt的树形表示如图7.1所示。 图7.1 二叉树bt的逻辑结构 图7.2 二叉树bt的后序线索化树 （2）先序遍历序列：abcedfhgij 中序遍历序列：ecbhfdjiga 后序遍历序列：echfjigdba （3）二叉树bt的后序遍历序列为echfjigdba，则后序线索树如图7.2所示。 7.2 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出该二叉树树形表示。 7.3 设给定权集合W={2,3,4,7,8,9}，试构造关于W的一棵哈夫曼树，并求其带权路径长度WPL。 答：由权值集合W极选的哈夫曼树如图7.4所示。其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。 7.4 一棵具有n个节点的完全二叉树以顺序方式存储在数组A中，假设每个节点的元素为单个字符，没有对应节点时A中元素取值为#。设计一个算法构造该二叉树的二叉链存储结构。 void Ctree(BTNode *b,char A[],int i) { //由二叉树的顺序存储结构A建立二叉链存储结构，二叉链的根节点由b指向 if (i=MaxSize || A[i]==#) //若i无效或A[i]为无效节点 b=NULL; else { b=(BTNode *)malloc(sizeof(BTNode)); b-data=A[i-1]; Ctree(b-lchild,A,2*i); //递归构造*b的左子树 Ctree(b-rchild,A,2*i+1); //递归构造*b的右子树 } } 7.5 假设二叉树中每个节点的值为单个字符，设计一个算法将一棵以二叉链方式存储的二叉树b转换成对应的顺序存储结构A。 void Ctree(BTNode *b,SqBTree A,int i) { if (b!=NULL) { A[i]=b-data; Ctree(b-lchild,A,2*i); Ctree(b-rchild,A,2*i+1); } else A[i]=#; } 7.7 假设二叉树采用二叉链存储结构，t指向根节点，p所指节点为任一给定的节点，设计一个算法，输出从根节点到p所指节点之间路径。 int Path(BTNode *t,BTNode *s) { BTNode *St[MaxSize]; BTNode *p; int i,flag,top=-1; //栈顶指针置初值 do { while (t) //将t的所有左节点进栈 { top++; St[top]=t; t=t-lchild; } p=NULL; //p指向当前节点的前一个已访问的节点 flag=1; //设置t的访问标记为已访问过 while (top!=-1 flag) { t=St[top]; //取出当前的栈顶元素 if (t-rchild==p) //右子树不存在或已被访问,访问之 { if (t==s) //当前访问的节点为要找的节点,输出路径 { for (i=0;i=top;i++) printf(%c ,St[i]-data); return 1; } else { top--; p=t; //p指向则被访问的结 } } else { t=t-rchild; //t指向右子树 flag=0; //设置未被访问的标记 } }