TA：于波 计算机科学工程系 上海交通大学 December 5, 2009 数据结构习题课二 树和查找 TA：于波 计算机科学工程系 上海交通大学 December 5, 2009

二叉树的性质 1. 一棵非空的二叉树的第i层上最多有 个结点。 证明见教材 Page 93页。

二叉树的性质 2. 一棵高度为 k 的二叉树最多具有 个结点。 证明见教材 Page 93页。

二叉树的性质 3. 对于一棵非空的二叉树如果叶子结点 数为 ，度数为2的结点数为 ，则 有 成立。 证明见教材 Page 93页。 3. 对于一棵非空的二叉树如果叶子结点 数为 ，度数为2的结点数为 ，则 有 成立。 证明见教材 Page 93页。 对结点： n=n0+n1+n2; 对边： n-1=0*n0+1*n1+2*n2

二叉树的性质 4. 具有n个结点的完全二叉树高度 为 。 证明见教材 Page 94页。 注意： 树的深度 + 1 == 树的高度

基础知识题 1. 若一个具有N个顶点，K条边的无向图 是一个森林（N>K），求该森林中有多少 棵树。

基础知识题 解答: 因为一棵具有n个顶个的树有n-1条 边，因此设此森林中有m棵树，每棵树具 有的定点数为 vi （1<= i <=m） v1+v2+…+vm=N; (v1-1)+(v2-1)+…+(vm-1)=K; => m=N-K

基础知识题 2. 已知一棵度为m的树中有N1个度为1的 结点，N2个度为2的结点，….，Nm个度 为m的结点。试问该树中有多少个叶子结 点？

基础知识题 解答: 关键在于树的结点个数与边的条数 联系起来 总的结点个数-1 = 边数 => ….

基础知识题 3. 将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉 树

基础知识题 * + + g h + f + * + a b c d e

基础知识题 4. 任意一个有n个结点的二叉树，一直它 有m个叶子结点，试证明非叶子结点有 m-1个度为2，其余的度为1.

基础知识题 解答: 关键在于树的结点个数与边的条数 联系起来 n=n1+n2+m n-1=1*n1+2*n2 => n2=m-1

基础知识题 5. 有n个结点的二叉树，已知叶子结点的 个数为n0，写出求度数为1的结点个数n1 的计算公式；若此树是高度为k的完全二 叉树，写出n为最小的公式；若二叉树中 仅有度为0和度为2的结点，写出求该二 叉树结点个数n的公式。

基础知识题 解答: 记度为2的结点个数为n2 当树是高度为k的完全二叉树， n=n0+n1+n2 n-1=1*n1+2*n2; => n1=n+1-2n0 当树是高度为k的完全二叉树， 完全二叉树，最小，那就是高度为k-1的满二叉树加1个结点。 仅有度为0和2，n=n0+n2,n-1=2*n2 => n=2*n0 -1

基础知识题 6. 设高为h的二叉树只有度为0和2的结点， 则此类二叉树的结点数至少为____, 至多 为______.

基础知识题 解答: 最少的情形 最多的情形 高度为h-1的满二叉树 高度为h的满二叉树

基础知识题 7. 深度为 k-1 的完全二叉树至少有____ 个结点，至多有_____个结点，k和结点 数n之间的关系为______.

基础知识题 解答: 深度为 k-1 的完全二叉树至少有 个 结点，至多有 个结点，k和结点数 n之间的关系为 . 高为h-1满二叉树+1结点 二叉树性质四

基础知识题 8. 回答问题写出推导过程: 含N个结点和N个叶子结点的完全三叉树 的高度是多少？

基础知识题 解答: 含N个结点的完全三叉树的高度设为H

基础知识题 解答: 2. 含N个叶子结点的完全三叉树的高度 设为H H为 a. N为3的幂： 或 b. 其他：

基础知识题 9. 用一维数组存放的一棵完全二叉树如 下： A B C D E F G H I J K L 写出后序遍历二叉树时访问结点的顺序

基础知识题 解答: 画树出解 H I D J K E B L F G C A

