二叉查找树的c++实现：

1. 节点和二叉查找树的定义

1.1 二叉查找树节点

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(),left(l),right(r) {}

};

BSTNode是二叉查找树的节点，它包含二叉查找树的几个基本信息：
(01) key -- 它是关键字，是用来对二叉查找树的节点进行排序的。
(02) left -- 它指向当前节点的左孩子。
(03) right -- 它指向当前节点的右孩子。
(04) parent -- 它指向当前节点的父结点。

1.2 二叉树操作

template <class T>

class BSTree {

    private:

        BSTNode<T> *mRoot;    // 根结点

    public:

        BSTree();

        ~BSTree();

        // 前序遍历"二叉树"

        void preOrder();

        // 中序遍历"二叉树"

        void inOrder();

        // 后序遍历"二叉树"

        void postOrder();

        // (递归实现)查找"二叉树"中键值为key的节点

        BSTNode<T>* search(T key);

        // (非递归实现)查找"二叉树"中键值为key的节点

        BSTNode<T>* iterativeSearch(T key);

        // 查找最小结点：返回最小结点的键值。

        T minimum();

        // 查找最大结点：返回最大结点的键值。

        T maximum();

        // 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。

        BSTNode<T>* successor(BSTNode<T> *x);

        // 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。

        BSTNode<T>* predecessor(BSTNode<T> *x);

        // 将结点(key为节点键值)插入到二叉树中

        void insert(T key);

        // 删除结点(key为节点键值)

        void remove(T key);

        // 销毁二叉树

        void destroy();

        // 打印二叉树

        void print();

    private:

        // 前序遍历"二叉树"

        void preOrder(BSTNode<T>* tree) const;

        // 中序遍历"二叉树"

        void inOrder(BSTNode<T>* tree) const;

        // 后序遍历"二叉树"

        void postOrder(BSTNode<T>* tree) const;

        // (递归实现)查找"二叉树x"中键值为key的节点

        BSTNode<T>* search(BSTNode<T>* x, T key) const;

        // (非递归实现)查找"二叉树x"中键值为key的节点

        BSTNode<T>* iterativeSearch(BSTNode<T>* x, T key) const;

        // 查找最小结点：返回tree为根结点的二叉树的最小结点。

        BSTNode<T>* minimum(BSTNode<T>* tree);

        // 查找最大结点：返回tree为根结点的二叉树的最大结点。

        BSTNode<T>* maximum(BSTNode<T>* tree);

        // 将结点(z)插入到二叉树(tree)中

        void insert(BSTNode<T>* &tree, BSTNode<T>* z);

        // 删除二叉树(tree)中的结点(z)，并返回被删除的结点

        BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);

        // 销毁二叉树

        void destroy(BSTNode<T>* &tree);

        // 打印二叉树

        void print(BSTNode<T>* tree, T key, int direction);

};

BSTree是二叉树。它包含二叉查找树的根节点和二叉查找树的操作。二叉查找树的操作中有许多重载函数，例如insert()函数，其中一个是内部接口，另一个是提供给外部的接口。

2. 遍历（前序遍历、中序遍历、后序遍历、…）//相对于根节点来说

2.1 前序遍历

若二叉树非空，则执行以下操作：
(01) 访问根结点；
(02) 先序遍历左子树；
(03) 先序遍历右子树。

template <class T>

void BSTree<T>::preOrder(BSTNode<T>* tree) const

{

    if(tree != NULL)

    {

        cout<< tree->key << " " ;

        preOrder(tree->left);

        preOrder(tree->right);

    }

}

template <class T>

void BSTree<T>::preOrder()

{

    preOrder(mRoot);

}

2.2 中序遍历

若二叉树非空，则执行以下操作：
(01) 中序遍历左子树；
(02) 访问根结点；
(03) 中序遍历右子树。

template <class T>

void BSTree<T>::inOrder(BSTNode<T>* tree) const

{

    if(tree != NULL)

    {

        inOrder(tree->left);

        cout<< tree->key << " " ;

        inOrder(tree->right);

    }

}

template <class T>

void BSTree<T>::inOrder()

{

    inOrder(mRoot);

}

2.3 后序遍历

