4、〕對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)場(chǎng)進(jìn)展連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用〔〕遍歷實(shí)現(xiàn)編號(hào)。
A．先序 B. 中序 C. 后序 D. 從根開(kāi)場(chǎng)按層次遍歷
答案：C
解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹(shù)，即后序遍歷二叉樹(shù)。
〔8〕假設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)構(gòu)造，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利用〔〕遍歷方法最適宜。
A．前序B．中序C．后序 D．按層次
答案：C
解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹(shù)的交換，不過(guò)層次遍歷的實(shí)現(xiàn)消耗比后續(xù)
5、大，后序遍歷方法最適宜。
〔9〕在以下存儲(chǔ)形式中，〔〕不是樹(shù)的存儲(chǔ)形式
A．雙親表示法 B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法
答案：D
解釋：樹(shù)的存儲(chǔ)構(gòu)造有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹(shù)都能通過(guò)孩子兄弟表示法轉(zhuǎn)換為二叉樹(shù)進(jìn)展存儲(chǔ)。
〔10〕一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足〔〕。
A．所有的結(jié)點(diǎn)均無(wú)左孩子 B．所有的結(jié)點(diǎn)均無(wú)右孩子
C．只有一個(gè)葉子結(jié)點(diǎn) D．是任意一棵二叉樹(shù)
答案：C
解釋：因?yàn)橄刃虮闅v結(jié)果是“中左右〞，后序遍歷結(jié)果是“左右中〞，當(dāng)
6、沒(méi)有左子樹(shù)時(shí)，就是“中右〞和“右中〞；當(dāng)沒(méi)有右子樹(shù)時(shí)，就是“中左〞和“左中〞。則所有的結(jié)點(diǎn)均無(wú)左孩子或所有的結(jié)點(diǎn)均無(wú)右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無(wú)左孩子與所有的結(jié)點(diǎn)均無(wú)右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，應(yīng)選C。
〔11〕設(shè)哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有〔 〕個(gè)葉子結(jié)點(diǎn)。
A．99B．100
C．101D．102
答案：B
解釋：在哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，只有度為0〔葉子結(jié)點(diǎn)〕和度為2的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹(shù)的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n= n0+n2=2*n0-1，得到n0=100。
〔12〕假設(shè)X是二
7、叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為〔〕。
A．X的雙親B．X的右子樹(shù)中最左的結(jié)點(diǎn)
C．X的左子樹(shù)中最右結(jié)點(diǎn) D．X的左子樹(shù)中最右葉結(jié)點(diǎn)
答案：C
〔13〕引入二叉線索樹(shù)的目的是〔〕。
A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B．為了能在二叉樹(shù)中方便的進(jìn)展插入與刪除
C．為了能方便的找到雙親 D．使二叉樹(shù)的遍歷結(jié)果唯一
答案：A
〔14〕設(shè)F是一個(gè)森林，B是由F變換得的二叉樹(shù)。假設(shè)F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有〔 〕個(gè)。
A．n?1 B．n C．n + 1 D．n + 2
答案：C
〔15〕n〔n≥2〕個(gè)權(quán)值均不一樣的
8、字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的表達(dá)中，錯(cuò)誤的選項(xiàng)是〔?〕。
A．該樹(shù)一定是一棵完全二叉樹(shù)
B．樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)
C．樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)
D．樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值
答案：A
解釋：哈夫曼樹(shù)的構(gòu)造過(guò)程是每次都選取權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，所以樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。
2．應(yīng)用題
〔1〕試找出滿足以下條件的二叉樹(shù)
① 先序序列與后序序列一樣②中序序列與后序序列一樣
③ 先序序列與中序序列一樣④中序序列與層次遍歷序列一樣
9、答案：先序遍歷二叉樹(shù)的順序是“根—左子樹(shù)—右子樹(shù)〞，中序遍歷“左子樹(shù)—根—右子樹(shù)〞，后序遍歷順序是：“左子樹(shù)—右子樹(shù)―根＂，根據(jù)以上原則有
①或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù)
②或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù)．
③或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)．
④或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)
〔2〕設(shè)一棵二叉樹(shù)的先序序列： A B D F C E G H ，中序序列： B F D A G E H C
①畫出這棵二叉樹(shù)。
②畫出這棵二叉樹(shù)的后序線索樹(shù)。
③將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)〔或森林〕。
答案：
A
B
F
D
③
10、
C
E
H
G
①②
〔3〕假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
①試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。
② 試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。
③對(duì)于上述實(shí)例，對(duì)比兩種方案的優(yōu)缺點(diǎn)。
答案：方案1；哈夫曼編碼
先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。
w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[〔2,3〕，6], (7,10)】, ……19,21,32
〔100〕
〔40〕 〔60〕
19 21
11、 32 〔28〕
〔17〕〔11〕
7 10 6 〔5〕
2 3
0 1
0 1 0 1
19 21 32
0 1
0 1 0 1
7 10 6
0 1
2 3
方案對(duì)比：
字母編號(hào)
對(duì)應(yīng)編碼
出現(xiàn)頻率
1
000
0.07
2
001
0.19
3
010
0.02
4
011
0.06
5
100
0.32
6
101
0.03
7
110
0.21
8
111
0.10
字母編號(hào)
對(duì)應(yīng)編碼
出現(xiàn)頻率
12、
1
1100
0.07
2
00
0.19
3
11110
0.02
4
1110
0.06
5
10
0.32
6
11111
0.03
7
01
0.21
8
1101
0.10
方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼
〔4〕以下字符A、B、C、D、E、F、G的權(quán)值分別為3、
13、12、7、4、2、8，11，試填寫出其對(duì)應(yīng)哈夫曼樹(shù)HT的存儲(chǔ)構(gòu)造的初態(tài)和終態(tài)。
答案：
初態(tài):
?
weight
parent
lchild
rchild
1
3
0
0
0
2
12
0
0
0
3
7
0
0
0
4
4
0
0
0
5
2
0
0
0
6
8
0
0
0
7
11
0
0
0
8
?
0
0
0
9
?
0
0
0
10
?
0
0
0
11
?
0
0
0
12
?
0
0
0
13
?
0
0
0
終態(tài)：
?
weigh
14、t
parent
lchild
rchild
1
3
8
0
0
2
12
12
0
0
3
7
10
0
0
4
4
9
0
0
5
2
8
0
0
6
8
10
0
0
7
11
11
0
0
8
5
9
5
1
9
9
11
4
8
10
15
12
3
6
11
20
13
9
7
12
27
13
2
10
13
47
0
11
12
3．算法設(shè)計(jì)題
以二叉鏈表作為二叉樹(shù)的存儲(chǔ)構(gòu)造，編寫以下算法：
〔1〕統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)。
[題目分析]
15、如果二叉樹(shù)為空，返回0，如果二叉樹(shù)不為空且左右子樹(shù)為空，返回1，如果二叉樹(shù)不為空，且左右子樹(shù)不同時(shí)為空，返回左子樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)。
[算法描述]
int LeafNodeCount(BiTree T)
{
if(T==NULL)
return 0; //如果是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為0
else if(T->lchild==NULL&&T->rchild==NULL)
return 1; //判斷結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)〔左孩子右孩子都為空〕，假設(shè)是則返回1
else
return LeafNodeCount(T->lchild)+Leaf
16、NodeCount(T->rchild);
}
〔2〕判別兩棵樹(shù)是否相等。
[題目分析]先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點(diǎn)不相等，直接返回兩棵樹(shù)不相等;如果當(dāng)前節(jié)點(diǎn)相等，那么就遞歸的判斷他們的左右孩子是否相等。
[算法描述]
int compareTree(TreeNode* tree1, TreeNode* tree2)
//用分治的方法做，對(duì)比當(dāng)前根，然后對(duì)比左子樹(shù)和右子樹(shù)
{bool tree1IsNull = (tree1==NULL);
bool tree2IsNull = (tree2==NULL);
if(tree1IsN
17、ull != tree2IsNull)
{
return 1;
}
if(tree1IsNull && tree2IsNull)
{//如果兩個(gè)都是NULL，則相等
return 0;
}//如果根節(jié)點(diǎn)不相等，直接返回不相等，否則的話，看看他們孩子相等不相等
if(tree1->c != tree2->c)
{
return 1;
}
return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))
(compareTree(tree1->left,tree2-
18、>right)&compareTree(tree1->right,tree2->left));
}//算法完畢
〔3〕交換二叉樹(shù)每個(gè)結(jié)點(diǎn)的左孩子和右孩子。
[題目分析]如果某結(jié)點(diǎn)左右子樹(shù)為空，返回，否則交換該結(jié)點(diǎn)左右孩子，然后遞歸交換左右子樹(shù)。
[算法描述]
void ChangeLR(BiTree &T)
{
BiTree temp;
if(T->lchild==NULL&&T->rchild==NULL)
return;
else
{
temp = T->lchild;
T->lchild = T->rchild;
T->rchild =
19、temp;
}//交換左右孩子
ChangeLR(T->lchild); //遞歸交換左子樹(shù)
ChangeLR(T->rchild); //遞歸交換右子樹(shù)
}
〔4〕設(shè)計(jì)二叉樹(shù)的雙序遍歷算法〔雙序遍歷是指對(duì)于二叉樹(shù)的每一個(gè)結(jié)點(diǎn)來(lái)說(shuō)，先訪問(wèn)這個(gè)結(jié)點(diǎn)，再按雙序遍歷它的左子樹(shù)，然后再一次訪問(wèn)這個(gè)結(jié)點(diǎn)，接下來(lái)按雙序遍歷它的右子樹(shù)〕。
[題目分析]假設(shè)樹(shù)為空，返回；假設(shè)某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則僅輸出該結(jié)點(diǎn)；否則先輸出該結(jié)點(diǎn)，遞歸遍歷其左子樹(shù)，再輸出該結(jié)點(diǎn)，遞歸遍歷其右子樹(shù)。
[算法描述]
void DoubleTraverse(BiTree T)
{
if(T == NULL)
20、
return;
else if(T->lchild==NULL&&T->rchild==NULL)
cout<data; //葉子結(jié)點(diǎn)輸出
else
{
cout<data;
DoubleTraverse(T->lchild); //遞歸遍歷左子樹(shù)
cout<data;
DoubleTraverse(T->rchild); //遞歸遍歷右子樹(shù)
}
}
〔5〕計(jì)算二叉樹(shù)最大的寬度〔二叉樹(shù)的最大寬度是指二叉樹(shù)所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值〕。
[題目分析] 求二叉樹(shù)高度的算法見(jiàn)上題。求最大寬度可采用層次遍
21、歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，假設(shè)結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。
[算法描述]
int Width(BiTree bt)//求二叉樹(shù)bt的最大寬度
{if (bt==null) return (0); //空二叉樹(shù)寬度為0
else
{BiTree Q[];//Q是隊(duì)列，元素為二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大
front=1;rear=1;last=1;
//front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置
temp=0; maxw=0; //temp記局部寬度, maxw記最大寬度
Q[rear]=bt;
22、 //根結(jié)點(diǎn)入隊(duì)列
while(front<=last)
{p=Q[front++]; temp++; //同層元素?cái)?shù)加1
if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入隊(duì)
if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入隊(duì)
if (front>last) //一層完畢，
{last=rear;
if(temp>maxw) maxw=temp;
//last指向下層最右元素, 更新當(dāng)前最大寬度
temp=0;
}//if
}/
23、/while
return (maxw);
}//完畢width
〔6〕用按層次順序遍歷二叉樹(shù)的方法，統(tǒng)計(jì)樹(shù)中具有度為1的結(jié)點(diǎn)數(shù)目。
[題目分析]
假設(shè)某個(gè)結(jié)點(diǎn)左子樹(shù)空右子樹(shù)非空或者右子樹(shù)空左子樹(shù)非空，則該結(jié)點(diǎn)為度為1的結(jié)點(diǎn)
[算法描述]
int Level(BiTree bt) //層次遍歷二叉樹(shù)，并統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù)
{int num=0; //num統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù)
if(bt){QueueInit(Q); QueueIn(Q,bt);//Q是以二叉樹(shù)結(jié)點(diǎn)指針為元素的隊(duì)列
while(!QueueEmpty(Q))
{p=QueueOut(Q); cout
24、<data; //出隊(duì),訪問(wèn)結(jié)點(diǎn)
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;
//度為1的結(jié)點(diǎn)
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入隊(duì)
if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入隊(duì)
} //while(!QueueEmpty(Q))
}//if(bt)
return(num);
}//返回度為1的結(jié)點(diǎn)的個(gè)數(shù)
〔7〕求任意二叉樹(shù)中第一條最長(zhǎng)的路徑長(zhǎng)度，并輸出此路徑上各結(jié)點(diǎn)
25、的值。
[題目分析]因?yàn)楹笮虮闅v棧中保存當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)，則將該棧倒入輔助棧中，輔助棧始終保存最長(zhǎng)路徑長(zhǎng)度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。
[算法描述]
void LongestPath(BiTree bt)//求二叉樹(shù)中的第一條最長(zhǎng)路徑長(zhǎng)度
{BiTree p=bt,l[],s[];
//l, s是棧，元素是二叉樹(shù)結(jié)點(diǎn)指針，l中保存當(dāng)前最長(zhǎng)路徑中的結(jié)點(diǎn)
int i，top=0,tag[],longest=0;
while(p || top>0)
{while(p) {s[+
26、+top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下
if(tag[top]==1) //當(dāng)前結(jié)點(diǎn)的右分枝已遍歷
{if(!s[top]->Lc && !s[top]->Rc) //只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長(zhǎng)度
if(top>longest)
{for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}
//保存當(dāng)前最長(zhǎng)路徑到l棧，記住最高棧頂指針，退棧
}
else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下
}//while(p!=null
27、||top>0)
}//完畢LongestPath
〔8〕輸出二叉樹(shù)中從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。
[題目分析]采用先序遍歷的遞歸方法，當(dāng)找到葉子結(jié)點(diǎn)*b時(shí)，由于*b葉子結(jié)點(diǎn)尚未添加到path中，因此在輸出路徑時(shí)還需輸出b->data值。
[算法描述]
void AllPath(BTNode *b,ElemType path[],int pathlen)
{int i;
if (b!=NULL)
{if (b->lchild==NULL && b->rchild==NULL) //*b為葉子結(jié)點(diǎn)
{cout << " " << b->data << "到根結(jié)點(diǎn)路徑:" <<
28、 b->data;
for (i=pathlen-1;i>=0;i--)
cout << endl;
}
else
{path[pathlen]=b->data; //將當(dāng)前結(jié)點(diǎn)放入路徑中
pathlen++; //路徑長(zhǎng)度增1
AllPath(b->lchild,path,pathlen); //遞歸掃描左子樹(shù)
AllPath(b->rchild,path,pathlen); //遞歸掃描右子樹(shù)
pathlen--; //恢復(fù)環(huán)境
}
}//if (b!=NULL)
}//算法完畢
數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版 第二版(嚴(yán)蔚敏) 第5章樹(shù)和二叉樹(shù) 答案
