关于第四章：
第四章讲的是树，属于图类的一个分支。
术在包括查找、编译器、数据库方面都有很多很大的用途，也是一类非常基础的数据结构。
笔记：
一棵树就是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深度的节点。