ZJU_DS_04-树（中）

前面学习了树的基本术语、性质，以及二叉树的形态、遍历方法等，这次会继续学习两种“新”二叉树

Binary Search Tree

定义

二叉搜索树（BST，Binary Search Tree），也成为二叉排序树或二叉查找树。
二叉搜索树：前提得是一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左、右子树都是二叉搜索树

特别函数

二叉搜索树本质上还是二叉树，所以其抽象数据类型描述与二叉树是一致的，但操作集存在差异，多了几个特别函数：

1. Position Find(ElementType X, BinTree BST)，从二叉搜索树BST中查找元素X，返回其所在结点的地址
2. Position FindMin(BinTree BST)，从二叉搜索树BST中查找并返回最小元素所在结点的地址
3. Position FindMax(BinTree BST)，从二叉搜索树BST中查找并返回最大元素所在结点的地址
4. BinTree Insert(ElementType X, BinTree BST)，向二叉搜索树中插入结点
5. BinTree Delete(ElementType X, BinTree BST)，在二叉搜索树中删除结点

下面以二叉树的链式存储结构为准，完成几个常用的特别函数。

查找

查找函数的实现思路比较直接，按照二叉搜索树的性质，比根结点小则在左子树中查找，比根节点大则在右子树中查找，循环这个过程即可。

递归

Position Find(ElementType X, BinTree BST) {
    if(!BST) return NULL;
    if(X > BST->Data) return Find(X, BST->Right);
    else if(X < BST->Data) return Find(X, BST->Left);
    else return BST;
}

非递归

Position IterFind(ElementType X, BinTree BST) {
    while(BST) {
        if(X > BST->Data) BST = BST->Right;
        else if(X < BST->Data) BST = BST->Left;
        else return BST;
    }
    return NULL;
}

查找最值

有了前面查找的思路后，根据 BST 的性质，直接查找最值的函数也很容易得到。

递归

Position FindMax(BinTree BST) {
    if(!BST) return NULL;
    else if(!BST->Right) return BST;
    else FindMin(BST);
}

Position FindMin(BinTree BST) {
    if(!BST) return NULL;
    else if(!BST->Left) return BST;
    else FindMin(BST);
}

非递归

Position FindMax(BinTree BST) {
    if(BST) {
        while(BST->Right) BST = BST->Right;
    }
    return BST;
}

Position FindMin(BinTree BST) {
    if(BST) {
        while(BST->Left) BST = BST->Left;
    }
    return BST;
}

插入

插入的关键在于先确定好插入的位置，既然要确定位置，那么就可以借助查找的思路。

递归

