再话二叉排序树

昨天复习了一下二叉树,却没有记录广义树。广义树采用静态实现,孩子域改成vector child,用来记录孩子节点的在静态数组中的index即可,比较复杂的情况是拿这棵树去DFS&BFS,其实也就那么回事。BST比较有用的特征是inOrderTraverse得到的是一个有序序列。

查找

一个平凡二叉树一般是没有特性的,而BST具有大小关系,所以可以选择其中一颗子树进行向下探测,所以查找将会得到一条路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void search(node* root,int x)
{
if(root==NULL){
//说明是空树
printf("search failed\n");
return;
}
if(x==root->data)
{
printf("%d\n",root->data);
}else if(x<root->data)
{
search(root->lchild,x);
}else{
search(root->rchild,x);
}
}

插入与建立操作

对一个BST,查找一个节点是顺着一条路径,因此如果能够查找成功,说明已经存在;否则,查找失败,说明这个查找失败的地方正是节点需要插入的地方,显然插入的复杂度是O(layer)级别的。插入和查找差不太多。建立一颗bst也就是插入一系列节点的过程。

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
void insert(node8 &root,int x)
{
if(root==NULL)
{
root=newNode(x); //之前有过newNode的函数
return;
}
if(x==root->data)
{
return; //已经存在,直接返回
}else if(x<root->data){
insert(root->lchild,x);
}else{
insert(root->rchild,x);
}
}

node* Create(int data[],int n)
{
node* root=NULL;
for(int i=0;i<n;i++)
{
insert(root,data[i]);
}
return root;
}

需要注意的是,即便是一组相同的数字,如果插入顺序不同,最后生成的BST也可能不同。

BST节点删除

BST删除一般有两种方法,复杂度都是O(layer),重点在于怎么保持删除后仍然是BST。对于给定节点,在BST中比节点权值大的最小节点为后继,比节点权值小的最大节点为前驱。所以我们需要先来寻找以当前节点root为根的树中的最大或者最小权值的节点,用于辅助寻找前驱或后继。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
node* findMax(node* root)
{
while(root->rchild!=NULL){
root=root->rchild;
}
return root;
}
node* findMin(node* root)
{
while(root->lchild!=NULL){
root=root->lchild;
}
return root;
}

基本思路分为四步,第一步是root为空则return;第二步时如果当前root权值大于目的x,则说明要在左子树里面递归删除x的节点;第三步是如果当前root权值小于目的x,则说明要在其右子树递归去删除值为x的节点。第四步比较复杂,当root值等于目的x:

  • 如果当前root没有左右孩子则说明是叶子直接删除
  • 如果当前节点存在左孩子,则在左子树中寻找节点前驱pre,让pre的数据覆盖root,接着在左子树中删除pre
  • 如果当前节点存在右孩子,则在右子树中寻找节点后继next,让next的数据覆盖root,接着在右子树中删除next
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void deleteNode(node* &root,int x)
    {
    if(root==NULL) return;
    if(root->data==x){
    if(root->lchild==NULL&&root->rchild==NULL){
    root=NULL;
    }else if(root->lchild!=NULL){
    node* pre=findMax(root->lchild);
    root->data=pre->data;
    deleteNode(root->rchild,pre->data);
    }else{
    node* next=findMax(root->rchild);
    root->data=next->data;
    deleteNode(root->rchild,next->data);
    }
    }else if(root->data>x){
    deleteNode(root->lchild,x);
    }else{
    deleteNode(root->rchild,x);
    }
    }