课件数据结构第六章作业.doc

《课件数据结构第六章作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.6叶结点个数为6.7最大深度h=N-k+1；最小深度为:logkN+16.8归纳法证明，设满k叉树深度为L，则当L=1时，n0=1，n1=0，则n01=(k-1)n11+1成立假定L=m时结论成立，即n0m=(k-1)n1m+1则当L=m+1=M时，n1M=n1m+n0m=n1m+(k-1)n1m+1=kn1m+1所以n1m=(n1M-1)/kn0M=kn0m=k((k-1)n1m+1)=k((k-1)((n1M-1)/k)+1)=(k-1)((n1M-1)+k=(k-1)n1M+1,结论成立6.9H=（上取整）H=（上取整）6.

2、101）2n-12）采用数学归纳法，设树的高度为L当L=1时，树中只有根节点，结论成立假定L=k时，结论成立则当L=k+1时，k+1层上的每一对叶结点由原来k层上一个叶结点演化而来，由于，也就是说，放到要证明的公式里新增加的两项的和刚好是原来减少的值，所也结论成立。6.13前序n在m之前中序n在m之前后序n在m之前n在m左方Φ代表不确定1代表肯定Φ代表不确定n在m左方Φ代表不确定0代表恰恰相反Φ代表不确定n在m右方1代表肯定Φ代表不确定0代表恰恰相反n在m右方0代表恰恰相反Φ代表不确定1代表肯定6.17修改程序中的错误If(!r->r

3、tag)→If(!q->rtag)While(!r->rtag)r=r->rchild;→While(!r->ltag)r=r->lchild;6.20对应的二叉树为：前序前驱线索化：中序全线索化：后序后继线索化：6.24对应二叉树的先序序列为：ABCDEFGHIJKL对应二叉树的中序序列为：CBEFDGAJIKLH所以对应的二叉树为：所以对应的森林为：6.37先序遍历非递归算法voidPreOrderUnrec(Bitree*t){Stacks;StackInit(s);Bitree*p=t;while(p!=NULL

4、

5、!Stac

6、kEmpty(s)){while(p!=NULL)//遍历左子树{visite(p->data);push(s,p);p=p->lchild;}if(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}6.42intf(treeT){if(!T)return(0);else{if(T-lchild==0)&&(T->rchild==0)return(1);elsereturn(f(T-lchild)+f(T->rchild)

7、);}}6.43voidf(treeT){if(T){T->lchild←→T->rchild;f(T-lchild);f(T->rchild);}}6.55intf(treeT){if(!T)return(0);else{T->DescNum=f(T-lchild)+f(T->rchild);return(T->DescNum+1);}}6.62intf(treeT){if(!T)return(0);else{h1=f(T-lchild);h2=f(T->rchild);if(h2>h1+1)return(h2);elseretur

8、n(h1+1);}}6.69voidf(TreeT,inti)//i表示结点所在层次,初次调用时i=0{  if(T->rchild)f(T->rchild,i+1);  for(j=1;j<=i;j++)printf("");  printf("%c",T->data);  if(T->lchild)f(T->rchild,i+1);}