一个简单的二叉搜索树（C++实现）-低调大师

一个简单的二叉搜索树（C++实现）

2018-01-14 562

参考：http://www.cnblogs.com/skywang12345/p/3576373.html

这里主要就是自己实现的代码，删除动作有点不一样：

#ifndef __BSTREE_H__
#define __BSTREE_H__
/*
参考：http://www.cnblogs.com/skywang12345/p/3576373.html

这里是介绍二叉查找树

1）若任意结点的左子树不空，则左子树上所有的结点的值均小于它的根结点的值
2）若任意结点的右子树不空，则左子树上所有的结点的值均大于它的根结点的值
3）任意结点的左右子树也分别为二叉查找树
4）没有键值相等的结点（但是这里实现的可以有相同key值的结点）。当键值相同时，插入在右子树中。
*/
#include<iomanip>
#include<iostream>
using namespace std;

template <class T>
class BSTNode
{
public:
    T key;
    BSTNode *left;
    BSTNode *right;
    BSTNode *parent;

    BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value), parent(p),left(l), right(r)
    {
        //cout << "BSTNode() +++ " << endl;
    }
};

template <class T>
class BSTree
{
private:
public:
    BSTNode <T> *mRoot;

public:
    BSTree();
    ~BSTree();

    void insert(T key);
    void print();
    void preOrder();
    T maximum();
    T minimum();
    int remove(T data);
    void destory();
    
private:
    void insert(BSTNode<T> *&tree, BSTNode<T> *z);
    void print(BSTNode<T> *tree, T key, int direction);
    void preOrder(BSTNode<T> *tree) const;
    BSTNode<T>*  maximum(BSTNode<T> *tree);
    BSTNode<T>*  minimum(BSTNode<T> *tree);
    BSTNode<T>* getNode(T data);
    void destory(BSTNode<T> *tree);
};


template <class T>
BSTree<T>::BSTree()
{
    mRoot = NULL;
}

template <class T>
BSTree<T>::~BSTree()
{

}

template <class T>
void BSTree<T>::insert(T key)
{
    BSTNode<T> *z = new BSTNode<T>(key, NULL, NULL, NULL);
    if(z)
    {
        insert(mRoot, z);
    }
}

// 这里的&是引用传递
template <class T>
void BSTree<T>::insert(BSTNode<T> *&tree, BSTNode<T> *pNode) 
{
    BSTNode<T> *pIndex = NULL;
    BSTNode<T> *pTemp = tree;

    // 先找到插入的位置
    while(pTemp != NULL)
    {
        pIndex = pTemp;
        if(pNode->key < pTemp->key)
            pTemp = pTemp->left;
        else
            pTemp = pTemp->right;
    }

    pNode->parent = pIndex;
    if(!pIndex)
        tree  = pNode;
    else if(pNode->key < pIndex->key)
        pIndex->left = pNode;
    else
        pIndex->right = pNode;

}



template <class T>
void BSTree<T>::print()
{
    if(mRoot)
    {
        print(mRoot, mRoot->key, 0);
    }
}

/*
key:结点的键值
direction：
    -1 - 表示为左孩子
    0 - 表示为根节点
    1 - 表示为左孩子
*/
template <class T>
void BSTree<T>::print(BSTNode<T> *tree, T key, int direction)
{
    if(tree)
    {
        if(direction == 0)
            cout << setw(2) << tree->key << " is root" << endl;
        else
            cout << setw(2) << tree->key << " is " << setw(2) << key << "'s " << setw(12) << (direction==1?"right child":"left child") << endl;

        print(tree->left, tree->key, -1);
        print(tree->right, tree->key, 1);
    }
}

template <class T>
void BSTree<T>::preOrder()
{
    cout << "preOrder: ";
    preOrder(mRoot);
    cout << endl;
}


// 这里是遍历。
template <class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
    if(tree)
    {
        #if 1 // 前置遍历
        cout << tree->key << " "; 
        preOrder(tree->left);
        preOrder(tree->right);
        #endif
        
        #if 0 // 中序遍历
        preOrder(tree->left);
        cout << tree->key << " ";     
        preOrder(tree->right);
        #endif

        #if 0 // 后序遍历
        preOrder(tree->left);    
        preOrder(tree->right);
        cout << tree->key << " ";     
        #endif
    }
}

