练习题6.doc

3. 简答题（1）一棵度为2的树与一棵二叉树有何区别？答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的，即在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。另外，一棵度为2的树至少有3个结点，而一棵二叉树的结点个数可以为0。（2）试求含有n0个叶子结点的完全二叉树的总结点数。答：由二叉树的性质可知，n2=n0-1，在完全二叉树中，度为1的结点数n1至多为1，所以具有n0个叶子结点的完全二叉树结点数是n0+(n0-1)+1=2n0或2n0-1。（3）某二叉树的结点数据采用顺序存储结构如下：1234567891011121314151617181920EAF#D#H#C#GI#B 画出该二叉树； 写出结点值为D的双亲结点及左、右子树。 将此二叉树还原为森林。答： 该二叉树如图8.21所示。 图8.21 一棵二叉树 图8.2 二叉树还原成的森林 结点值为D的结点的双亲结点为结点值为A的结点，其左子树为以C为根结点的子树，其右子树为空。 由此二叉树还原成的森林如图8.2所示。（4）证明完全二叉树的每棵子树也都是完全二叉树。证明：让T是一棵完全二叉树，S是它的一棵子树。由子树定义可知，S是由T中某个结点及其所有子孙构成的。由于T是完全二叉树，T的所有叶子结点都在两个相邻的层次上，因此，S的所有叶子结点都在两个相邻的层次上。类似的，如果在S中存在不位于底层上结点层，那么，该层也不位于T的底层上，它必须在T中所有底层叶子结点的右边，因此它也必须在S中所有底层叶子结点的右边。从而得到S是完全二叉树。（5）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A答：由这些显示部分推出二叉树如图8.3所示。则先序序列为ABDFKICEHJG；中序序列为DBKFIAHEJCG；后序序列为DKIFBHJEGCA。图8.3 一棵二叉树（6）如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1可知，n0=n2+1，即n2=n0-1，则总结点数n=n0+n2=2n0-1。4. 算法设计题（1）已知一棵二叉树按顺序方式存储在数组A1.n中。设计一个算法求出离下标分别为i和j（0q) p=p/2;else q=q/2;return Ap;（2）已知一棵二叉树采用顺序方式存储在数组A1.n中。设计一个先序遍历的递归算法。解：先序遍历树中结点的递归算法如下：void PreOrder1(ElemType A,int i,int n)if (idata只有一个结点时f(bt)=Maxf(bt-lchild),f(bt-rchild),bt-data 其他情况对应的算法如下：ElemType MaxNode(BTNode *bt)ElemType max,max1,max2;if (bt-lchild=NULL & bt-rchild=NUL)return bt-data;elsemax1=MaxNode(bt-lchild);/求左子树的最大结点值max2=MaxNode(bt-rchild);/求右子树的最大结点值max=bt-data;if (max1max) max=max1;if (max2max) max=max2;/求最大值return(max);/返回最大值（4）假设含有n个结点的二叉树采用二叉链存储结构。设计一个算法输出中序遍历序列中的第k（1in）个结点值。解：对应的算法如下：int i=0;/i为全局变量void Trav(BTNode *bt,int k)if (bt!=NULL)Trav(bt-lchild,k);/遍历左子树i+;if (i=k)printf(%c,bt-data);return;Trav(bt-rchild,k);/遍历右子树（5）假设二叉树采用二叉链存储结构，设计一个算法Level()求二叉树中结点值为x的结点的层数。解：对应的递归算法如下：int Level(BTNode *bt,ElemType x,int h)/调用h对应的实参置初值1int l;if (bt=NULL)return 0;else if (bt-data=x)return h;elsel=Level(bt-lchild,x,h+1);/在左子树中查找if (l!=0)return l;else/在左子树中未找到,再在右子树中查找return(Level(bt-rchild,x,h+1);上机实验题6假设一棵二叉树采用二叉链存储结构，其中所有结点值均不相同。设计一个算法求从根结点到值为x的结点的路径。并用相关数据进行测试。解：采用递归和层次遍历两种求解方法，对应的程序如下：#include #include BTree.hvoid Path1(BTNode *bt,ElemType x,ElemType path,int pathlen)int i;if (bt!=NULL)if (bt-data=x)/找到值为x的结点printf(从根结点到%c结点的路径: ,bt-data);for (i=0;idata);return;elsepathpathlen=bt-data;/将当前结点放入路径中pathlen+;/path中元素个数增1Path1(bt-lchild,x,path,pathlen);/递归遍历左子树Path1(bt-rchild,x,path,pathlen);/递归遍历右子树void Path2(BTNode *bt,ElemType x)BTNode *p;ElemType pathMaxSize;int i,d;struct BTNode *s;/存放结点指针int parent;/存放其双亲结点在qu中的下标 quMaxSize;/qu存放队中元素int front=-1,rear=-1;/队头队尾指针rear+;qurear.s=bt;/根结点进队qurear.parent=-1;/根结点没有双亲,其parent置为-1while (front!=rear)/队不空循环front+;p=qufront.s;/出队一个结点*p,它在qu中的下标为frontif (p-data=x)/找到值为x的结点printf(从根结点到%c结点的路径: ,p-data);d=0; pathd=p-data;i=qufront.parent;while (i!=-1)d+; pathd=qui.s-data;i=qui.parent;printf(%c,pathd);for (i=d-1;i=0;i-)printf(%c,pathi);printf(n);if (p-lchild!=NULL)/*p有左孩子,将左孩子进队rear+;qurear.s=p-lchild;qurear.parent=front;/左孩子的双亲为qufront结点if (p-rchild!=NULL)/*p有右孩子,将右孩子进队rear+;qurear.s=p-rchild;qurear.parent=front;/右孩子的双亲为qufront结点void main()BTNode *bt;ElemType pat