用c++實作一個二叉排序樹

二叉排序樹又稱二叉查找樹（Binary Search Tree）。其定義為：二叉排序樹或者收空樹，或者是滿足如下性質的二叉樹。

（1）若它的左子樹非空，則左子樹上所有節點的值均小于根節點的值。

（2）若它的右子樹非空，則右子樹上所有節點的值均大于根節點的值。

（3）左右子樹本身又各是一顆二叉排序樹。

二叉排序樹資料結構如下：

//節點類定義
class Node
{
    int data;
    Node *parent;   //父節點
    Node *left;        //左節點
    Node *right;     //右節點
    public:
        Node():data(-1),parent(NULL),left(NULL),right(NULL){};
        Node(int num):data(num),parent(NULL),left(NULL),right(NULL){};
}
           

二叉排序樹類的定義：

class Tree
{
    public:
        Tree(int num[],int len);  //插入num數組的前len個資料
        void insertNode1(int data);  //插入資料，用遞歸的方式
        void insertNode(int data);   //插入資料，用非遞歸的方式
        Node *searchNode(int data); //查找節點
        void deleteNode(int data);    //删除節點以及子樹
     private:
         void insertNode(Node* current,int data); //遞歸插入方法
         Node* searchNode(Node* current,int data); //遞歸查找方法
         void deleteNode(Node* current);   //遞歸删除方法
    private:
        Node *root; //根節點
}
           

在private中的三個方法主要是為了封裝性的考慮，指針root是私有成員變量，于是在public中使用遞歸方法的三個函數都隻能有一個參數data，然而，這裡隻含有一個參數是無法進行遞歸計算的。是以他們内部調用了這三個private中的方法。

接下來說明各個方法的實作。

1，建立二叉排序樹的方法（在構造函數中）

Tree::Tree(int num[],int len)
{
    root=new Node(num]);//建立root節點
    for(int i;i<len;i++)
    {
        insertNode1(num[i]);
        /*insertNode(num[i]);*/
    }
};
           

2，插入節點操作

//以非遞歸的方式
void Tree::insertNode1(int data)
{
    Node *p,*par;
    Node *newNode=new Node(data);
    p=par=root;
    while(p!=NULL)
    {
        par=p;
        if(data>p->data)
            p=p->right;
            else if(data<p->data)
                p=p->left;
        else if(data==p->data)
            {
                delete newNode;  //不能插入重複資料
                return;
            }
    }
    newNode->parent=par;
    if(par->data > newNode->data)
        par->left=newNode;
    else
        par->right=newNode;
}
           

它分為以下步驟：

（1）建立節點

（2）查找建立節點的插入位置

（3）把建立點插入目标節點的正确位置。

insertNode()内部調用private函數insertNode(),使用遞歸方式插入。

//插入資料為參數data的節點，調用遞歸插入的方法
void Tree::insertNode(int data)
{
    if(root!=NULL)
    {
        insertNode(root,data);
    }
}
//遞歸插入方法
void Tree::insertNode(Node* current,int data)
{
    //如果data小于目前節點資料，則在目前節點的左子樹插入
    if(data<current->data)
    {
        if(current->left==NULL)//若不存在，則插入到左節點
        {
            current->left=new Node(data);
            current->left->parent=current;
        }
        else
            insert(current->left,data);
    }
    //如果data大于目前節點，則在右子樹中插入
    else if(data>current->data)
    {
        if(current->right==NULL)
        {
            current->right=new Node(data);
            current->right->parent=current;
        }
        else
            insertNode(current->right,data);
    }
    return;   //data等于目前節點資料時，不插入
}
           

3，查找節點

Node* Tree::searchNode(Node* current,int data)
{
    //如果data小于目前節點，則搜尋左子樹
    if(data<current->data)
    {
        if(current->left==NULL)//如果不存在左子樹
            return NULL;
        return searchNode(current->left,data);
    }
    /*如果data大于目前節點，則遞歸搜尋其右子樹*/
    else if(data>current->data)
    {
        if(current->right==NULL)
            return NULL;
        return searchNode(current->right,data);
    }
    //如果相等，則傳回current
    return current;
}
           

4，删除節點

void Tree::deleteNode(int data)
{
    Node *current=NULL;
    current=searchNode(data);   //查找節點
    if(current!=NULL）
    {
        deleteNode(current);
    }
}
void Tree::deleteNode(Node *current)
{
    if(current->left!=NULL) 
        deleteNode(current->left);
    if(current->right!=NULL)
        deleteNode(current->right);
    if(current->parent==NULL)
    {
             /*如果current是根節點，把root置空*/
        delete current;
        root=NULL;
        return;
    }
    //将current父親節點的相應指針置空
    if(current->parent->data>current->data)
        current->parent->left=NULL;
    else
        current->parent->right=NULL;
    //最後删除此節點
    delete current;
}