二叉排序树的建立_二叉排序树的删除_二叉排序树删除节点

STL中还有一类非常重要的容器，就是关联容器，比如map啊set啊等等，这些容器说实话，在应用层上还不能完全得心应手（比如几种容器效率的考虑等等），更别说源码了，因此这一部分打算稳扎稳打，好好做做笔记研究一番。二叉排序树的删除

说到关联容器，我们想到了什么L树，红黑树等等，但大多时候我们仅仅局限于知道其名字，或者知道其概念，俗话说“talk is cheap，show me the code”，因此，我打算从他们的祖爷爷二叉排序树开始下手。（其实，侯老师的书上也是这么安排的哈）

1.任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2.任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3.任意节点的左、右子树也分别为二叉查找树；

4.没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(logn)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

1.中序遍历是一个升序的有序序列。

2.搜索、插入、删除的复杂度等于树高，期望O(logn)，最坏O(n)（数列有序，树退化成线性表）。

既然看到此，不如试着实现一下二叉排序树，主要需要包含这些操作：构建二叉排序树输入一个序列输出一个二叉排序树，插入、删除节点。

写代码之前考虑的问题：

1.二叉排序树的插入一定是在叶子节点处。

2.二叉排序树的删除需要考虑三种情况：

a）待删除节点在叶子节点处

直接另其父节点相应指针制空，并删除该节点即可。

b）待删除节点只含有一个孩子（左子树为空或者右子树为空）

将待删除节点父节点对应指针指向待删除节点的孩子节点。

c）待删除节点即包含左右孩子都不为空

找到待删除节点的右子树的最小值（右子树一路向左），并将该值替换待删除节点的值，最后删除最小值原本所在位置的节点（叶子节点）。二叉排序树的删除

3.二叉排序树的中序遍历是升序。

4.摈弃以前的C语言写法，我这次想把BST封装成一个C++类，虽然困难重重，勉强实现了吧。

5.既然是C++类，在析构函数中做所有节点内存释放处理（最后一个根节点需要特殊处理）。

上述5个问题中除了对C++的熟悉程度外，涉及BST算法部分最麻烦的就是删除操作了，因为它考虑的情况比较多，这里贴出侯老师书中的方便理解：

vcD4NCjxoNCBpZD0="目标节点有两个子节点">目标节点有两个子节点

编译运行环境：Visual Studio 2013，Windows 7 32 bits

//BSTNode.h
#ifndef __BSTNODE_H__
#define __BSTNODE_H__
#include
class BSTNode{
public:
    BSTNode();
    BSTNode(int val);
    int value;
    BSTNode *lchild;
    BSTNode *rchild;
};
#endif

//--------------------------------------------
//--------------------------------------------
//--------------------------------------------

//BSTNode.cpp
#include "BSTNode.h"
BSTNode::BSTNode()
{
    value = 0;
    lchild = NULL;
    rchild = NULL;
}
BSTNode::BSTNode(int val)
{
    value = val;
    lchild = NULL;
    rchild = NULL;
}

//BST.h
#ifndef __BST_H__
#define __BST_H__
#include "BSTNode.h"
#include 
#include 
class BSTNode;
class BST
{
    //说明：
    //为了数据结构私有化，不为外部访问，这里提供一些私有内部函数实现真正的操作以"__"开头。
    //对于public的接口来说，只需要直接调用内部函数即可
private:
    BSTNode * bstroot;//二叉排序树数据结构
    BSTNode * __search(BSTNode* root,const int& key);//查找关键字
    BSTNode * __treeMin(BSTNode*const root,BSTNode *&parent);//返回当前节点的最小孩子（一路向左）
    BSTNode * __treeMax(BSTNode*const root);//查找最大值（未实现）
    bool __Insert( const int &key);//插入节点
    bool __Delete(const int &key);//删除删除
    bool __isLeaf(BSTNode* const &);//判断是否是叶子节点
    bool __isNodeWithTwoChild(BSTNode * const &);//判断是否有两个孩子
    void __InorderTraversal(BSTNode *root,std::vector&result);//中序遍历
    void __DeleteAllNodes(BSTNode *root);//删除所有节点
public:
    //构造函数
    BST();//默认构造函数
    BST(std::vectorarr);
    BST(int *arr, int len);
    //析构函数
    ~BST();
    bool isEmpty() const;//判断树空
    bool search(const int &key);//查找关键字是否存在的对外接口
    bool Insert(const int &key);//插入节点的外部接口
    bool Delete(const int &key);//删除节点的外部接口
    void InorderTraversal(std::vector&);//中序遍历的外部接口
};
#endif

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