二叉排序树的构造

发布时间：2023-05-20

一、二叉排序树的定义

二叉排序树（Binary Search Tree）是一种特殊的二叉树，它的左子树中的所有节点都比根节点小，右子树中的所有节点都比根节点大。 总之，对于树中的每个节点，其左子树中的所有节点的值都小于它，其右子树中的所有节点的值都大于它。

typedef struct Node                   
{
    int data;
    struct Node *right,*left;
}*BiTree;

二、二叉排序树的构造

1. 递归插入节点

二叉排序树可以通过递归插入节点来构造，在插入节点的时候需要比较节点的值与当前节点的值的大小关系，以此来确定节点的插入位置。

void insertBST(BiTree *root,int data)  
{
    if(!(*root))                     
    {
        *root=(Node*)malloc(sizeof(Node)); 
        (*root)->data=data;
        (*root)->left=(*root)->right=NULL;
        return;
    }
    if(data==(*root)->data)         
    {
        return;
    } 
    else if(data<(*root)->data)     
    {
        insertBST(&(*root)->left,data);    
    }
    else if(data>(*root)->data)     
    {
        insertBST(&(*root)->right,data);
    }
}

当插入一个节点时，如果二叉排序树为空，则将该节点作为根节点插入； 当插入的节点的值等于二叉排序树的根节点的值时，不进行任何操作； 当插入的节点的值小于二叉排序树的根节点的值时，递归地插入在左子树中； 当插入的节点的值大于二叉排序树的根节点的值时，递归地插入在右子树中。

2. 非递归插入节点

除了递归插入节点，我们还可以通过非递归方式插入节点来构造二叉排序树，方法是利用while循环周期性地遍历二叉排序树的节点，直到找到插入位置。

void insertBST(BiTree *root,int data)
{
    BiTree p=*root,q;               
    if(!p)                          
    {
        *root=(Node*)malloc(sizeof(Node)); 
        (*root)->data=data;
        (*root)->left=(*root)->right=NULL;
        return;
    }
    while(p)                        
    {
        if(data==p->data)           
        {
            return;
        }
        q=p;                        
        if(data < p->data)         
        {
            p=p->left;
        }
        else            
        {
            p=p->right;
        }
    }
    p=(BiTree)malloc(sizeof(Node));  
    p->data=data;                   
    p->left=p->right=NULL;          
    if(data < q->data)                
    {
        q->left=p;
    }
    else                            
    {
        q->right=p;
    }
}

先定义一个p指针指向根节点，如果p为空，则将新节点作为根节点插入；若p不为空，则进行while循环。对于每个节点p，我们比较插入的值与p的值大小，以此来确定插入位置。如果查找到相同节点的值，则不进行插入；如果移向了空节点，则插入新节点作为其子节点。

三、二叉排序树的遍历

遍历二叉排序树可以得到一个有序的数列，可以按照从小到大或从大到小的顺序输出节点值。

1. 中序遍历

中序遍历是一种常用的遍历方式，中序遍历二叉排序树可以得到有序的节点序列。

void inOrder(BiTree root) 
{
    if(root!=NULL)       
    {
        inOrder(root->left);   
        printf("%d ",root->data);
        inOrder(root->right);  
    }
}

从根节点开始，先遍历左子树，然后输出根节点，最后遍历右子树。

2. 前序遍历

前序遍历从根节点开始遍历，先输出根节点，然后访问左子树，最后遍历右子树。

void preOrder(BiTree root)  
{ 
    if(root!=NULL)       
    {   
        printf("%d ",root->data);
        preOrder(root->left);      
        preOrder(root->right);    
    }
}

3. 后序遍历

后序遍历从左叶子结点开始后序遍历，然后是右子树，最后是根节点。

void postOrder(BiTree root) 
{
    if(root!=NULL)
    {   
        postOrder(root->left);     
        postOrder(root->right);    
        printf("%d ",root->data);
    }
}

四、二叉排序树的删除

二叉排序树的删除分为三种情况：

  1. 被删除节点无子节点，直接删除即可；
  2. 被删除节点仅有一个子节点，将其子节点作为其父节点的子节点即可；
  3. 被删除节点有两个子节点，需要寻找其前驱或后继来替代被删除节点，并删除前驱或后继节点。

1. 寻找前驱节点

寻找前驱节点是指在二叉排序树中，寻找比被删除节点的值小的最大节点。要做到这一点，我们需要在被删除节点的左子树中，找到值最大的节点，即左子树的最右下角节点。

BiTree findMax(BiTree root)     
{
    while(root->right!=NULL)       
    {
        root=root->right;
    }
    return root;
}

2. 寻找后继节点

寻找后继节点是指在二叉排序树中，寻找比被删除节点的值大的最小节点。要做到这一点，我们需要在被删除节点的右子树中，找到值最小的节点，即右子树的最左下角节点。

BiTree findMin(BiTree root)
{
    while(root->left!=NULL)
    {
        root=root->left;
    }
    return root;
}

3. 删除节点

删除节点需要对被删除节点的子树进行重连，也就是将被删除节点的父节点、子节点与被删除节点割离，然后对两部分子树进行合并。

void deleteNode(BiTree *root,int data)
{   
    if((*root)==NULL)
    {
        return;
    }
    if((*root)->data > data)          
    {
        deleteNode(&((*root)->left),data);
    }
    else if((*root)->data < data) 
    {
        deleteNode(&((*root)->right),data);
    }
    else                            
    {
        if((*root)->left==NULL && (*root)->right==NULL)
        {
            (*root)=NULL;
        }
        else if((*root)->left==NULL)
        {
            (*root)=(*root)->right;
        }
        else if((*root)->right==NULL)
        {
            (*root)=(*root)->left;
        }
        else                        
        {
            BiTree max=findMax((*root)->left);
            (*root)->data=max->data;
            deleteNode(&((*root)->left),max->data);
        }
    }
}

首先比较删除节点的值与当前节点的值的大小关系，递归查找要删除的节点，直到找到该节点；对于待删除节点是否有子节点，分别进行不同的操作。如果没有子节点，则直接删除该节点；如果只有一个子节点，则将该子节点作为当前节点的子节点；如果有两个子节点，则找到该节点的前驱或后继节点来替换此节点，并删除前驱或后继节点。

推荐文章