基础知识题 10. 有二叉树中序序列为：ABCEFGHD 后序序列为：ABFHGEDC 画出此二叉树

基础知识题 解答: C B D A E G F H

基础知识题 11. 已知二叉树各结点的先序、中序遍历 分别为ABCDEF和CBAEDF，画出该二叉 树。

基础知识题 解答: A B D C E F

基础知识题 12. 若一棵二叉树，左右子树均有三个结 点，其左子树的前序序列与中序序列相同， 右子树的中序序列与后序序列相同，试图 构造树。

基础知识题 解答: 左子树前序与中序相同 前序：根 左 右 中序：左 根 右 同理右子树中序与后序 后序：左 右 根

基础知识题 13. 已知二叉树左右子树均含有3个结点， 试图构造满足下面条件的二叉树 （1）左右子树先序与中序相同 （2）左子树中序与后序，右子树先序与 中序相同

基础知识题 解答:

基础知识题 14. 对于前序遍历和中序遍历结果相同的 二叉树为______;对于前序遍历和后序遍 历结果相同的二叉树为______。

基础知识题 解答: 对于前序遍历和中序遍历结果相同的二叉 树为 ;对 于前序遍历和后序遍历结果相同的二叉树 为 。 对于前序遍历和中序遍历结果相同的二叉 树为 ;对 于前序遍历和后序遍历结果相同的二叉树 为 。 所有节点只有右子树的二叉树 只有根结点的二叉树

基础知识题 15. 假设一个二叉树的层次序列为 ABCDEFGHIJ，中序序列DBGEHJACIF。 画出这棵二叉树。

基础知识题 解答:蓝色左子树，下划线右子树 ABCDEFGHIJ DBGEHJACIF BCDEFGHIJ DBGEHJ CDEFGHIJ CIF DEFGHIJ D EFGHIJ GEHJ FGHIJ IF GHIJ G HIJ HJ IJ I J J

基础知识题 构造树的过程： A A A A B B C B C D A A A B C B C B C D E D E F D E F G

基础知识题 A A A B C B C B C D E F D E F D E F G G H A G H I B C D E F G H J

基础知识题 16. 已知某字符串S中共有8种字符，各种 字符分别出现2次、1次、4次、5次、7次、 3次、4次、9次，对该字符串用{0，1}进 行前缀编码，问该字符串编码至少有多少 位？

基础知识题 解答: 至少需要 5*1+5*2+4*3+3*4+3*4+3*5+9*2+7*2= 98位 1 2 3 3 5 6 4 4 11 解答: 至少需要 5*1+5*2+4*3+3*4+3*4+3*5+9*2+7*2= 98位 1 2 3 3 5 6 4 4 11 9 7 8 20 15 35

基础知识题 17. 假设二叉树采用链表存储方式存储， 编写一个后序遍历二叉树的非递归算法。

