当前位置:
文档之家› 数据结构(第二版) 第六章 答案
数据结构(第二版) 第六章 答案
else if (i<=r) printf("%c",bt->data); else printf("not parent");
}
2.设计判断两个二叉树是否相同的算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
void level(bitree *bt,int x)
{
if (bt!=0)
{lev++; if (bt->key==x) return;
else if (bt->key>x) level(bt->lchild,x);
else level(bt->rchild,x);
}
}
}
3.设计计算二叉树中所有结点值之和的算法。
void sum(bitree *bt,int &s)
{
if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);}
}
4.设计求二叉树中值为x的结点所在的层号的算法。
int lev=0;
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
11、哈夫曼树
12、4 16
13、0
14、
165
15、63
16、6
三综合应用题
1ቤተ መጻሕፍቲ ባይዱ
(1)根节点:A叶子节点:C E F H I J K M N非终端节点:A B D G L
(2)深度:5
各节点层数A:1;B、C、D:2;E、F、G、H、I、J:3;K、L、M:4;N:5
(3)双亲:D祖先:A D孩子:K L M子孙:K L M N兄弟:H I J堂兄弟:E F
}
void parent(bitree *bt,char x)
{
int i;
preorder(bt,x);
for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break;
if (flag==0) printf("not found x\n");
int judgebitree(bitree *bt1,bitree *bt2)
{
if (bt1==0 && bt2==0) return(1);
else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0);
else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));
第6章树答案
一选择题
1-5 ABBDC
6-10 CACBD
11-15 BCADB
16-20 BAAAA
21-22 CA
二填空题
1、n2+1
2、3 7
3、单分支
4、完全二叉树
5、127 64
6、31
7、2 +1 2 -1
8、1多
9、129
10、P->lchild==null&&p->rchild==null
(2)哈夫曼树为:
(3)哈弗曼编码:
a:1110 b:1111 c:110 d:00 e:01 f:10
(4)长度:244
四、算法设计题
1.设计一个求结点x在二叉树中的双亲结点的算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
bitree *q[20]; int r=0,f=0,flag=0;
void preorder(bitree *bt, char x)
{
if (bt!=0 && flag==0)
if (bt->data==x) { flag=1; return;}
else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); }
2先序遍历:ABCDEFGHIJ
中序遍历:BCDAFEHJIG
后序遍历:DCBFJIHGEA
3对应的二叉树
后序遍历为:bdeca
4
5
6
带权路径长度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131
树的结点总数13
7 (1)哈夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。