若二叉树非空，则执行以下操作：
(01) 后序遍历左子树；
(02) 后序遍历右子树；
(03) 访问根结点。

template <class T>

void BSTree<T>::postOrder(BSTNode<T>* tree) const

{

    if(tree != NULL)

    {

        postOrder(tree->left);

        postOrder(tree->right);

        cout<< tree->key << " " ;

    }

}

template <class T>

void BSTree<T>::postOrder()

{

    postOrder(mRoot);

}

3. 查找

递归版本的代码：

 template <class T>

BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const

{

    if (x==NULL || x->key==key)

        return x;

    if (key < x->key)

        return search(x->left, key);

    else

        return search(x->right, key);

}

template <class T>

BSTNode<T>* BSTree<T>::search(T key)

{

    search(mRoot, key);

}

非递归：

template <class T>

BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key) const

{

    while ((x!=NULL) && (x->key!=key))

    {

        if (key < x->key)

            x = x->left;

        else

            x = x->right;

    }

    return x;

}

template <class T>

BSTNode<T>* BSTree<T>::iterativeSearch(T key)

{

    iterativeSearch(mRoot, key);

}

4. 最大值和最小值

查找最大值：

template <class T>

BSTNode<T>* BSTree<T>::maximum(BSTNode<T>* tree)

{

    if (tree == NULL)

        return NULL;

    while(tree->right != NULL)

        tree = tree->right;

    return tree;

}

template <class T>

T BSTree<T>::maximum()

{

    BSTNode<T> *p = maximum(mRoot);

    if (p != NULL)

        return p->key;

    return (T)NULL;

}

查找最小值：

template <class T>

BSTNode<T>* BSTree<T>::minimum(BSTNode<T>* tree)

{

    if (tree == NULL)

        return NULL;

    while(tree->left != NULL)

        tree = tree->left;

    return tree;

}

template <class T>

T BSTree<T>::minimum()

{

    BSTNode<T> *p = minimum(mRoot);

    if (p != NULL)

        return p->key;

    return (T)NULL;

}

5. 前驱和后继

节点的前驱：是该节点的左子树中的最大节点。
节点的后继：是该节点的右子树中的最小节点。

查找前驱节点代码：

/*

 * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。

 */

template <class T>

BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)

{

    // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。

    if (x->left != NULL)

        return maximum(x->left);

    // 如果x没有左孩子。则x有以下两种可能：

    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。

    // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。

    BSTNode<T>* y = x->parent;

    while ((y!=NULL) && (x==y->left))

    {

        x = y;

        y = y->parent;

    }

    return y;

}

查找后继节点的代码：

/*

 * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。

 */

template <class T>

BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)

{

    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。

    if (x->right != NULL)

        return minimum(x->right);

    // 如果x没有右孩子。则x有以下两种可能：

    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。

    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。

    BSTNode<T>* y = x->parent;

    while ((y!=NULL) && (x==y->right))

    {

        x = y;

        y = y->parent;

    }

    return y;

}

6. 插入节点

/*

 * 将结点插入到二叉树中

 *

 * 参数说明：

 *     tree 二叉树的根结点

 *     z 插入的结点

 */

template <class T>

void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T>* z)

{

    BSTNode<T> *y = NULL;

    BSTNode<T> *x = tree;

    // 查找z的插入位置

    while (x != NULL)

    {

        y = x;

        if (z->key < x->key)

            x = x->left;

        else

            x = x->right;

    }

    z->parent = y;

    if (y==NULL)

        tree = z;

    else if (z->key < y->key)

        y->left = z;

    else

        y->right = z;

}

/*

 * 将结点(key为节点键值)插入到二叉树中

 *

 * 参数说明：

 *     tree 二叉树的根结点

 *     key 插入结点的键值

 */

template <class T>

void BSTree<T>::insert(T key)

{

    BSTNode<T> *z=NULL;

    // 如果新建结点失败，则返回。

    if ((z=new BSTNode<T>(key,NULL,NULL,NULL)) == NULL)

        return ;

    insert(mRoot, z);

}

注：本文实现的二叉查找树是允许插入相同键值的节点的。若想禁止二叉查找树中插入相同键值的节点，可以参考"二叉查找树(一)之 图文解析 和 C语言的实现"中的插入函数进行修改。