基础知识题 解答: void postorder(Bitree *root) { Bitree *stack[max],*p; int tag[max],top; top=0; p=root; do{ //扫描左孩子 while(p!=NULL){ top++; stack[top]=p; tag[top]=0; //有孩子还未访问过标志 p=p->child; } if(top>0){ if(tag[top]==1){ //左右孩子结点均已访问过，则访问该结点 printf(“%c”,stack[top]->data); top--; else{ p=stack[top]; p=p->rchild; //扫描右孩子 tag[top]=1; //置当前结点的右孩子已//访问过标志 }while((p!=NULL) || (top!=0));

基础知识题 18. 设计算法，统计一个二叉树中所有叶 子结点的数目（递归与非递归）

基础知识题 解答: a. 递归，先序遍历 void countleaf(Bitree *t,int *count) { if(t!=NULL){ if((t->lchild==NULL) && (t->rchild==NULL)) count++;//结点是叶子,计数目加1 countleaf(t->lchild,count);//累计左子树上叶 //子结点树 countleaf(t->rchild,count);//右子树的 }

基础知识题 解答: b. 非递归 int countleaf ( Bitree *root) { int m; Seqstack *s; if(t!=NULL){ top=0; s->data[s->top]=t; do{ t=s->data[s->top]; s->top--; //退栈 if((t->lchild==NULL) && (t->rchild==NULL)) m++;//叶子结点,计数加一 else{ if(t->lchild != NULL){//左孩子进栈 s->top++; s->data[s->top]=t->lchild; } if(t->rchild != NULL){//右孩子进栈 s->data[s->top]=t->rchild; }while(top!=-1)//栈空是结束 return m;

基础知识题 19. 设计算法，将一个二叉树中每个结点 的左右孩子交换的算法（递归与非递归）

基础知识题 解答: a. 递归，先序遍历 void swap(Bitree *b) { Bitee *t; if(b == NULL) return; else{ t=b->lchild; b->lchild=b->rchild; b->rchild=t; swap(b->lchild); swap(b->rchild); }

基础知识题 解答: b. 非递归 void swap ( Bitree *root) { int top; Bitree *temp,*stack[max]; if(root != NULL){ top=1; stack[top]=root;//根结点进栈 } do{ root=stack[top]; //弹出栈顶结点 top--; //退栈 if((root->lchild != NULL) || (root->rchild != NULL)){//左右指针交换 temp=root->lchild; root->lchild=root->rchild; root->rchild=temp; if(root->lchild != NULL){//交换后左指针入栈 top++; stack[top]=root->lchild; if(root->rchild != NULL){//交换后右指针入栈 stack[top]=root->rchild; }while(top != 0);

基础知识题 20. 标示二叉树中各结点的值，各结点的 值依次为32~40.

基础知识题 解答: 36 32 40 35 37 33 38 34 39

基础知识题 21. 已知序列17，31，13，11，20，35， 25，8，4，11，24，40，27，请画出该 序列的二叉排序树，并分别给出下列操作 后的二叉树： 1) 插入数据9； 2) 删除结点17; 3) 再删除结点13;

基础知识题 解答: 17 13 31 11 20 35 8 25 40 4 24 27

基础知识题 插入9 17 13 31 11 20 35 8 25 40 4 9 24 27

基础知识题 插入17 13 11 31 8 20 35 4 9 25 40 24 27

基础知识题 插入13 11 8 31 4 9 20 35 25 40 24 27

基础知识题 22. 设K1，K2，K3是三个不同的关键字， K1>K2>K3，请画出按不同输入顺序简历 的二叉排序树

基础知识题 解答: K1 K1 K2 K3 K1 K3 K1 K3 K2 K1 K2 K2 K3 K3 K2 K1K2K3 K1K3K2

基础知识题 23. 哈希地址范围[0,9]，哈希函数为 H(hey)=(key*key+2) MOD 9,采用链地 址法处理冲突，画出元素7,4,5,3,6,2,8,9 依次插入后的状态。

基础知识题 解答: 4 5 ^ 1 2 3 6 9 ^ 3 8 ^ 4 5 6 7 2 ^ 7 8 9

二叉树的构建唯一性证明 （1）前序+中序 可以唯一确定一棵二叉树 （2）后序+中序 可以唯一确定一棵二叉树 （3）前序+后序 不能唯一确定一棵二叉树 用归纳法证明(1), 定理(2)同理可证。 (1)n=1时候只有一个根节点显然成立 (2)假设n<k时成立，则n=k时，假设前序为P1, P2 , P3 , …, Pk-1 , Pk,中序为Q1 , Q2 , Q3 ,… Qj… Qk-1 ,Qk P1显然为根，我们假设P1 = Qj ,则[Q1,Qj-1]为P1的左子树， [Qj+1,Qk]为P1的右子树，同样我们推出[P2,Pj]为P1的左子树， [Pj+1,Pk]为P1的右子树。 根据假设我们知道[Q1,Qj-1]和[P2,Pj]可以唯一确定一棵二叉 树， [Qj+1,Qk]和[Pj+1,Pk]可以唯一确定一棵二叉树。所以n=k也 成立得证。

二叉树的构建唯一性证明 （1）前序+中序 可以唯一确定一棵二叉树 （2）后序+中序 可以唯一确定一棵二叉树 （3）前序+后序 不能唯一确定一棵二叉树 反例： A A B B

结束 谢谢大家 ！