特点：左子树值<结点值<右子树值，其中序遍历序列为递增有序序列
-
二叉排序树的插入
二叉排序树作为一种动态集合，其特点是树的结构通常不是一次生成的，而是在查找过程中当树中不存在关键字等于给定值的结点时再进行插入。插入的新结点一定是某个叶结点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int BST_Insert(BiTree &T, KeyType k){
if(T==NULL){
T=(BiTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=NULL;
T->rchild=NULL;
return 1;
}
else if(k==T->key)
return 0;
else if(k<T->key)
return BST_Insert(T->lchild, k);
else
return BST_Insert(T->rchild, k);
} -
二叉排序树的建立
1
2
3
4
5
6
7
8void (BiTree &T, KeyType str[], int n){
int i=0;
T=NULL;
while(i<n){
BST_Insert(T,str[i++]);
}
} -
二叉排序树的非递归查找(类比线性表的二分查找)
1
2
3
4
5
6
7
8
9
10
11
12//查找函数返回指向关键字值为key的结点指针，若不存在则返回NULL
BSTNode *BST_Search(BiTree T, Elemtype key, BSTNode *&p){
p=NULL; //p指向被查找结点的双亲，用于插入或删除操作
while(key!=T->data&&T!=NULL){
p=T;
if(key<T->data)
T=T->lchild;
else
T=T->rchild;
}
return T;
} -
判断给定的二叉树是否是二叉排序树
中序遍历序列为递增有序序列的二叉树即为二叉排序树。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15KeyType predt=-65535;
int JudgeBST(BiTree T){
int b1,b2;
if(T==NULL)
return 1;
else{
b1=JudgeBST(T->lchild);
if(b1==0||T->data<predt)
return 0;
predt=T->data;
b2=JudgeBST(T->rchild);
return b2;
}
}
平衡二叉树
平衡二叉树是二叉排序树的演变与进化。
二叉排序树在结点插入的顺序不同时，性能可能有所不同。
举个极端例子，当用一个顺序序列建立二叉排序树时，结点的数量等于二叉树的高。此时查询一个结点的时间复杂度与单链表相同，为O(n)。这与我们想要的时间复杂度O($log_2 n$)相距甚远。
由于二叉排序树的性能与其高度息息相关，为避免出现性能下降的情况，则在插入结点时要充分利用其高度，避免其增长过快。由此，平衡二叉树诞生了。
平衡二叉树（AVL树）保证在插入和删除结点后，二叉树任意节点的左、右子树高度差绝对值不超过1。定义结点左右子树的高度差为结点的平衡因子。
近期评论