BinTree Insert( BinTree BST, ElementType X ) {
    if(!BST) {
        BST = (struct TNode*)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else {
        if(X < BST->Data) BST->Left = Insert(BST->Left, X);
        else if(X > BST->Data) BST->Right = Insert(BST->Right, X);
    }
    return BST;
}

非递归

BinTree Insert( BinTree BST, ElementType X ) {
    if(!BST) {
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else {
        Position pre, t;
        t = BST; 
        while(t) {
            pre = t;
            if(X > t->Data) t = t->Right;
            else if(X < t->Data) t = t->Left;
        }
        struct TNode *tmpnode = (struct TNode*)malloc(sizeof(struct TNode));
        tmpnode->Data = X;
        tmpnode->Left = tmpnode->Right = NULL;
        if(X < pre->Data) {
            pre->Left = tmpnode;
        } else if(X > pre->Data) {
            pre->Right = tmpnode;
        }
    }
    return BST;
}

删除

删除的思路与插入的思路也类似，还是需要先找删除的位置。但是针对删除结点的不同（叶结点和非叶结点），需要分别考虑。如果删除的是叶结点，那么可以直接删除；但若删除非叶结点，就需要在删除这个结点后，用另一结点替代被删除结点，这样才不会使链式结构断裂。

对于度为 1 的被删除结点，另一结点直接使用其子结点即可；对于度为 2 的被删除结点，另一结点可以用其右子树的最小元素或者其左子树的最大元素，之所要用这两个结点，因为这两个结点一定是叶结点，可以直接拿掉。

BinTree Delete( BinTree BST, ElementType X ) {
    Position tmp;
    if(!BST) printf("Not Found\n");
    else if(X < BST->Data) BST->Left = Delete(BST->Left, X);
    else if(X > BST->Data) BST->Right = Delete(BST->Right, X);
    else {
        if(BST->Left && BST->Right) {
            /* method 1: use the minium node of right subtree
			
			tmp = FindMin(BST->Right);
			BST->Data = tmp->Data;
			BST->Right = Delete(BST->Right, BST->Data); 
			
			*/
            /* method 2: use the maximum node of left subtree */
            tmp = FindMax(BST->Left);
            BST->Data = tmp->Data;
            BST->Left = Delete(BST->Left, BST->Data);
        } else {
            tmp = BST;
            if(!BST->Left) BST = BST->Right;
            else BST = BST->Left;
            free(tmp); 
        }
    }
    return BST;
}

Balanced Tree

平衡二叉树需要引入平衡因子的概念，其解决了二叉搜索树中出现“单枝树”而导致查找效率过低的树形结构问题。

平衡因子（Balance Factor，BF）：$BF(T) = h_l - h_r$，其中$h_l$和$h_r$分别为树 T 的左右子树高度。

定义

平衡二叉树（Balanced Tree，也叫 AVL 树）:空树，或者任何一结点左右子树高度差的绝对值不超过 1，即$|BF(T)| \le 1$。

调整

平衡二叉树的结构调整情况有以下四种情况，关键在于观察离破坏者最近的被破坏者和破坏者之间的位置关系。
但是要注意有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子。

• RR
• LL
• LR
• RL

RR旋转（虽然叫 RR 旋转，但是实际过程是左旋），破坏者位于被破坏者的右子树的右子树下。

Tree RRrotate(Tree root) {
    PtrToTNode t = root->rchild;
    root->rchild = t->lchild;
    t->lchild = root;
    t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
    root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
    return t;
}

LL旋转（虽然叫 LL 旋转，但是实际过程是右旋），破坏者位于被破坏者的左子树的左子树下。

Tree LLrotate(Tree root) {
    PtrToTNode t = root->lchild;
    root->lchild = t->rchild;
    t->rchild = root;
    t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
    root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
    return t;
}

LR旋转（与名称一致，先左旋后右旋），破坏者位于被破坏者的左子树的右子树下。

Tree LRrotate(Tree root) {
    root->lchild = RRrotate(root->lchild);
    return LLrotate(root);
}

RL旋转（与名称一致，先右旋后左旋），破坏者位于被破坏者的右子树的左子树下。

Tree RLrotate(Tree root) {
    root->rchild = LLrotate(root->rchild);
    return RRrotate(root);
}

Homework

04-4 是否同一棵二叉搜索树

这道题与树的同构有点像，下面的代码包含两种做法：

1. 构造两棵树，判断两棵树是否一致
2. 只构造一棵树，判断给定序列顺序是否与树的结点序列一致

/* method 1: use recursion to judge two trees is same or not */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TNode{
    int data;
    struct TNode *left, *right;
};
typedef struct TNode* PtrToTNode;
typedef PtrToTNode Tree;
PtrToTNode createnode(int data) {
    PtrToTNode t = (PtrToTNode)malloc(sizeof(struct TNode));
    t->left = t->right = NULL;
    t->data = data;
    return t;
}
Tree insert(Tree root, int data) {
    if(!root) root = createnode(data);
    else if(data < root->data) root->left = insert(root->left, data);
    else if(data > root->data) root->right = insert(root->right, data);
    return root;
}
bool issame(Tree root1, Tree root2) {
    if(!root1 && !root2) return true;
    else if((!root1 && root2) && (root1 && !root2)) return false;
    else {
        if(root1->data != root2->data) return false;
        else return issame(root1->left, root2->left) && issame(root1->right, root2->right);
    }
}
void destorytree(Tree root) {
    if(root->left) destorytree(root->left);
    if(root->right) destorytree(root->right);
    free(root);
}
int main() {
    int n, l;
    scanf("%d", &n);
    while(n) {
        scanf("%d", &l);
        Tree root1 = NULL;
        int i, data;
        for(i = 0; i < n; i++) {
            scanf("%d", &data);
            root1 = insert(root1, data);
        }
        while(l--) {
            Tree root2 = NULL;
            for(i = 0; i < n; i++) {
                scanf("%d", &data);
                root2 = insert(root2, data);
            }
            if(issame(root1, root2)) printf("Yes\n");
            else printf("No\n");
            destorytree(root2);
        }
        scanf("%d", &n);
        if(n == 0) destorytree(root1);
    }
    return 0;
}

/* method 2: constitute a tree, check the path of visiting everynodes is same
or not 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node{
	int flag, data;
	struct node *left, *right;
};
typedef struct node* Tree;
typedef struct node* PtrToTNode;
PtrToTNode newnode(int data) {
	PtrToTNode t = (PtrToTNode)malloc(sizeof(struct node));
	t->data = data;
	t->flag = 0;
	t->left = t->right = NULL;
	return t;
}
Tree insert(Tree root, int data) {
	if(!root) root = newnode(data);
	else if(data > root->data) root->right = insert(root->right, data);
	else if(data < root->data) root->left = insert(root->left, data);
	return root;
}
Tree buildtree(int n) {
	int i, data;
	Tree root = NULL;
	for(i = 0; i < n; i++) {
		scanf("%d", &data);
		root = insert(root, data);
	}
	return root;
}
bool check(Tree root, int data) {
	if(root->flag) {
		if(data < root->data) return check(root->left, data);
		else if(data > root->data) return check(root->right, data);
		else return false;
	} else {
		if(data == root->data) {
			root->flag = 1;
			return true;
		} else return false;
	}
}
bool judge(Tree root, int n) {
	int i, data;
	bool flag = false;
	scanf("%d", &data);
	if(data != root->data) flag = true;
	else root->flag = 1;
	for(i = 1; i < n; i++) {
		scanf("%d", &data);
		if(!flag && !check(root, data)) flag = 1;
	}
	return !flag;
}
void reset(Tree root) {
	if(root->left) reset(root->left);
	if(root->right) reset(root->right);
	root->flag = 0;
}
void destorytree(Tree root) {
	if(root->left) destorytree(root->left);
	if(root->right) destorytree(root->right);
	free(root);
}
int main() {
	int n, l, i;
	while(scanf("%d", &n) && n) {
		scanf("%d", &l);
		Tree root = buildtree(n);
		while(l--) {
			if(judge(root, n)) printf("Yes\n");
			else printf("No\n");
			reset(root);
		}
		destorytree(root);
	}
	return 0;
} 

*/

04-5 Root of AVL Tree

这道题就是何老师讲的平衡二叉树的四种旋转方式，题目一次将四种旋转方式全部考察到了，出的很好。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TNode{
    int data, height;
    struct TNode *lchild, *rchild;
};
typedef struct TNode* PtrToTNode;
typedef PtrToTNode Tree;
int max(int a, int b) {
    return a > b ? a : b;
}
int getheight(Tree root) {
    if(!root) return -1;
    else return root->height;
}
Tree RRrotate(Tree root) {
    PtrToTNode t = root->rchild;
    root->rchild = t->lchild;
    t->lchild = root;
    t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
    root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
    return t;
}
Tree LLrotate(Tree root) {
    PtrToTNode t = root->lchild;
    root->lchild = t->rchild;
    t->rchild = root;
    t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
    root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
    return t;
}
Tree RLrotate(Tree root) {
    root->rchild = LLrotate(root->rchild);
    return RRrotate(root);
}
Tree LRrotate(Tree root) {
    root->lchild = RRrotate(root->lchild);
    return LLrotate(root);
}
Tree insert(Tree root, int data) {
    if(!root) {
        root = (Tree)malloc(sizeof(struct TNode));
        root->lchild = root->rchild = NULL;
        root->data = data;
        root->height = 0;
    } else if(data > root->data) {
        root->rchild = insert(root->rchild, data);
        if(getheight(root->rchild) - getheight(root->lchild) == 2) {
            if(data > root->rchild->data) root = RRrotate(root);
            else root = RLrotate(root);
        } 
    } else if(data < root->data) {
        root->lchild = insert(root->lchild, data);
        if(getheight(root->lchild) - getheight(root->rchild) == 2) {
            if(data < root->lchild->data) root = LLrotate(root);
            else root = LRrotate(root);
        }
    }
    root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
    return root;
}
int main() {
    int i, n, data;
    scanf("%d", &n);
    Tree root = NULL;
    for(i = 0; i < n; ++i) {
        scanf("%d", &data);
        root = insert(root, data);
    }
    printf("%d", root->data);
    return 0;
}

04-6 Complete Binary Search Tree

这道题很有难度，要对完全二叉树、二叉查找树及二叉树的遍历有较深的理解才能解出来，不过解不出来也没事，姥姥后面会讲。

#include <stdio.h>
#include <stdlib.h>
#define maxn 1005
int n, tree[maxn], seq[maxn], inde = 0;
void inorder(int root) {
    if(root > n) return;
    inorder(2 * root);
    tree[root] = seq[inde++];
    inorder(2 * root + 1);
}
int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
int main() {
    scanf("%d", &n);
    int i;
    for(i = 0; i < n; ++i) {
        scanf("%d", &seq[i]);
    }
    qsort(seq, n, sizeof(seq[0]), cmp);
    inorder(1);
    for(i = 1; i <= n; ++i) {
        printf("%d", tree[i]);
        if(i < n) printf(" ");
    }
    return 0;
}

04-7 二叉搜索树的操作集

这道题目是用来测试二叉搜索树常用操作的，可以尝试多种不同的写法来提交来验证是否正确。

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT );
void InorderTraversal( BinTree BT );

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}
void PreorderTraversal( BinTree BT ) {
    if(!BT) return;
    printf("%d ", BT->Data);
    PreorderTraversal(BT->Left);
    PreorderTraversal(BT->Right);
}
void InorderTraversal( BinTree BT ) {
    if(!BT) return;
    InorderTraversal(BT->Left);
    printf("%d ", BT->Data);
    InorderTraversal(BT->Right);
}
BinTree Insert( BinTree BST, ElementType X ) {
    /* method 1: use recursion 
	
	if(!BST) {
		BST = (struct TNode*)malloc(sizeof(struct TNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {
		if(X < BST->Data) BST->Left = Insert(BST->Left, X);
		else if(X > BST->Data) BST->Right = Insert(BST->Right, X);
	}
	return BST;
	*/
    /* method 2: use loop */
    if(!BST) {
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else {
        Position pre, t;
        t = BST; 
        while(t) {
            pre = t;
            if(X > t->Data) t = t->Right;
            else if(X < t->Data) t = t->Left;
        }
        struct TNode *tmpnode = (struct TNode*)malloc(sizeof(struct TNode));
        tmpnode->Data = X;
        tmpnode->Left = tmpnode->Right = NULL;
        if(X < pre->Data) {
            pre->Left = tmpnode;
        } else if(X > pre->Data) {
            pre->Right = tmpnode;
        }
    }
    return BST;
}
BinTree Delete( BinTree BST, ElementType X ) {
    Position tmp;
    if(!BST) printf("Not Found\n");
    else if(X < BST->Data) BST->Left = Delete(BST->Left, X);
    else if(X > BST->Data) BST->Right = Delete(BST->Right, X);
    else {
        if(BST->Left && BST->Right) {
            /* method 1: use the minium node of right subtree
			
			tmp = FindMin(BST->Right);
			BST->Data = tmp->Data;
			BST->Right = Delete(BST->Right, BST->Data); 
			
			*/
            /* method 2: use the maximum node of left subtree */
            tmp = FindMax(BST->Left);
            BST->Data = tmp->Data;
            BST->Left = Delete(BST->Left, BST->Data);
        } else {
            tmp = BST;
            if(!BST->Left) BST = BST->Right;
            else BST = BST->Left;
            free(tmp); 
        }
    }
    return BST;
}
Position Find( BinTree BST, ElementType X ) {
    /* method 1: use recursion
	
	if(!BST) return NULL;
	if(X > BST->Data) return Find(BST->Right, X);
	else if(X < BST->Data) return Find(BST->Left, X);
	else return BST;
	
	*/
    /* method 2: use loop*/
    while(BST) {
        if(X > BST->Data) BST = BST->Right;
        else if(X < BST->Data) BST = BST->Left;
        else break;
    }
    return BST;
}
Position FindMin( BinTree BST ) {
    /* method 1: use recursion
	
	if(!BST) return NULL;
	else if(!BST->Left) return BST;
	else return FindMin(BST->Left);
	
	*/
    /* method 2: use loop, but need use if to avoid segmentation fault */
    if(BST)	while(BST->Left) BST = BST->Left;
    return BST;
}
Position FindMax( BinTree BST ) {
    /* method 1: use recursion
	
	if(!BST) return NULL;
	else if(!BST->Right) return BST;
	else return FindMax(BST->Right);
	
	*/
    /* method 2: use loop, but need use if to avoid segmentation fault */
    if(BST) while(BST->Right) BST = BST->Right;
    return BST;
}

/*
samples:
in:
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3

out:
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9
*/

---