作者:heqiuhao | 来源:互联网 | 2023-05-17 03:27
二叉查找树是一种特殊的二叉树。其树结点的结构和普通二叉树一样。所不同的是,我们对二叉查找树的建立和修改操作都需要使其始终满足一个条件:对于树中的每个结点X,它的左子树中所有关键字值
二叉查找树是一种特殊的二叉树。其树结点的结构和普通二叉树一样。所不同的是,我们对二叉查找树的建立和修改操作都需要使其始终满足一个条件:对于树中的每个结点X,它的左子树中所有关键字值小于X的关键值,而它的右子树中所有关键字大于X的关键值。
正是这个条件二叉查找树的建立和修改操作和普通二叉树不一样,需要按照一定的规则。这一规则赋予二叉查找树一些性质。
二叉查找树具有的性质:
1、二叉查找树具有较好的查找性质(如果构建得当的话)。
2、二叉查找树的中序遍历序列是正序排序。
3、最小元素在最左端。最大元素在最右端。
以二叉查找树为基础的树:
1、平衡二叉树(AVL树)
2、红黑树
3、伸展树(Splay)
4、B树
二叉查找树具有的操作:
1、查找特定元素;
2、查找最大、最小元素;
3、中序遍历序列索引:查找某个结点的前趋结点、查找某个结点的后继结点;
3、插入结点:仅在叶子结点插入。
4、删除结点:可以删除任意结点,但不可以改变该树的性质。因此删除操作存在三种情况。(假设被删结点为z)
第一种情况:z结点是叶子结点。那么它可以直接被删除。而不会影响其他结点。
第二种情况:z结点具有一个孩子(左或者右)。那么把z的孩子接在z的双亲上,就不会破坏树的性质。
第三种情况:z结点具有两个孩子。对于这种情况,可能存在不同的处理方法。《算法导论》中给出的办法是用z结点的后继结点的值来的代替z的位置,然后把后继结点删除。
为什么可以用后继结点来替代z的位置?
理由一:z结点的后继结点必定是z的右子树的最左结点(即z的右子树中的最小元素),当删除掉z元素之后,z结点的后继结点自然可以拿出来作为z的左右两个子树的分叉结点。
理由二:同时,z的后继结点必定没有左孩子(即叶子结点或者单右孩子结点),删除这样的结点属于第二种情况。
#include
#include
typedef struct TreeNode{
int value;
TreeNode* left;
TreeNode* right;
}TreeNode, *SearchTree;
void clear(SearchTree &root)
{
if(root!=NULL)
{
clear(root->left);
clear(root->right);
free(root);
root = NULL;
}
}
SearchTree find(int x, SearchTree root)
{
if(root == NULL)
return NULL;
if(x value)
return find(x, root->left);
else if(x > root->value)
return find(x, root->right);
else
return root;
}
SearchTree find_nonrecursion(int x, SearchTree root)
{
if(root == NULL)
return NULL;
while(root != NULL)
{
if(x == root->value)
return root;
else if(x value)
root = root->left;
else if(x > root->value)
root = root->right;
}
return NULL;
}
SearchTree find_min(SearchTree root)
{
if(root == NULL)
return NULL;
if(root->left == NULL)
return root;
else
return find_min(root->left);
}
SearchTree find_min_nonrecursion(SearchTree root)
{
if(root == NULL)
return NULL;
while(root->left !=NULL)
{
root = root->left;
}
return root;
}
SearchTree find_max(SearchTree root)
{
if(root == NULL)
return NULL;
if(root->right == NULL)
return root;
else
return find_max(root->right);
}
SearchTree find_max_nonrecursion(SearchTree root)
{
if(root == NULL)
return NULL;
while(root->right != NULL)
{
root = root->right;
}
return root;
}
void insert(int x, SearchTree &T)
{
//参数T必须是引用类型,因为当树最初为空时,并不存在根结点的地址
if(T == NULL)
{
T = (TreeNode*)malloc(sizeof(TreeNode));
T->value = x;
T->left = NULL;
T->right = NULL;
printf("%d has been inserted.\n",x);
return;
}
int flag = 0;
TreeNode *root = T;//不能把根节点的地址弄丢了
TreeNode *p = NULL;
while(root != NULL)
{
p = root;
if(x value)
{
flag = 1;
root = root->left;
}
else if(x > root->value)
{
flag = -1;
root = root->right;
}
else //该元素已经存在
{
printf("%d Exists!\n",x);
return ;
}
}
if(flag == 1)
{
p->left = (TreeNode*)malloc(sizeof(TreeNode));
p = p->left;
}
else
{
p->right = (TreeNode*)malloc(sizeof(TreeNode));
p = p->right;
}
p->value = x;
p->left = NULL;
p->right = NULL;
printf("%d has been inserted.\n",x);
}
void remove(int x, SearchTree &T)
{
TreeNode *root = T;
TreeNode *p = root;
int flag = 0;
while(root != NULL && root->value != x)
{
if(x value)
{
p = root;
flag = 1;
root = root->left;
}
else
{
p = root;
flag = -1;
root = root->right;
}
}
if(root == NULL)
{
printf("%d Not Found!\n",x);
return;
}
if(p == root) //被删结点是根节点
{
TreeNode *tmp = root;
if(root->left == NULL)
{
root = root->right;
free(tmp);
if(root == NULL)
{
T = NULL;
printf("%d has been inserted.\n",x);
return;
}
}
else if(root->right == NULL)
{
root = root->left;
free(tmp);
if(root == NULL)
{
T = NULL;
printf("%d has been inserted.\n",x);
return;
}
}
else
{
TreeNode *post = root->right;
TreeNode *ppost;
while(post->left!=NULL)
{
ppost = post;
post = post->left;
}
if(post == root->right)
{
root->value = post->value;
root->right = post->right;
free(post);
}
else
{
root->value = post->value;
ppost->left = NULL;
free(post);
}
}
}
else //被删结点不是根节点
{
if(root->left == NULL)
{
TreeNode *tmp = root;
if(flag == 1)
p->left = root->right;
else
p->right = root->right;
free(tmp);
}
else if(root->right == NULL)
{
TreeNode *tmp = root;
if(flag == 1)
p->left = root->left;
else
p->right = root->left;
free(tmp);
}
else
{
TreeNode *post = root->right;
TreeNode *ppost;
while(post->left != NULL)
{
ppost = post;
post = post->left;
}
if(post == root->right)
{
root->value = post->value;
root->right = post->right;
free(post);
}
else
{
root->value = post->value;
ppost->left = NULL;
free(post);
}
}
}
printf("%d has been removed.\n",x);
}
void inorder_traverse(SearchTree root)
{
if(root != NULL)
{
inorder_traverse(root->left);
printf("%d ", root->value);
inorder_traverse(root->right);
}
}
void show(SearchTree T)
{
printf("Tree: ");
inorder_traverse(T);
printf("\n");
}
int main()
{
SearchTree T = NULL;
printf("%s\n",T);
insert(3, T);
insert(7, T);
insert(2, T);
printf("%s\n",T);
show(T);
remove(7,T);
remove(2,T);
remove(3,T);
printf("%s\n",T);
insert(4, T);
insert(6, T);
insert(6, T);
insert(6, T);
insert(9, T);
show(T);
TreeNode *p;
p = find(4, T);
printf("Find :%d\n",p->value);
p = find_max(T);
printf("MAX :%d\n",p->value);
p = find_max_nonrecursion(T);
printf("MAX :%d\n",p->value);
p = find_min(T);
printf("MIN :%d\n",p->value);
p = find_min_nonrecursion(T);
printf("MIN :%d\n",p->value);
return 1;
}
编码细节:
1、我在定义结构体类型的时候经常在typedef之后忘记加struct,这一点再次提醒自己。
2、以上对树的许多操作都有递归形式和非递归形式两种,都要掌握。
3、对于不会修改树的操作函数,可以只传入指向树根结点的指针作为形参。这时候只传入了根结点的地址的副本,不会改变根结点的地址。但对于要修改树的操作函数(清空树、插入结点、删除结点),则必须传入指向树根结点指针的引用,因为这些函数可能会改变树根结点的地址,当树为空时,需要将根指针指向NULL。使用引用类型的话就要注意一开始就要把根结点指针备份,以免丢失。
PS:此类比较复杂一些的代码,我如何训练自己顶住压力在人前当面写出来?