二叉排序樹實現（C++封裝），二叉排序

二叉排序樹實現（C++封裝），二叉排序

設計思路

設計一個類，根結點只可讀取，具備構造二叉樹、插入結點、刪除結點、查找、 查找最大值、查找最小值、查找指定結點的前驅和後繼等功能接口。

二叉排序樹概念

它或者是一棵空樹；或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值； （2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹。

二叉排序樹的各種操作

插入新節點
這是一個遞歸操作，遞歸設計時要找到最源頭，才能得到最簡設計。一種設計是判斷葉子節點，把新節點作為葉子節點的孩子插入；一種是永遠當作根進行插入，插入節點永遠是當前子樹的根！看代碼：

//root為二級指針的原因是，如果樹為空，需要將根修改反饋回來
bool BinaryTree::InsertNode(pNode * cuRoot, int data, pNode self)
{   //遞歸設計時找到最源頭，才能得到最簡設計
    if (*cuRoot == nullptr){
        pNode node = new Node;
        if (node == nullptr)
            return false;
        node->data = data;
        node->lChild = node->rChild = node->parent = nullptr;
        (*cuRoot) = node;
        node->parent = self;
        return true;
    }
    if (data > (*cuRoot)->data)
        InsertNode(&(*cuRoot)->rChild, data, *cuRoot);
    else
        InsertNode(&(*cuRoot)->lChild, data, *cuRoot);
    return true;
}

構造函數
一共兩個重載函數：一個無參，一個接受數組利用插入函數直接構造二叉排序樹。

BinaryTree::BinaryTree(int * datum, int len)
{
    root = nullptr;
    for (int i = 0; i < len; i++)
        InsertNode(&root, datum[i], root);
}

BinaryTree::BinaryTree()
{
    root = nullptr;
}

查找函數
這也是一個遞歸操作，為了對外隱藏root（根節點），因此編寫了一個私有函數，進行真正的查找操作。

//真正的查找函數
BinaryTree::pNode BinaryTree::_searchKey(pNode root, int key){
    if (root == nullptr)
        return nullptr;
    if (root->data == key)    //找到了
        return root;
    else if (root->data > key)//值偏小，到左子樹找
        return _searchKey(root->lChild, key);
    else                      //值偏大，到右子樹找
        return _searchKey(root->rChild, key);
}
//對外接口
BinaryTree::pNode BinaryTree::SearchKey(int key){
    return _searchKey(root, key);
}

找前驅節點
要麼為左子樹中最大者，要麼一直追溯其父節點鏈，第一個是其父節點的右孩子的父節點，即為所求。

BinaryTree::pNode BinaryTree::SearchPredecessor(pNode node){
    if (node == nullptr)
        return nullptr;
    else if (node->lChild != nullptr)
        return SearchMaxNode(node->lChild);
    else
    {
        if (node->parent == nullptr)
            return nullptr;
        while (node)
        {
            if (node->parent->rChild == node)
                break;
            node = node->parent;
        }
        return node->parent;
    }
}

找後繼節點
與找前驅節點基本相似。 要麼為右子樹中最小者，要麼一直追溯其父節點鏈，第一個是其父節點的左孩子的父節點，即為所求。

BinaryTree::pNode BinaryTree::SearchSuccessor(pNode node){
    if (node == nullptr)
        return nullptr;
    else if (node->rChild != nullptr)
        return SearchMinNode(node->rChild);
    else
    {
        if (node->parent == nullptr)
            return nullptr;
        while (node)
        {
            if (node->parent->lChild == node)
                break;
            node = node->parent;
        }
        return node->parent;
    }
}

找最小值

BinaryTree::pNode BinaryTree::SearchMinNode(pNode curNode){
    if (curNode == nullptr)
        return nullptr;
    //一直找到左子樹為空的節點，即為最小值
    while (curNode->lChild != nullptr)
        curNode = curNode->lChild;
    return curNode;
}

找最大值

