二叉搜尋樹的代碼實作

1. 定義節點

struct Node
{
    int val;
    Node* left;
    Node* right;
    Node(){
        val=0;
        left=NULL;
        right=NULL;
    }
    Node(int x){
        val=x;
        left=NULL;
        right=NULL;
    }
};
           

2. 建構二叉搜尋樹

每當新插入一個值時，先在原樹上進行查找，找到其值對應的位置。

Node *insert(Node *rt,int x)
{
    if(rt==NULL)
    {
        //rt = Node();
        Node *q = new Node;
        q->val=x;
        q->left=q->right=NULL;
        return q;
    }
    if(rt->val>x)
    {
        rt->left = insert(rt->left,x);
    }
    else
    {
        rt->right = insert(rt->right,x);
    }
    return rt;
}
           

3. 查找

bool find(Node* rt,int x)
{
    if(rt==NULL)
    {
        return false;
    }
    if(rt->val==x) return true;
    if(rt->val>x)
    {
        return find(rt->left,x);
    }
    else
    {
        return find(rt->right,x);
    }
}
           

4. 删除

删除比較麻煩，需要分三種情況讨論。

（1）删除葉節點，直接将其删除即可

 （2）删除的節點隻有左子樹或者隻有右子樹，則讓子樹取代它

（3）删除的節點既有左子樹又有右子樹，則在左子樹中找到值最大的結節，讓其取代它。

Node *remove(Node *rt,int x)
{
    if(rt==NULL) return NULL;
    if(rt->val>x) //先找到被删除節點
    {
        rt->left = remove(rt->left,x);
    }
    else if(rt->val<x)
    {
        rt->right = remove(rt->right,x);
    }
    else 
    {
        if(rt->left&&rt->right) //左右子樹都不為空
        {
            Node* tmp = rt->left; //找左子樹的最大值，隻要一直往右找即可
            while (tmp->right)
            {
                tmp = tmp->right;
            }
            //cout<<tmp->val<<endl;
            int v = rt->val;
            rt->val = tmp->val;
            tmp->val = v;//替換
            rt->left = remove(rt->left,v); //在左子樹中删除
        }
        else if(rt->left==NULL&&rt->right==NULL) //葉節點，直接指派為空
        {
            rt = NULL;
        }
        else
        {
            if(rt->left) //
            {
                rt = rt->left;
            }
            else
            {
                rt = rt->right;
            }
        }   
    }
    return rt;
}
           

完整代碼

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <stack>
using namespace std;
const int maxn=1e5+7;
struct Node
{
    int val;
    Node* left;
    Node* right;
    Node(){
        val=0;
        left=NULL;
        right=NULL;
    }
    Node(int x){
        val=x;
        left=NULL;
        right=NULL;
    }
};
Node *insert(Node *rt,int x)
{
    if(rt==NULL)
    {
        //rt = Node();
        Node *q = new Node;
        q->val=x;
        q->left=q->right=NULL;
        return q;
    }
    if(rt->val>x)
    {
        rt->left = insert(rt->left,x);
    }
    else
    {
        rt->right = insert(rt->right,x);
    }
    return rt;
}
bool find(Node* rt,int x)
{
    if(rt==NULL)
    {
        return false;
    }
    if(rt->val==x) return true;
    if(rt->val>x)
    {
        return find(rt->left,x);
    }
    else
    {
        return find(rt->right,x);
    }
}
Node *remove(Node *rt,int x)
{
    if(rt==NULL) return NULL;
    if(rt->val>x) //先找到被删除節點
    {
        rt->left = remove(rt->left,x);
    }
    else if(rt->val<x)
    {
        rt->right = remove(rt->right,x);
    }
    else 
    {
        if(rt->left&&rt->right) //左右子樹都不為空
        {
            Node* tmp = rt->left; //找左子樹的最大值，隻要一直往右找即可
            while (tmp->right)
            {
                tmp = tmp->right;
            }
            //cout<<tmp->val<<endl;
            int v = rt->val;
            rt->val = tmp->val;
            tmp->val = v;//替換
            rt->left = remove(rt->left,v); //在左子樹中删除
        }
        else if(rt->left==NULL&&rt->right==NULL) //葉節點，直接指派為空
        {
            rt = NULL;
        }
        else
        {
            if(rt->left) //
            {
                rt = rt->left;
            }
            else
            {
                rt = rt->right;
            }
        }   
    }
    return rt;
}
void dfs(Node* rt)
{
    if(rt==NULL) return;
    dfs(rt->left);
    cout<<rt->val<<" ";
    dfs(rt->right);
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    Node* root = NULL;
    //cout<<root->val<<endl;
    root = insert(root,7);
    root = insert(root,2);
    root = insert(root,15);
    root=insert(root,1);
    root=insert(root,5);
    dfs(root);
    cout<<endl;
    cout<<find(root,15)<<endl;
    root = remove(root,15);
    dfs(root);
    cout<<endl;
    root = remove(root,7);
    cout<<endl;
    dfs(root);
    cout<<endl;
    root = remove(root,2);
    dfs(root);
    return 0;
}