By

文章目录

如果数据集是普通的顺序存储，即整个数据表无序存储。那么插入操作就是放在表的末端，表元素个数加1即可。删除操作可以是删除后，后面的元素前移。或者是待删除元素与末尾元素互换，同时表元素个数减一。但是表无序造成的查找效率很低。
如果查找的数据表是有序线性表，并且是顺序存储的，查找可以用折半，插值等算法实现，但是因为数据表有序，导致插入和删除操作，需要消耗大量的时间。
那么我们希望找到一种数据结构，可以使得插入和删除效率不错，同时可以满足高效率的查找操作。
二叉排序树就可以满足这个要求，二叉排序树又称为二叉查找树，它或者是一棵空树，或者满足下列性质：
1.若它的左子树不空，则左子树所有节点的值均小于根节点的值。
2.若它的右子树不空，则右子树所有节点的值均大于根节点的值。
3.它的左右子树也分别是二叉排序树。
二叉排序树非线性的结构，有利于插入和删除的实现。当对它进行中序遍历时，就可以得到有序的序列。
为了详细说明二叉树，我们先提供一个二叉树的结构。

1
2
3
4
5
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

这种用法的意思是给struct BitNode取别名位BitNode，给struct BitNode *取别名为BitTree，所以BitTree声明的变量是一个指针。
下面来说明下二叉排序树的查找的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status SearchBst(BiTree T,int key,BiTree f,BiTree *p){
	if(!T){
		/*查找不成功*/
		*p = f;
		return FALSE;
	}
	else if(key = T->data)
	{
		*p = T;
		return TRUE;
	}
	else if(key<T->data)
		return SearchBST(T->lchild,key,T,p);
	else
		return SearchBST(T->rchild,key,T,p);
}

SearchBST函数是一个可递归运行的函数，key代表要查找的关键字，二叉树f指向T的双亲，当T指向根节点时，f的初值就为NULL,它在递归时有用，最后的参数p是为了查找成功后可以得到查找到的结点位置。
二叉排序树的插入操作需要借助查找操作，插入就是将关键字放到树中的合适位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status InsertBST(BiTree *T ,int key)
{
	BiTree p,s;
	if(!SearchBST(*T,key,NULL,&p))
	{
		s = （BiTree）malloc(sizeof(BiTnode));
		s->data = key;
		s->lchild = s->rchild = NULL;
		if(!p)//树为空
		{
			*T = s;
		}
		else if(key<p->data){
		p->lchild = s;
		}
		else
			p->rchild = s;
		return TRUE;
	}
	else return FALSE;
}

二叉树的构建就是利用循环逐步插入节点生成二叉排序树。
二叉树对于插入和查找都很方便，但是为了满足二叉树节点删除后，仍满足二叉树的特性，因此删除节点需要考虑多种情况。
1.删除叶子节点。删除叶子节点对整棵树的其它节点结构没有影响，直接删除即可。
2.要删除的节点只有左子树或者右子树的情况，将节点删除后，将它的左子树或者右子树整个移动到删除节点的位置。
3.对于要删除的节点，既有左子树也有右子树的情况，可以找一个节点代替被删除节点的位置。当该节点是与被删除节点大小最相近的节点时，整个树结构不改变。即该节点可以是待删除节点左子树的最右节点，或者是右子树的最左节点。也同样是中序遍历中与删除节点相邻的节点。

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
Status DeleteBST(BiTree *T ,int key)
{
	if(!*T)
		return FALSE;
	else
	{
		if(key == (*T)->data)
			return Delete(T);
		else if(key < (*T)->data)
			return DeleteBST(& (*T)->lchild,key);
		else
			return DeleteBST(&(*T)->rchild,key);
	}
}
status Delete(BiTree *p)
{
	BiTree q,s;
	if((*p)->rchild == NULL)
	{
		q = *p;
		*p = (*p)->lchild;
		free(q); 
	}
	else if((*p)->lchild == NULL)
	{
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}
	else
	{
		q = *p;
		s = (*p) ->lchild;
		while(s->rchild)
		{
			q =s;
			s = s->rchild;
		}	
		(*p)->data = s->data;
		if(q!=*p)
			q->rchild = s->lchild;
		else//p的左孩子没有右孩子
			q->lchild = s->lchild;
	}
}