7. 删除节点

/*

 * 删除结点(z)，并返回被删除的结点

 *

 * 参数说明：

 *     tree 二叉树的根结点

 *     z 删除的结点

 */

template <class T>

BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z)

{

    BSTNode<T> *x=NULL;

    BSTNode<T> *y=NULL;

    if ((z->left == NULL) || (z->right == NULL) )

        y = z;

    else

        y = successor(z);

    if (y->left != NULL)

        x = y->left;

    else

        x = y->right;

    if (x != NULL)

        x->parent = y->parent;

    if (y->parent == NULL)

        tree = x;

    else if (y == y->parent->left)

        y->parent->left = x;

    else

        y->parent->right = x;

    if (y != z)

        z->key = y->key;

    return y;

}

/*

 * 删除结点(z)，并返回被删除的结点

 *

 * 参数说明：

 *     tree 二叉树的根结点

 *     z 删除的结点

 */

template <class T>

void BSTree<T>::remove(T key)

{

    BSTNode<T> *z, *node; 

    if ((z = search(mRoot, key)) != NULL)

        if ( (node = remove(mRoot, z)) != NULL)

            delete node;

}

8. 打印二叉查找树

/*

 * 打印"二叉查找树"

 *

 * key        -- 节点的键值

 * direction  --  0，表示该节点是根节点;

 *               -1，表示该节点是它的父结点的左孩子;

 *                1，表示该节点是它的父结点的右孩子。

 */

template <class T>

void BSTree<T>::print(BSTNode<T>* tree, T key, int direction)

{

    if(tree != NULL)

    {

        if(direction==)    // tree是根节点

            cout << setw() << tree->key << " is root" << endl;

        else                // tree是分支节点

            cout << setw() << tree->key << " is " << setw() << key << "'s "  << setw() << (direction==?"right child" : "left child") << endl;

        print(tree->left, tree->key, -);

        print(tree->right,tree->key,  );

    }

}

template <class T>

void BSTree<T>::print()

{

    if (mRoot != NULL)

        print(mRoot, mRoot->key, );

}

9. 销毁

/*

 * 销毁二叉树

 */

template <class T>

void BSTree<T>::destroy(BSTNode<T>* &tree)

{

    if (tree==NULL)

        return ;

    if (tree->left != NULL)

        return destroy(tree->left);

    if (tree->right != NULL)

        return destroy(tree->right);

    delete tree;

    tree=NULL;

}

template <class T>

void BSTree<T>::destroy()

{

    destroy(mRoot);

}

本文来自http://www.cnblogs.com/skywang12345/p/3576373.html

最新文章

  1. XML中的转义字符
  2. PHP内核探索之变量（1）Zval
  3. Html5 Egret游戏开发 成语大挑战（九）设置界面和声音管理
  4. Session原理浅析
  5. NET 命名规范
  6. webkit和xcode
  7. 转:FileReader详解与实例---读取并显示图像文件
  8. （一）SQL关联查询的使用技巧 （各种 join）
  9. 贪心：字典树openjudge1799-最短前缀
  10. dwr3+spring实现消息实时推送
  11. Cow Cycling 动态规划
  12. 总结描述用户和组管理类命令的使用方法,系统用户相关信息，取出主机IP地址
  13. Solaris：你好奇的十件事
  14. pyqt5界面使用
  15. Java+Selenium环境搭建
  16. Android---Hellow World
  17. Huffman Coding
  18. [lua, mysql] 将多条记录数据组合成一条sql插入语句(for mysql)
  19. TraceSource记录程序日志
  20. pandas 常用语句

热门文章

  1. [SoapUI] 各种日期计算
  2. 如何使用css来让图片居中不变形 微信小程序和web端适用
  3. QDesktopWidget
  4. HDU2212 DFS 2016-07-24 13:52 56人阅读 评论(0) 收藏
  5. hdu2680 choose the best route
  6. hdu 4946 凸包注意重点
  7. java web eclipse中项目的加载过程
  8. ibatIs中的isNotNull、isEqual、isEmpty
  9. EBS MOAC相关
  10. ORACLE报表触发器