柚子快報激活碼778899分享：初試811-數(shù)據(jù)結(jié)構(gòu)(C語言)
柚子快報激活碼778899分享：初試811-數(shù)據(jù)結(jié)構(gòu)(C語言)
第五章：樹和二叉樹??
知識點：
樹的概念 樹的性質(zhì)：
考題：一些概念
樹的路徑長度是從樹根到每個結(jié)點的路徑長度的總和 P131，t6 P131，t10
??重要性質(zhì)：n個結(jié)點的樹具有n-1條邊，那么對于每一棵樹，其結(jié)點數(shù)比邊數(shù)多1，結(jié)點樹比邊數(shù)多n，就有n棵樹。 二叉樹
概念
滿二叉樹與完全二叉樹的異同
正則二叉樹 性質(zhì)
高度
考題
第i結(jié)點的左孩子，不一定為2i，因為未必存在 ??注意：樹的性質(zhì)難題，往往是給定一些條件，讓你確定某些說法是否正確，這種題一般選項都難以判斷，解決辦法是從定義下手，回想該樹的定義，然后從特殊的情況下手，比方說根節(jié)點，既滿足原本定義，又符合題目要求，即可選出答案
P139，t18 性質(zhì)的應用，綜合題：P140，t4、t5、t6 遍歷
與各表達式的異同
應用
注意??：給定了一個遍歷序列，無法推出具體的樹
緣由 南郵的話需要了解，遍歷的遞歸算法與非遞歸算法都要學會 遍歷的考題：P155（t8、t9、t20、t21） 存儲
注意二叉樹的順序存儲結(jié)構(gòu)，只適合完全二叉樹 如果存儲非完全二叉樹，需要用isEmpty來判斷是否有左右孩子
存儲非完全二叉樹的缺陷，太浪費空間 二叉樹、樹、森林
主要考點（轉(zhuǎn)化為二叉樹）
“左孩子，右兄弟“ 重要性質(zhì) 1、分支節(jié)點的最右孩子一定是葉子結(jié)點 2、森林轉(zhuǎn)化的二叉樹，最右邊是葉子結(jié)點 3、左指針為空的沒有孩子(葉節(jié)點) 哈夫曼樹
主要考點
重要性質(zhì)
結(jié)點為奇數(shù)2n-1（合并n-1次） 每個子樹，對應左右子樹都可以任意看成0/1，即固定一部分，看后續(xù)有沒有違反 P198：t18 線索二叉樹
中序線索二叉樹
代碼：??都別忘了處理最后一個結(jié)點
中序 先序線索化，需要注意判斷l(xiāng)tag==0
進階：學會寫所有遍歷的算法，遞歸的非遞歸的，線索化代碼，手推前中后序線索化，找前驅(qū)后繼的過程，包括線索二叉樹的遍歷過程，可以實現(xiàn)低時間復雜度
并不是每個結(jié)點通過線索就能直接求出直接前驅(qū)和后繼： 前序：找前驅(qū)麻煩 后序：找后繼麻煩（都需要知道父節(jié)點，三叉鏈表） 2.后序線索化，無法通過線索遍歷所有結(jié)點，需要用到棧的支持（??） 線索二叉樹：為一種物理結(jié)構(gòu) 二叉樹為一種邏輯結(jié)構(gòu)，但線索二叉樹是加上線索后的鏈表線性表結(jié)構(gòu)，即它是二叉樹在計算機內(nèi)部的一種存儲結(jié)構(gòu)，所以是一種物理結(jié)構(gòu)
有序樹：
樹中任意節(jié)點的?子結(jié)點之間有順序關(guān)系，這種樹稱為有序樹
無序樹：
樹中任意節(jié)點的?子結(jié)點之間沒有順序關(guān)系，這種樹稱為無序樹,也稱為自由樹
拓展 ：遞歸
本章遞歸遍歷極其重要??，是解決樹問題的關(guān)鍵??
遞歸可視化過程，對寫出遞歸代碼幫助大
Q&A：
1、對于三個結(jié)點A、B和C，可分別組成多少不同的無序樹、有序樹和二叉樹？
可以組成?9?種無序樹，分別是：
1個父節(jié)點，2個子結(jié)點的情況有 3 種鏈式結(jié)構(gòu)有 6 種（因為鏈式結(jié)構(gòu)相互之間都是父子關(guān)系，所以有6種不同的組合）
有?12?種有序樹，分別是：
1個父節(jié)點，2個子結(jié)點的情況有 6 種（子樹可以交換位置）鏈式結(jié)構(gòu)有 6 種
組成的二叉樹，30種，如下圖所示每個6種（3!）
A
/ \
B C //第一種
A
/
B
/
C //第二種
A
\
B
\
C //第三種
A
/
B
\
C //第四種
A
\
B
/
C //第五種
2、如果哈夫曼樹T有n?個葉子結(jié)點，那么，樹T有多少個結(jié)點?要求給出求解過程。??
首先哈夫曼樹，屬于二叉樹，即存在性質(zhì)n?=n?+1，且哈夫曼樹沒有度為1的結(jié)點。故n=2n?+1=2(n?-1)+1,即樹T有2n?-1個結(jié)點
?3、設一棵完全二叉樹采用順序存儲結(jié)構(gòu)，保存在一維數(shù)組A中。試設計一個遞歸算法，復制該完全二叉樹，得到一棵新的采用普通二叉鏈表存儲的二叉樹。設二叉鏈表的每個結(jié)點有3個域：lChild，rChild和element。算法返回所構(gòu)造的新二叉樹的根結(jié)點地址。
typedef struct TreeNode{ //結(jié)構(gòu)體
int element;
TreeNode *lChild;
TreeNode *rChild;
TreeNode(int val) : element(val), lChild(nullptr), rChild(nullptr) {}
}TreeNode,*Tree;
Tree copyBuild(int A[],int n,int index){
if(index>=n) //如果下標超出數(shù)組范圍return NULL
return null;
//創(chuàng)建樹鏈結(jié)點
TreeNode *TNode = new TreeNode(A[index]);
//遞歸構(gòu)造
Tnode->lChild=copyBuild(A,n,index*2+1);
Tnode->rChild=copyBuild(A,n,index*2+2);
//返回根結(jié)點
return Tnode;
}
4、已知二叉樹以二叉鏈表存儲，是編寫算法輸出二叉樹中值為x的結(jié)點的所有祖先結(jié)點，假設值為x的結(jié)點不超過1個。
bool findAllParents(int x, LinkTree *T) {
if (T == null)
return false; // 空樹返回，尋找失敗
if (T->data == x)
return true; // 找到目標直接返回true
// 檢查左子樹或右子樹中是否能找到目標節(jié)點
if ((T->data > x && findAllParents(x, T->lChild)) ||
(T->data < x && findAllParents(x, T->rChild))) {
print(T); // 打印路徑祖先節(jié)點
return true; // 找到后返回true，停止繼續(xù)遞歸
}
return false; // 如果在當前節(jié)點及其子樹中未找到目標節(jié)點，返回false
}
5、設計一個算法，對二叉樹進行按從上到下、從左到右的層次遍歷。
//遞歸形式
void levelSearch(LinkTree *T, Queue &Q) {
if (T == null)
return; // 是空樹，就返回
print(T); // 打印當前節(jié)點
// 將左右子樹入隊，前提是子樹非空
if (T->lChild != null)
Q.Enqueue(T->lChild);
if (T->rChild != null)
Q.Enqueue(T->rChild);
// 隊列非空，一個個出隊，遞歸
if (!Q.IsEmpty()) {
LinkTree *nextNode = Q.Dequeue();
levelSearch(nextNode, Q);
}
}
//非遞歸，迭代形式，特別適用于廣度優(yōu)先遍歷
void levelSearch(LinkTree *T) {
if (T == null)
return; // 空樹直接返回
Queue Q;
Q.Enqueue(T); // 根節(jié)點入隊
while (!Q.IsEmpty()) {
LinkTree *current = Q.Dequeue(); // 出隊一個節(jié)點
print(current); // 打印當前節(jié)點
// 將當前節(jié)點的左右子節(jié)點入隊
if (current->lChild != null)
Q.Enqueue(current->lChild);
if (current->rChild != null)
Q.Enqueue(current->rChild);
}
}
6、設一棵二叉樹T采用二叉鏈表表示，試設計一個算法判斷二叉樹T是否為完全二叉樹。
//算法思想：完全二叉樹，即每個父節(jié)點可以有左孩子
//，或者同時擁有左右孩子，不存在只擁有右孩子
//遞歸形式
bool judge(LinkTree *T, Queue &Q)
{
if (T == null)
return true; // 空樹直接返回
if (T->lChild == null && T->rChild != null)
return false; // 存在只有右孩子的節(jié)點，非完全二叉樹
if (T->lChild != null)
Q.Enqueue(T->lChild);
if (T->rChild != null)
Q.Enqueue(T->rChild);
if (!Q.isEmpty())
{
LinkTree *nextTree = Q.Dequeue();
return judge(nextTree, Q); // 遞歸調(diào)用時返回結(jié)果
}
return true; // 隊列為空，表示所有節(jié)點已處理完且符合條件
}
//迭代形式
bool judge(LinkTree *T)
{
if (T == null)
return true; // 空樹直接返回
Queue Q;
Q.Enqueue(T);
while (!Q.isEmpty())
{
LinkTree *current = Q.Dequeue();
if (current->lChild == null && current->rChild != null) // 非完全二叉樹
return false;
if (current->lChild != null) // 陸續(xù)入非空的左右子樹
Q.Enqueue(current->lChild);
if (current->rChild != null)
Q.Enqueue(current->rChild);
}
return true; // 如果所有節(jié)點都符合條件，返回true
}
7、分別寫出下面的算法 (1)在中序線索二叉樹T中查找給定結(jié)點*p在中序序列中的前驅(qū)和后繼。
//找到以p為根的子樹中，第一個被中序遍歷的結(jié)點
ThreadNode *Firstnode(ThreadNode *p){
//循環(huán)找到最左下結(jié)點(不一定是葉結(jié)點)
while(p->ltag==0) p=p->lchild;
return p;
}
//在中序線索二叉樹中找到結(jié)點p的后繼結(jié)點
ThreadNode *Nextnode(ThreadNode *p){
//右子樹中最左下的結(jié)點
if(r->rtag==0) return Firstnode(p->rChild);
else return p->rChild; //rtag==1直接返回后繼
}
-------------------------------------------------
//找到以p為根的子樹中，最后被中序遍歷的結(jié)點
ThreadNode *Firstnode(ThreadNode *p){
//循環(huán)找到最右下結(jié)點(不一定是葉結(jié)點)
while(p->rtag==0) p=p->rchild;
return p;
}
//在中序線索二叉樹中找到結(jié)點p的前驅(qū)結(jié)點(前驅(qū)即右下)
ThreadNode *Prenode(ThreadNode *p){
//左子樹中最右下的結(jié)點
if(r->ltag==0) return Firstnode(p->lChild);
else return p->lChild; //ltag==1直接返回前驅(qū)
}
(2)在先序線索二叉樹T中查找給定結(jié)點*p在先序序列中的后繼。
//在先序線索二叉樹中找到結(jié)點p的后繼結(jié)點
//ltag==0,有左子樹，后繼就是其左子樹的根
//ltag==1，即沒有左子樹，根據(jù)先序遍歷NLR，即后繼就是右子樹的根
ThreadNode *Nextnode(ThreadNode *p){
if(r->ltag==0) return p->lChild;
else return p->rChild; //rtag==1直接返回后繼
}
(3)在后序線索二叉樹T中查找給定結(jié)點*p在后序序列中的前驅(qū)。
//在后序線索二叉樹中找到結(jié)點p的前驅(qū)結(jié)點
//1）ltag==0,有左子樹，根據(jù)LRN，前驅(qū)結(jié)點比較復雜需要分析左右子樹
//若右子樹存在，即內(nèi)判斷rtag==0，尋找右子樹最后一個后序遍歷的結(jié)點，即右子樹的根
//若右子樹不存在，即rtag==1，尋找左子樹最后一個后序遍歷的結(jié)點，即左子樹的根
//2）ltag==1，即沒有左子樹，根據(jù)線索化定義，其前驅(qū)就是lChild
ThreadNode *Prenode(ThreadNode *p) {
if (p->ltag == 0) { // 如果p有左子樹
if (p->rtag == 0) { // 如果p有右子樹
return p->rchild; // 右子樹根結(jié)點即為前驅(qū)
} else { // 如果p沒有右子樹
return p->lchild; // 左子樹根結(jié)點即為前驅(qū)
}
} else {
return p->lchild; // 沒有左子樹，直接返回lchild作為前驅(qū)
}
}
8、假設二叉樹以二叉鏈表存儲，設計一個算法，求其指定的某一層k(k>1)的葉子結(jié)點個數(shù)
//k>1,傳入?yún)?shù)即是根結(jié)點時，第一層
int N0 = 0; //全局變量
void countN0(LinkTree *T, int k) {
if (T == nullptr) {
return; // 空節(jié)點直接返回
}
if (k == 1) {
// 如果當前層數(shù)是目標層，且是葉子節(jié)點
if (T->lChild == null && T->rChild == null) {
N0++;
}
return;
}
// 遞歸處理左子樹和右子樹，層數(shù)減1
countN0(T->lChild, k - 1);
countN0(T->rChild, k - 1);
}
柚子快報激活碼778899分享：初試811-數(shù)據(jù)結(jié)構(gòu)(C語言)
推薦閱讀
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Ioffer國際自由市