二叉排序树以链接形式存储，在插入和删除过程中，不需要移动元素，只要修改链接指针即可。对于查找来说，走的就是从根节点到要查找的节点的路径，比较次数等于节点在树中的层数。因此降低二叉树的深度有利于查找节点。也就是将二叉树构建成平衡二叉树。
平衡二叉树是二叉排序树的一种，其中每个节点的左子树和右子树的高度差至多等于1.空树也是平衡二叉树的一种。二叉树节点的左子树深度减去右子树深度的值称为平衡因子bf。若bf>1，则二叉树不平衡。
距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，为最小不平衡子树。平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每插入一个节点时，先检查是否因为插入节点而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树各节点的链接关系，进行相应的旋转，使之成为新的平衡子树。
平衡二叉树相对于二叉排序树，需要增加bf，用于存储平衡因子。

1
2
3
4
5
6
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild,*rchild;
	int bf;
}BiTNode,*BiTree;

平衡二叉树，就是在二叉排序树的创建过程中保持它的平衡性，一旦有不平衡的情况，马上处理，当一个节点的bf为正时，进行右旋操作，为负时，进行左旋操作。当该节点与其子节点bf值符号不一致时，先处理子节点。
右旋操作代码如下,其中p是指要右旋处理的树的根节点：

1
2
3
4
5
6
7
8
void R_Rotate(BiTree *p)
{
	BiTree L;
	L = (*p) ->lchild;
	(*p)->lchild = L->rchild;
	L->rchild = (*p);
	*p = L;
}

左旋操作和右旋操作对称，代码如下：

1
2
3
4
5
6
7
8
void L_Rotata(BiTree *p)
{
	BiTree R;
	R = (*p)->rchild;
	(*p) ->rchile = R->lchild;
	R->lchild = (*p);
	*p = R;
}

下面是左平衡旋转处理的代码，也就是当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
#define LH +1
#define EH 0
#define RH -1
void LeftBalance(BiTree *T)
{
	BiTree L,Lr;
	L = (*T)->lchild;
	switch(L->bf)
	{
		case LH://新节点插入在T的左孩子的左子树上，双旋
			(*T)->bf = L->bf = EH;
			R_Rotate(T);
			break;
		case RH://新节点插入在T的左孩子的右子树上，双旋
			Lr = L->rchild;/*Lr指向T的左孩子的右子树根*/
			switch(Lr->bf)
			{
				case LH:
				(*T)->bf = RH;
				L->bf = EH;
				break;
				case EH:
				(*T)->br = L->br = EH;
				break;
				case RH:
				(*T)->bf = EH;
				L->bf = LH;
				break;
			}
			Lr->bf = EH;
			L->Rotate(&(*T)->lchild);
			R_Rotate(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
Status InsertAVL(BiTree *T,int e,Status *taller)
{
	if(!*T)
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = e;
		(*T)->lchild = (*T)->rchild = NULL;
		(*T)->bf=EH;
		*taller = TRUE;
	}
	else
	{
		if(e==(*T)->data)
		{
			*taller = FALSE;
			return FALSE;
		}
		if(e<(*T)->data)
		{
			if(!InsertAVL(&(*T)->lchild,e,taller))
				return FALSE;
			if(*taller)
			{
				switch((*T)->bf)
				{
				case LH:
					LeftBalance(T);
					*taller = FALSE;
					break;
				case EH:
					(*T)->bf=LH;
					*taller = TRUE;
					break;
				case RH:
					(*T)->bf = EH;
					*taller = FALSE;
					break;
				}
			}
		}
		else
		{
			if(!InsertAVL(&(*T)->rchild,e,taller))
				return FALSE;
			if(*taller)
			{
				switch((*T)->bf)
				{
					case LH:
						(*T)->bf = EH;
						*taller = FALSE;
						break;
					case EH:
						(*T)->bf = RH;
						*taller = TRUE;
						break;
					case RH:
						RightBalance(T);
						*taller = FASLE;
						break;
				}
			}
		}
	}
	return TRUE;
}

不平衡的二叉树查找效率较低，而平衡二叉树插入删除和查找的时间复杂度O(logn)。

文章目录