二叉排序樹的構造

一、二叉排序樹的定義

二叉排序樹（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(datadata)     
    {
        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(datadata)         
        {
            p=p->left;
        }
        else            
        {
            p=p->right;
        }
    }
    p=(BiTree)malloc(sizeof(Node));  
    p->data=data;                   
    p->left=p->right=NULL;          
    if(datadata)                
    {
        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)->dataright),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);
        }
    }
}

首先比較刪除節點的值與當前節點的值的大小關係，遞歸查找要刪除的節點，直到找到該節點；對於待刪除節點是否有子節點，分別進行不同的操作。如果沒有子節點，則直接刪除該節點；如果只有一個子節點，則將該子節點作為當前節點的子節點；如果有兩個子節點，則找到該節點的前驅或後繼節點來替換此節點，並刪除前驅或後繼節點。