Scott's world.

第四讲-树-中

Word count: 1.3kReading time: 6 min
2019/07/05 Share

第四讲 树(中)

二叉搜索树

二叉搜索树常用操作

Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//伪代码
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;
}

查找最大元素和最小元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//伪代码
Position FindMin(BinTree BST)
{
if(!BST) return NULL;
else if (!BST->Left) return BST; /*找到最左叶结点并返回*/
else return FindMin(BST->Left); //沿左分支继续查找
}

Positon FindMax(BinTree BST)
{
if(BST)
while(BST->Right) BST=BST->Right; //沿右分支继续查找直至最右叶结点
return BST;
}
Insert

与Find操作的递归相似,若比该结点小则插入左子树,若比比该结点大则插入右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//伪代码
BinTree Insert(ElementType X,BinTree BST)
{
if(!BST)
{
BST = malloc(sizeof(struct TreeNode));
BST->data=X;
BST->Left=BST->Right=NULL;
}else
{
if(X<BST->data) BST->Left=Insert(X,BST->Left);
else if(X>BST->data) BST->Right=Insert(X,BST->Right);
}
return BST;
}
Delete

主要考虑三种情况:

  • 删除叶结点:直接删除,并再修改其父结点指针置为NULL
  • 删除只有一个孩子结点的结点:将其父结点的指针指向要删除结点的孩子结点
  • 删除有左右子树的结点:取右子树的最小元素(最多只有一个孩子结点)替代或者取左子树中的最大元素替代(无孩子结点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//伪代码
BinTree Delete(ElementType X,BinTree BST)
{
Position Temp;
if(!BST) count<<"Not Found"<<endl;
else if(X<BST->data) BST->Left=Delte(X,BST->Left); //根据大小在左子树递归删除
else if(X>BST->data) BST->Right=Delete(X,BST->Right);//根据大小在右子树递归删除
else //找到要删除的结点
{
//有左右子树的结点
if(BST->Left && BST->Right)
{
//取该结点右子树最小元素
Temp=FindMin(BST->Right);
BST->data=Temp->data;
//删除该结点的右子树中最小元素
BST->Right=Delete(BST->data,Right);
}
else //被删除的结点有一个或无孩子结点
{
Temp=BST;
if(!BST->Left) //有右孩子或无子结点
BST=BST->Right;
else if(!BST->Right) //有左孩子或无子结点
BST=BST->Left;
free(Temp);
}
}
return BST;
}

平衡二叉树

不同的插入次序,将导致不同的深度平均查找长度ASL

平衡二叉树的调整

RR旋转插入

LL旋转插入

LR旋转插入

RL旋转插入

应用:是否同一棵二叉搜索树

求解思路

  • 分别建两棵搜索树的判别方法

    根据两个序列分别建树,再判断树是否一样

  • 不建树的判别方法

    先与头结点相比,然后将剩下的序列按与头结点大小比较分成两个序列,然后再根据这个两个序列分别比较,然后递归下去

  • 建一棵树,再判断其他序列是否与该树一致

    如果每次搜索所经过的结点在前面均出现过,则一致

    否则(某次搜索中遇到前面未出现的结点),则不一致

需要解决的问题:

1.搜索树表示

2.建搜索树T

3.判别一序列是否与搜索树T一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
typedef struct TreeNode * Tree;
struct TreeNode{
int v;
Tree Left,Right;
int flag;
}

int main()
{
int N,L,i;
Tree T;

scanf("%d",&N);
while(N){
scanf("%d",&L);
T=MakeTree(N);
for(i=0;i<L;i++)
{
if(Judge(T,N)) printf("Yes\n");
else print("No\n");
ResetT(T);
}
FreeTree(T);
scanf("%d",&N);
}
return 0;
}

Tree MakeTree(int N)
{
Tree T;
int i,V;

scanf("%d",&V);
T=NewNode(V); //创建头结点
for(i=1;i<N;i++)
{
scanf("%d",&V);
T=Insert(T,V);//插入进树中
}
return T;
}

Tree NewNode(int V)
{
Tree T=(Tree)malloc(sizeof(struct TreeNode));
T->v=V;
T->Left=T->Right=NULL;
T->flag=0;
return T;
}

Tree Insert(Tree T,int V)
{
if(!T) T=NewNode(V);
else{
if(V>T->v)
T->Right = Insert(T->Right,V);
else
T->Left = Insert(T->Left,V);
}
return T;
}

int check(Tree T,int V)
{
if(T->flag){
if(V<T->v) return check(T->Left,V);
else if(V>T->v) return check(T->Right,V);
else return 0;
}else{
if(V==T->v){
T->flag=1;
return 1;
}
else return 0;
}
}

int Judge(Tree T,int N)
{
int i,V,flag=0;
scanf("%d",&V);
if(V!=T->v)flag=1;
else T->flag=1;
for(i=1;i<N;i++)
{
scanf("%d",&V);
if((!flag)&& !check(T,V)) flag=1;
}
if(flag) return 0;
return 1;
}

//清除T中的flag标志
void ResetT(Tree T)
{
if(T->Left) ResetT(T->Left);
if(T->Right) Reset(T->Right);
T->flag=0;
}

//释放T的空间
void FreeTree(Tree T)
{
if(T->Left) FreeTree(T->Left);
if(T->Right) FreeTree(T->Right);
free(T);
}
CATALOG
  1. 1. 第四讲 树(中)
    1. 1.1. 二叉搜索树
      1. 1.1.0.1. 二叉搜索树常用操作
        1. 1.1.0.1.1. Find
        2. 1.1.0.1.2. Insert
        3. 1.1.0.1.3. Delete
  2. 1.2. 平衡二叉树
    1. 1.2.1. 平衡二叉树的调整
      1. 1.2.1.0.1. RR旋转插入
      2. 1.2.1.0.2. LL旋转插入
      3. 1.2.1.0.3. LR旋转插入
      4. 1.2.1.0.4. RL旋转插入
  • 1.3. 应用:是否同一棵二叉搜索树
    1. 1.3.1. 求解思路