# 資料結構與演算法 習題解答 第5章
## 第五章 樹
---
### 1. 針對程式 5-1 一般化串列鏈結節點的宣告，設計樹的輸入，寫出必要的程序，使能完成樹的一般化鏈結串列的建構。
:::spoiler
```cpp=
Add (struct TreeNode *p, struct TreeNode *subtree)
{ struct TreeNode *s;
s->tag = 1;
s->link = p->link;
p->link = s;
s->node = subtree;
}
```
:::
---
### 2. 在 5.2.2 節中，我們用圖 5-7 描繪了左子右兄弟表示法的節點構造，請寫出此節點的程式宣告。
:::spoiler
```cpp=
# include <stdio.h>
struct node
{ struct node *leftmostchild;
int data;
struct node *rightsibling;
};
struct node *root;
int main(){
return 0;
}
```
:::
---
### 3. 在5.2.3節中我們討論了分支度為2的樹表示法，請寫出此節點的程式宣告。
:::spoiler
```cpp=
# include <stdio.h>
struct node
{ struct node *Left;
int data;
struct node *Right;
};
struct node *root;
int main(){
return 0;
}
```
:::
---
### 4. 一個分支度為 k，高度為 h 的二元樹，其最大節點數為多少？證明你的答案。
:::spoiler
$\sum\limits_{i=1}^{h}{k^{i-1}} = 1+k^1+k^2+...+k^{h-1} = \frac{k^h-1}{k-1}$
:::
---
### 5. 參考程式 5-6-1，實作出非遞迴版本的程式，執行二元樹前序走訪。
:::spoiler
```cpp=
# include <stdio.h>
# include <stdlib.h>
//BinaryTreeNode
struct node
{ struct node *LeftChild;
int data;
struct node *RightChild;
};
struct node *NewNode(int x)
{ struct node *Node = (struct Node *)malloc(sizeof(struct node));
Node->data = x;
Node->LeftChild = NULL;
Node->RightChild = NULL;
return Node;
}
struct node *Insert(struct node *Node,int x){
if (Node == NULL) return NewNode(x);
if (x < Node->data) Node->LeftChild = Insert(Node->LeftChild, x);
else Node->RightChild = Insert(Node->RightChild, x);
return Node;
}
struct node *root;
//Stack
struct node **Stack;
int top = -1;
void push(struct node *element)
{ if (top >= 1000) return;
else Stack[++top] = element;
}
struct node *pop(){
if (top == -1)return NULL;
else return Stack[top--];
}
int StackEmpty()
{ return top == -1;
}
//preorder
void preorder()
{ struct node *p = root;
while (!StackEmpty()||p)
{ while (p)
{ printf("%d\n", p->data);
push(p);
p = p->LeftChild;
}
if (!StackEmpty())
{ p = pop();
p = p->RightChild;
}
}
}
int main()
{ Stack = (struct Node **)malloc(1000 * sizeof(struct node*));//Insert 100 random number(0~32767)
for(int i=0; i<100; i++)
{ int number = rand();
root = Insert(root,number);
}
preorder();
}
```
:::
---
### 6. 參考程式 5-6-2 和習題 6，實作出非遞迴版本的程式，執行二元樹後序走訪。
:::spoiler
```cpp=
struct BTreeNode
{ struct BTreeNode *leftchild;
char data;
bool traversed = false;
struct BtreeNode *rightchild;
};
void postorder_Stack()
{ struct StackNode *top;
struct BTreeNode *node = root;
push_node(node);
do
{ while (node != NULL)
{ push_node(node);
node = node->leftchild;
}
if (top != NULL)
{ node = pop_node();
if(node->rightchild != NULL && node->traversed == false)
{ push_node(node);
node->traversed == true;
node = node->rightchild;
}
else
{ cout << node->data;
node = NULL;
}
}
} while (top != NULL);
}
```
:::
---
### 7. 參考程式 5-7 實作出階層走訪 (level-order travesal) 的程式，走訪一二元樹。
:::spoiler
```cpp=
# include <stdio.h>
# include <stdlib.h>
//BinaryTreeNode
struct node
{ struct node *LeftChild;
int data;
struct node *RightChild;
};
struct node *NewNode(int x)
{ struct node *Node = (struct node *)malloc(sizeof(struct node));
Node->data = x;
Node->LeftChild = NULL;
Node->RightChild = NULL;
return Node;
}
struct node *Insert(struct node *Node,int x){
if (Node == NULL) return NewNode(x);
if (x < Node->data)
Node->LeftChild = Insert(Node->LeftChild, x);
else
Node->RightChild = Insert(Node->RightChild, x);
return Node;
}
struct node *root;
//Queue
struct node **Queue;
int front = -1, rear = -1;
void AddQueue(struct node *element)
{ if (front >= 1000) return;
else Queue[++rear] = element;
}
struct node *DeleteQueue(){
if (rear == front)return NULL;
else return Queue[++front];
}
int QueueEmpty()
{ return front == rear;
}
//levelOrder
void LevelOrder()
{ AddQueue(root);
struct node *p = NULL;
while (!QueueEmpty())
{ p = DeleteQueue();
printf("%d\n", p->data);
if (p->LeftChild )
AddQueue(p->LeftChild);
if (p->RightChild)
AddQueue(p->RightChild);
}
}
int main()
{
Queue = (struct Node **)malloc(1000 * sizeof(struct node*));
//Insert 100 random number(0~32767)
for(int i=0; i<100; i++)
{ int number = rand();
root = Insert(root,number);
}
LevelOrder();
}
```
:::
---
### 8. 寫出能計算出二元樹 $T$ 中葉節點數目的程序，分析它的計算時間為何？
:::spoiler
利用階層走訪，當分支數為0 時Count++，走訪完後傳回Count 即為葉節點個數。
```cpp=
int Count_leaveNode()
{ struct StackNode *top;
struct BTreeNode *node = root;
push_node(node);
int Count = 0;
while(top != NULL)
{ node = pop_node();
cout << node->data;
int count = 0;
if(node->rightchild != NULL)
{ push_node(node->rightchild);
count++;
}
if (node-> leftchild != NULL)
{ push_node(node->leftchild);
count++;
}
if (count == 0)
Count++;
}
return Count;
}
```
時間複雜度為 $O(n)$，其中 $n$ 為節點個數。
:::
---
### 9. 寫出一演算法將輸入的二元樹 T，以 SwapTree(T)交換每一個節點的左右子點。請看圖 5-55 的例子。
:::spoiler
```cpp=
SwapTree(Tree T)
{ for( T 上每一個點)
{ node = T->leftchild;
T->leftchild = T->rightchild;
T->rightchild = node;
}
}
```
:::
---
### 10. 試想若程式 5-11 中的程序 Next，所傳入的參數指標正是 root，請問 Next是否可正常運作？
:::spoiler
當程式執行Next(root)時
(1)會將 temp 指向 root->rightchild (root->rightchild = 自己)，即node 與 temp 皆指向 root。
(2)判斷 temp->rightthread，因為 root->rightthread = 0，故會找temp->leftchild，即 root->leftchild。
由 (1) 和 (2) 可知執行 Next (root) 時候，可以正常運作，並且能找到該樹中序表
示中的第一個節點。
:::
---
### 11. 請參考程式 5-12，寫出程序—使可插入節點 new 成為引線二元樹的節點 p 的左子節點。
:::spoiler
```cpp=
void Threaded::InsertLeft ( ThreadedNode *s, char ch)//建立node h; 將ch 存入h; 插入h 作為s 的左兒子
{ ThreadedNode *h = new ThreadNode(ch);
h->LeftChild = s->LeftChild;
h->LeftThread = s->LeftThread;
h->RightChild = s;
h->RightThread = TRUE; // 右兒子為引線
s->LeftChild = h; //把h 加到s
s->LeftThread = FALSE;
if(!h->LeftThread)
{ ThreadedNode *temp = InorderPred(h);
Temp->RightChild = h;
}
}
```
:::
---
### 12. 考慮使用後序引線而非前序引線來連接一二元樹時，哪一個走訪法可以不使用堆疊就能夠完成？對於這些不使用堆疊就能夠完成的走訪法，寫出演算法來，並且分析其空間的複雜度。
:::spoiler
沒有任何走訪可以不使用堆疊就能完成。
以下圖高度為 3 的後序引線二元樹為例：
1. 中序走訪：第一個走訪節點為 D，下一個節點應為 B，但此時就無法透過節點 D 的左引線或右引線到達節點 B，故可知中序走訪無法不使用堆疊完成。
2. 前序走訪：第一個走訪節點為 A，下一個節點應為 B，可由節點 A 的左指標到達，而在下一個節點應為 D，可由節點 B 的左指標到達，再下一個節點應為 E，可由節點 D 的右引線到達，再下一個節點應為 C ，但此時就無法透過節點 E 的左引線或右引線到達節點 C，故可知前序走訪無法不使用堆疊完成。
3. 後序走訪：第一個走訪節點為 D，下一個節點應為 E，可由節點 D 的右引線到達，而下一個節點應為 B，可由節點 E 的右引線到達，再下一個節點應為 C，但此時就無法透過節點 B 的左指標或右指標到達節點 C，故可知後序走訪無法不使用堆疊完成。
以下圖高度為 4 的後序引線二元樹為例：
1. 中序走訪：第一個走訪節點為 H，下一個節點應為 D，但此時就無法透過節點 H 的左引線或右引線到達節點 D，故可知中序走訪無法不使用堆疊完成。
2. 前序走訪：第一個走訪節點為 A，下一個節點應為 B，可由節點 A 的左指標到達，而在下一個節點應為 D，可由節點 B 的左指標到達，再下一個節點應為 H，可由節點 D 的左指標到達，再下一個節點應為 I ，可由節點 H 的右引線到達，再下一個節點應為 E，但此時就無法透過節點 I 的左引線或右引線到達節點 E，故可知前序走訪無法不使用堆疊完成。
3. 後序走訪：第一個走訪節點為 H，下一個節點應為 I，可由節點 H 的右引線到達，而下一個節點應為 D，可由節點 I 的右引線到達，再下一個節點應為 E，但此時就無法透過節點 D 的左指標或右指標到達節點 E，故可知後序走訪無法不使用堆疊完成。
要能舉出沒有任何走訪可以不使用堆疊就能完成走訪的例子需在後序引線二元樹的高度大於 2 時才能舉出，
下圖為高度為 2 時有走訪法能成功走完的例子：
此後序引線二元樹高度為 2，但因只有兩個節點，所以不管是中序、前序和後序走訪都能成功走訪完，故無法舉出沒有任何走訪可以不使用堆疊就能完成走訪的例子。
此後序引線二元樹高度為 2，且為完滿二元樹，但此樹在前序和後序走訪時能成功利用後序引線走訪完整棵樹，唯獨在中序走訪無法成功，故無法舉出沒有任何走訪可以不使用堆疊就能完成走訪的例子。
:::
---
### 13. 寫一演算法以在最小堆積中作插入動作。這個演算法的複雜度應為$O(logn)$，請證明。
:::spoiler
```cpp=
void InsertHeap(int x)
{ if (n == maxsize) HeapFull();
else
{ n++;
i = n;
while ((i > 1) && (x < heap[i/2]))
{ heap[i] = heap[i/2];
i /= 2;
}
heap[i] = x;
}
}
```
新增節點的位置若在 $k$ 處，則新增資料可能的位置，會在 $k$ 往上走至樹根的任何節點上，亦即最差情況程式迴圈會執行 ⎡$log(k+1)$⎤ 次，這也是此完備二元樹的深度。因此程序 InsertHeap 在插入第 $n$ 個資料時，需要的時間複雜度為 $O(logn)$。
:::
---
### 14. 寫一演算法在最小堆積中刪除最小元素。此演算法的複雜度為 $O(logn)$，並證明這一點。
:::spoiler
```cpp=
int DeleteHeap()
{ int x, i, j;
if (n == 0) HeapEmpty();
else
{ x = heap[1];
heap[1] = heap[n];
n--;
i = 1;
while (i <= n/2)
{ if (heap[2*i] < heap[2*i+1]) j = 2*i;
else j = 2*i+1;
if (heap[i] < heap[j]) break;
swap(&heap[i], &heap[j]);
i = j;
}
return x;
}
}
```
每次刪除最小元素heap[1]後，將最後一個元素heap[$n$]取代heap[1]，並將堆積修正回最小堆積，故最差狀況會是取代後的heap[1]比對堆積的深度 $logn$ 次後才得到最小堆積，因此複雜度為 $O(logn)$。
:::
---
### 15. 證明一樹林的前序走訪與其對應二元樹的前序走訪，結果相同。
:::spoiler
假設$(T_1, T_2, ..., T_n)$視為一樹林且$PO(T_1, T_2, ..., T_n)$為樹林的前序走訪，將森林的樹個別做前序走訪並依序合併寫作$PO(T_1), PO(T_2), ..., PO(T_n)$，可將$T_1$視為是根以及左子樹，$T_2, T_3, ..., T_n$視為右子樹，顯然的，$T_1$ 在其他樹的元素前先做了前序走訪，重複這個假設，我們可以得到 $T_1, T_2, ..., T_n$ 的前序走訪會與樹林的前序走訪有相同的順序。
:::
---
### 16. 證明一樹林的階層走訪與其對應二元樹的階層走訪，並不一定獲得相同的結果。
:::spoiler
由上圖中樹林的階層順序為 ABCDEFGHI 與二元樹的階層順序為 ABCDGEHFI 不同。以圖5-51 樹林與圖5-53樹林對應的二元樹為例：
樹林的階層走訪為： ABCDEFGHI
樹林對應的二元樹之階層走訪為： ABCDGEHFI
:::
---
### 17. 以樹林後序走訪法，寫一個非遞迴程序走訪一樹林的對應二元樹。並計算你的程序之時間與空間複雜度。
:::spoiler
```cpp=
void Forest :: postorder()
{ stack<ForestNode*> s;
ForestNode *node = root;
ForestNode *prev = NULL;
while(node != NULL || !s.empty())
{ while(node != NULL)
{ s.push(node);
node = node->leftchild;
}
node = s.top();
if(node->rightchild == NULL || node->rightchild == prev)
{ cout<< node->data<< endl;
s.pop();
prev = node;
node = NULL;
}
else
{ node = node->rightchild;
}
}
}
```
時間複雜度 $O(n)$，$n$ 為樹林中節點的個數。
空間複雜度 $O(n)$，$n$ 為樹林中節點的個數。
:::
---
### 18. 二元樹中的中序和後序順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其後序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由後序與中序可以得到唯一的二元樹。
推論：使 T 為一個有 $n$ 個節點的樹，使它的後序與中序分別為 $p_1, p_2, ..., p_n$ 和 $i_1, i_2, ...i_n$，後序的最後一個元素為樹根，也就是 $p_n$，找到 $p_n$ 在中序中的位置，稱之為 $i_k$ ，因此，$(i_1, i_2, ..., i_{k-1})$ 與 $(p_1, p_2, ..., p_{k-1})$ 為 T 的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$ 與 $(p_k, p_{k+1}, ..., p_{n-1})$ 為 T 的右子樹。
T 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的後序與中序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一，因此 T 也為唯一的二元樹。
:::
---
### 19. 二元樹中的中序和前序順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其前序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由前序與中序可以得到唯一的二元樹。
推論：使 T 為一個有 $n$ 個節點的樹，使它的前序與中序分別為 $p_1, p_2, ..., p_n$ 和 $i_1, i_2, ...i_n$ ，前序的第一個元素為樹根，也就是 $p_1$，找到 $p_1$ 在中序中的位置，稱之為 $i_k$ ，因此，$(i_1, i_2, ..., i_{k-1})$ 與 $(p_2, p_3, ..., p_{k})$ 為T的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$ 與 $(p_{k+1}, p_{k+2}, ..., p_{n})$ 為 T 的右子樹。
T 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的前序與中序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一，因此 T 也為唯一的二元樹。
:::
---
### 20. 二元樹中的中序和階層順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其階層順序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由階層順序與中序可以得到唯一的二元樹。
推論：使 T 為一個有 $n$ 個節點的樹，使它的階層順序與中序分別為 $l_1, l_2, ..., l_n$ 和 $i_1, i_2, …, i_n$，階層順序的第一個元素為樹根，也就是 $l_1$，找到 $l_1$ 在中序中的位置，稱之為 $i_k$，因此，$(i_1, i_2, ..., i_{k-1})$ 與其對應的階層順序元素為 T 的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$與其對應的階層順序元素為 T 的右子樹。
T 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的中序與階層順序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一因此 T 也為唯一的二元樹。
:::
---
### 21. 寫一個演算法，以所提供的前序和中序順序，建立出對應的二元樹。
:::spoiler
```cpp=
struct BTreeNode * BTree_InfixPrefix ( String infix , String prefix )
{ int k;
struct BTreeNode * node;
if (infix.Length == 0) return NULL;
node = (struct BTreeNode *) malloc (sizeof(struct BTreeNode));
node->data = prefix[1];
k = find(prefix[1], infix);
node->leftchild = BTree_InfixPrefix (infix[1,k-1], prefix[2,k-1]);
node->rightchild = BTree_InfixPrefix (infix[k+1,infix.Length-k],prefix[k+1,prefix.Length-k]);
return node;
}
```
:::
---
### 22. 請証明 $N(h) = F_{h+2}−1，h ≥ 0$。（提示：$F_{0} = 0, F_1=1, F_n=F_{n-1}+F_{n-2}$；數學歸納法）
:::spoiler
基礎：高度為 0 時，為一空樹，最少 0 個節點即可，$F_{0+2}−1 = F_2−1 = 1−1 = 0$，原式成立。
(若原題條件為 $h≥1$，則
基礎：高度為 1 時，為含唯一節點(樹根)的樹，最少正是 1 個節點，$F_{1+2}−1 = F_3−1 = 2−1 = 1$，原式成立。)
假設：高度小於等於 $h−1$ 時該式成立。
推論：考慮高度等於 $h$ ，最少節點數 $N(h)$ 必定發生在「樹根」之左右子樹高度相差1時；不失一般性，令左子樹高度為 $h−1$；右子樹高度為 $h−2$。所以左子樹最少節點個數為 $F_{(h−1)+2}−1 = F_{h+1}−1$；右子樹最少節點個數為$F_{(h−2)+2}−1 = F_h−1$。
整棵樹需要最少的節點數為 $N(h) = F_{h+1}−1 + F_h−1 + 1 = F_{h+2}−1$。
基於數學歸納法原理可知原式得証。
:::
---
### 23. 實作程式 5-23 新增資料至 AVL 樹中。
:::spoiler
程式 5-23 已編譯正確。
:::
---
### 24. 實作程式 5-24 自 AVL 樹中刪除資料；並請舉例說明程序 DeleteAVLTree可能執行一次以上的旋轉以保持樹的平衡。
:::spoiler
程式 5-24 已編譯正確。
```cpp=
20 //刪除節點30
/ \
15 25
/ \ \
10 17 30
/
16
==> 20 //對節點15做左旋轉
/ \
15 25
/ \
10 17
/
16
==> 20 //對節點20做右旋轉
/ \
17 25
/
15
/ \
10 16
==> 17 //完成->共計2次旋轉
/ \
15 20
/ \ \
10 16 25
```
:::
---
Sign in with Wallet
Connect another wallet