// 找二叉查找树中的最大值，返回key值最大的那个结点
template <class T>
BSTNode<T> * BSTree<T>::maximum(BSTNode<T> *tree)
{
    BSTNode<T> *temp = tree;
    if(temp)
    {
        while(temp->right)
        {
            temp = temp->right;
        }

        return temp;
    }
    else
    {
        return NULL;
    }
}


// 找二叉查找树中的最小值，返回key值最小的那个结点
template <class T>
BSTNode<T> * BSTree<T>::minimum(BSTNode<T> *tree)
{
    BSTNode<T> *temp = tree;
    if(temp)
    {
        while(temp->left)
        {
            temp = temp->left;
        }

        return temp;
    }
    else
    {
        return NULL;
    }
}

template <class T>
T BSTree<T>::maximum()
{
    BSTNode<T> *temp = maximum(mRoot);
    if(temp)
    {
        return temp->key;
    }

    return NULL;
}

template <class T>
T BSTree<T>::minimum()
{
    BSTNode<T> *temp = minimum(mRoot);
    if(temp)
    {
        return temp->key;
    }

    return NULL;
}

// 通过data去获取结点。
template <class T>
BSTNode<T>* BSTree<T>::getNode(T data)
{
    BSTNode<T> *temp = mRoot;
    if(!temp)
    {
        return NULL;
    }

    while(temp)
    {
        if(temp->key == data)
            return temp;
        else if(temp->key < data)
            temp = temp->right;
        else
            temp = temp->left;
    }

    return NULL;
}


// 这个仅仅是用来打印结点的。测试用的
template <class T>
void showNode(BSTNode<T>* node)
{
        if(node->parent)
        {
            cout << "    parent: " << node->parent->key << endl;
        }
        else
        {
            cout << "    parent is NULL" << endl;
        }

        if(node->left)
        {
            cout << "    left: " << node->left->key << endl;
        }
        else
        {
            cout << "    left is NULL" << endl;
        }

        if(node->right)
        {
            cout << "    right: " << node->right->key << endl;
        }
        else
        {
            cout << "    right is NULL" << endl;
        }
}

/*
参考：http://blog.csdn.net/zq17865815296/article/details/52658908
先说一下如何删除二叉树查找树的节点吧。总共有三种情况
1.被删除的节点是叶子节点，这时候只要把这个节点删除，再把指向这个节点的父节点指针置为空就行
2.被删除的节点有左子树，或者有右子树，而且只有其中一个，那么只要把当前删除节点的父节点指向被删除节点的左子树或者右子树就行。
3.被删除的节点既有左子树而且又有右子树，这时候需要把左子树的最右边的节点或者右子树最左边的节点提到被删除节点的位置，为什么要这样呢，
根据二叉查找树的性质，父节点的指针一定比所有左子树的节点值大而且比右子树的节点的值小，为了删除父节点不破坏二叉查找树的平衡性，
应当把左子树最大的节点或者右子树最小的节点放在父节点的位置，这样的话才能维护二叉查找树的平衡性。（我是找的右子树的最小节点）
*/
template <class T>
int BSTree<T>::remove(T data)
{
    cout << "remove :" << data << endl;
    BSTNode<T>* node = getNode(data);// 这里要找到要删除的结点。
    if(node)
    {
        showNode(node);
        if(node->parent == NULL)// 删除根结点
        {
            // 这里选择的是把左子树接到右子树中key最小的那个结点的左结点上。还有一种是把右子树接到左子树的key最大的那个右结点上
            BSTNode<T> *temp = minimum(node->right);
            if(temp)
            {
                temp->left = node->left;
                mRoot = node->right;// 要更新根节点
            }
            delete node;
            node = NULL;
            return 0;
        }

        if((node->right == NULL) && (node->left == NULL)) // 删除叶子结点
        {
            if(node->parent->left == node)
            {
                node->parent->left = NULL;
            }
            else
            {
                node->parent->right = NULL;
            }
        }
        else if(node->right && node->left) // 删除有两个子节点的
        {
            BSTNode<T> *temp = minimum(node->right); // 获取后继结点，这个结点一定是没有左子树的。
            cout << "have left and right child, mimmum :" << temp->key << endl;
            if(temp == temp->parent->left) // 后继结点如果是左结点，就将它的右子树接到它父亲的左子树中。
            {
                temp->parent->left = temp->right;
            }
            else // 后继结点如果是右结点，就将它的右子树接到它父亲的右子树中。
            {
                temp->parent->right = temp->right;
            }
            node->key = temp->key; // 把后继结点的key保存在要删除的结点中
            delete temp; // 其实是删除的后继结点。
            temp = NULL;
        }
        else // 删除只有一个只有一个子结点。
        {
            if(node->right) // 有右子节点
            {
                if(node->parent->left == node)
                {
                    node->parent->left = node->right;
                }
                else
                {
                    node->parent->right = node->right;
                }
            }
            else
            {
                if(node->parent->left == node)
                {
                    node->parent->left = node->left;
                }
                else
                {
                    node->parent->right = node->left;
                }    
            }        
            delete node;
            node = NULL;
        }

    }
    else
    {
        return -1;
    }

    return 0;
}


