二进制排序树实现（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;
}

查找功能

这也是一个递归操作. 为了从外部隐藏根（根节点），编写了私有函数来执行实际搜索操作.

//真正的查找函数
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();
};

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-183226-1.html