BinaryTree::pNode BinaryTree::SearchMaxNode(pNode curNode){
    if (curNode == nullptr)
        return nullptr;
    //一直找到右子樹為空的節點，即為最大值
    while (curNode->rChild != nullptr)
        curNode = curNode->rChild;
    return curNode;
}

中序遍歷

void BinaryTree::_visitMiddle(pNode root){
    if (root != nullptr){
        _visitMiddle(root->lChild);
        printf("%d;", root->data);
        _visitMiddle(root->rChild);
    }
}

void BinaryTree::VisitMiddle(){
    _visitMiddle(root);
}

刪除節點
這個是最麻煩的操作，分四種情況分別處理，最麻煩的是被刪節點左右子樹都存在的情況，這時將被刪節點內容換成其後繼內容，刪除其後繼（遞歸）。

bool BinaryTree::DeleteNode(int key){
    //return _deleteNode(root, key);
    pNode node = SearchKey(key);
    if (!node)
        return false;
    //被刪節點為葉子結點
    if (node->lChild == nullptr && node->rChild == nullptr){
        if (node->parent == nullptr){
            root = nullptr;
        }
        else
        {
            if (node->parent->lChild == node)
                node->parent->lChild = nullptr;
            else
                node->parent->rChild = nullptr;
        }
        delete node;
    }
    //被刪節點只有左子樹
    else if (node->lChild != nullptr && node->rChild == nullptr){
        //將左孩子的父親指向被刪節點的父親
        node->lChild->parent = node->parent;
        //被刪節點為根，修改根節點
        if (node->parent == nullptr)
            root = node->lChild;
        else if(node->parent->lChild == node)
            node->parent->lChild = node->lChild;
        else
            node->parent->rChild = node->lChild;
        delete node;
    }
    //被刪節點只有右子樹
    else if (node->lChild == nullptr && node->rChild != nullptr){
        //將右孩子的父親指向被刪節點的父親
        node->rChild->parent = node->parent;
        //被刪節點為根，修改根節點
        if (node->parent == nullptr)
            root = node->rChild;
        else if (node->parent->lChild == node)
            node->parent->lChild = node->rChild;
        else
            node->parent->rChild = node->rChild;
        delete node;
    }
    //被刪節點左、右子樹都有
    else {  //用後繼節點取代刪除節點，並刪除後繼
        pNode successor = SearchSuccessor(node);
        int temp = successor->data;
        DeleteNode(temp);
        node->data = temp;
    }
}

柝構函數
函數超出作用域范圍時，清理占用內存。

BinaryTree::~BinaryTree()
{
    _delAllNode(root);
}
void BinaryTree::_delAllNode(pNode root){
    if (root != nullptr && root!=NULL){
        _delAllNode(root->lChild);
        _delAllNode(root->rChild);      
        DeleteNode(root->data);
    }
}

類的定義（頭文件）

#pragma once

#include<stdio.h>  
#include<stdlib.h> 

class BinaryTree
{
private:
    typedef struct Node{
        struct Node * parent;
        struct Node * lChild;
        struct Node * rChild;
        int data;
    }*pNode;
    pNode root;
    void _visitMiddle(pNode root);
    pNode _searchKey(pNode root, int key);
    void _delAllNode(pNode root);
public:
    BinaryTree();
    BinaryTree(int * datum, int len);
    pNode SearchMaxNode(pNode node);
    pNode SearchMinNode(pNode node);
    pNode GetRoot();
    pNode SearchKey(int key);
    bool DeleteNode(int key);
    pNode SearchPredecessor(pNode node);
    pNode SearchSuccessor(pNode node);
    void VisitMiddle();
    bool InsertNode(pNode * cuRoot, int data, pNode self);
    ~BinaryTree();
};

調用示例

#include <conio.h>
#include "BinaryTree.h"

int main()
{
    int arrs[] = { 23, 65, 12, 3, 8, 76,  90, 21, 75, 34,345, 61 };
    int len = sizeof(arrs) / sizeof(arrs[0]);
    BinaryTree bTree(arrs,len);
    bTree.DeleteNode(90);
    bTree.VisitMiddle();
    getch();
    return 0;
}