template <class T>
void BSTree<T>::destory(BSTNode<T> *tree)
{
    if(tree)
    {
        if(tree->left)
            destory(tree->left);
        if(tree->right)
            destory(tree->right);
        delete tree;
        tree = NULL;
    }
}

template <class T>
void BSTree<T>::destory()
{
    destory(mRoot);
}

#endif // __BSTREE_H__

下面是测试代码：

#include<iostream>
#include"bstree.h"
using namespace std;

/*
可以插入相同的，会插入在右子树中。
*/
void fun()
{
    cout << "fun() +++ " << endl;
    int i = 0, len = 0;
    BSTree<int>* tree = new BSTree<int>;
    if(tree->mRoot == NULL)
        cout << "fun() mRoot is NULL" << endl;
    int arr[] = {2, 15, 4, 44, 30, 36, 50, 12, 55, 414};
    int count = sizeof(arr)/sizeof(int);
    for(int i = 0; i<count; i++)
    {
        tree->insert(arr[i]);
    }
    tree->insert(125);

    tree->insert(5);
    tree->preOrder();
    int maxkey = tree->maximum();
    cout << "Max key = " << maxkey << endl;
    int minkey = tree->minimum();
    cout << "Min key = " << minkey << endl;
    tree->remove(12);
    tree->remove(2);

    tree->preOrder();
    //tree->print();

    tree->destory();
    cout << "fun() --- " << endl;
}

int main()
{
    cout << "hello world" << endl;
    fun();
    return 0;
}

注意：上面只有bstree.h，没有bstree.cpp。

关于为何C++的模板类声明和实现要放在一起可以参考：http://www.cnblogs.com/xcywt/p/8039574.html

微信关注我们

原文链接：https://yq.aliyun.com/articles/647051

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

Go Storm Is Coming!

版权声明：本文可能为博主原创文章，若标明出处可随便转载。 https://blog.csdn.net/Jailman/article/details/79068041 goland---http://idea.youbbs.org ...................................................................................................................................................................................................................... Prepare to get fucked, you suckers!

2018-01-14

984

说在前面的话：就像阿里规约里提到, 单元测试需要满足的AIR原则： A：Automatic（自动化） I：Independent（独立性） R：Repeatable（可重复）工欲善其事,必先利其器. 单元测试三剑客： TestNg：单元测试框架 AssertJ：断言工具 Jmockit：mock工具 TestNg testNg是个unit test/sut框架, 支持很多功能。但本篇文章重点不是介绍testNg,简单提一下我觉得比较有用的功能 Group：测试用例分组,根据业务/逻辑分组,以更小的粒度来执行case. Parallel：并行执行,可以配置多个线程来执行case.需要注意并发问题. <suite name="My suite" thread-count="10" parallel="classes"> <test name="mocking"> <packages> <package name="com.hz.constantine.jmockit.slideshare.mocking"/> </packages...

2018-01-14

791

资源下载

更多资源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。