關于第四章：
第四章講的是樹，屬于圖類的一個分支。
術在包括查找、編譯器、資料庫方面都有很多很大的用途，也是一類非常基礎的資料結構。
筆記：
一棵樹就是N個節點和N－1條邊的集合。
周遊方式：
(1)先序周遊：父節點在其兒子節點之前處理。
(2)後序周遊：父節點在其兒子節點之後處理。
(3)中序周遊：先周遊左子樹，再周遊根，最後周遊右子樹。
(4)層序周遊：在D深度的節點要在D＋1深度的節點之前處理。
二叉樹：
二叉樹是一棵樹，其中每個節點不能有多于兩個兒子。
struct TreeNode {
ElemType Data;
Tree Left;
Tree Right;
};
具有N個節點的每一棵二叉樹都需要N＋1個NULL指針。
查找二叉樹：
對于樹中的每個節點X，它的左子樹的關鍵字值少于X的關鍵字值，而它的右子樹的關鍵字值大于X的關鍵字值。
在實作中，要注意的是MakeEmpty和Delete兩個函數：
Tree MakeEmpty(Tree T)
{
if (T != NULL) {
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
在MakeEmpty中，後序周遊是必要的，否則實作錯誤。
Position Delete(Tree T,ElemType Search)
{
Position Target;
if (T == NULL)
return NULL;
else if (Search < T->Data)
T->Left = Delete(T->Left,Search);
else if (Search > T->Data)
T->Right = Delete(T->Right,Search);
else {
if (T->Left && T->Right) { // two child
Target = FindMin(T->Right);
T->Data = Target->Data;
T->Right = Delete(T->Right,T->Data);
}
else { // one child
Target = T;
if (T->Left == NULL)
T = T->Right;
else if (T->Right == NULL)
T = T->Left;
free(Target);
}
}
}
而在delete函數中，删除兩兒子節點的時候，先是将T節點和T的右子樹的最小值節點進行了移位，而真正的删除在完成移位之後遞歸進行，是以無須free調用。
而“真正的删除”到one child的情況才進行。
另外因為這種删除方式可能造成樹的不平衡，如果追求平衡，可以用随機删除右節點的最小值或左節點的最大值來保持平衡。
AVL樹：
平衡樹的出現避免了二叉樹深度過深的情況。
AVL樹是其每個節點的左子樹和右子樹的高度最多差1的二叉樹。
AVL樹的難點自然是平衡的保持，這要通過旋轉來達到。
書上AVL章節的前邊部分，描述得比較抽象，看得我一頭霧水，翻到後面看見代碼之後，豁然開朗。
強烈建議不了解的不要死讀描述(像我)，直接跳到後面看代碼就好。
Tree Insert(Tree T,ElemType Input)
{
if (T == NULL) {
T = malloc(sizeof(struct TreeNode));
T->Data = Input;
T->Height = 0;
T->Left = T->Right = NULL;
}
else if (Input < T->Data) {
T->Left = Insert(T->Left,Input);
// rotate
if ((Height(T->Left) - Height(T->Right)) == 2)
if (Input < T->Left->Data)
T = SingleLeft(T);
else
T = DoubleLeft(T);
}
else if (Input > T->Data) {
T->Right = Insert(T->Right,Input);
// rotate
if ((Height(T->Right) - Height(T->Left)) == 2)
if (Input > T->Right->Data)
T = SingleRight(T);
else
T = DoubleRight(T);
}
T->Height = Max(Height(T->Left),Height(T->Right)) + 1;
return T;
}
static Tree SingleLeft(Tree K2)
{
Position K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
K2->Height = Max(Height(K2->Left),Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left),Height(K1->Right)) + 1;
return K1;
}
static Tree DoubleLeft(Tree K3)
{
K3->Left = SingleRight(K3->Left);
return SingleLeft(K3);
}
static Tree SingleRight(Tree K2)
{
Position K1;
K1 = K2->Right;
K2->Right = K1->Left;
K1->Left = K2;
K2->Height = Max(Height(K2->Left),Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left),Height(K1->Right)) + 1;
return K1;
}
static Tree DoubleRight(Tree K3)
{
K3->Right = SingleLeft(K3->Right);
return SingleRight(K3);
}
課後練習：
4。8
(a) - * * a b + c d e
(b) ( ( a * b ) * ( c + d ) ) - e
(c) a b * c d + * e -
4。13
(1)c
(2)a
4。15
(a)(a) N (0) = 1, N (1) = 2, N (H ) = N (H −1) + N (H −2) + 1.
這個在書本80頁有談到。
4。20
執行二叉樹式的删除之後，再使用旋轉來保持删除某節點後的平衡，跟插入對比，删除需要更多的旋轉操作。
4。22
這裡答案錯誤了，是return k2才對。
這種操作的清晰性比執行兩個單旋轉來得清晰，我覺得。XD
Position
DoubleRotateWithLeft( Position K3 )
{
Position K1, K2;
K1 = K3->Left;
K2 = K1->Right;
K1->Right = K2->Left;
K3->Left = K2->Right;
K2->Left = K1;
K2->Right = K3;
K1->Height = Max( Height(K1->Left), Height(K1->Right) ) + 1;
K3->Height = Max( Height(K3->Left), Height(K3->Right) ) + 1;
K2->Height = Max( K1->Height, K3->Height ) + 1;
return K2; // 書本的這裡錯了
}
4。32
這題很簡單，可我沒做出來。。。
void
PrintRange( ElementType Lower, ElementType Upper, SearchTree T )
{
if( T != NULL )
{
if( Lower <= T->Element )
PrintRange( Lower, Upper, T->Left );
if( Lower <= T->Element && T->Element <= Upper )
PrintLine( T->Element );
if( Upper >= T->Element )
PrintRange( Lower, Upper, T->Right );
}
}
4。35
這道題使用隊列，對二叉樹實行層序周遊：
将同一深度的節點放到隊列裡(比如深度D)，處理完後再Dequeue出去，然後再處理D＋1深度的節點。