文档章节

二叉搜索树

首席吹牛官
 首席吹牛官
发布于 2015/05/22 12:57
字数 584
阅读 3
收藏 0

                    二叉搜索树也是二叉树,不过多了一些限定,根节点值大于左子树小于右子树,子树递归定义。

                   

/************************************************
*
*author:周翔
*e-mail:604487178@qq.com
*blog:http://blog.csdn.net/zhx6044
*
*
*************************************************/

#ifndef BINARYSEARCHTREE_HPP
#define BINARYSEARCHTREE_HPP


#include <iostream>
#include "linkQueue.hpp"


template <typename T>
/**
 * @brief The BinarySearchTree class 二叉搜索树
 */
class BinarySearchTree
{
public:
    BinarySearchTree();
    ~BinarySearchTree();
    bool find(const T &t) const;
    void insert(const T &t);
    void remove(const T &t);
    void clear();
    bool isEmpty() const;
    void levelTraverse(std::ostream &os = std::cout) const;
private:

    struct node {
        T data;
        node *lc, *rc;
        node():lc(NULL),rc(NULL) {

        }
        node(const T &t, node *_lc = NULL, node *_rc = NULL):
            data(t),
            lc(_lc),
            rc(_rc) {

        }
    };

    node *root;

    void clear(node *p);
    void insert(const T &t, node *&p);//此处为指针引用,因为改变指向的值,不只是使用指针指向的值
    bool find(const T &t, node *p) const;
    void remove(const T &t, node *&p);//


};


template <typename T>
inline
BinarySearchTree<T>::BinarySearchTree():root(NULL)
{

}

template <typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
    clear();
}

template <typename T>
bool BinarySearchTree<T>::find(const T &t) const
{
    return find(t,root);
}

template <typename T>
/**
 * @brief BinarySearchTree<T>::insert 插入操作
 * @param t
 */
void BinarySearchTree<T>::insert(const T &t)
{
    insert(t,root);
}

template <typename T>
void BinarySearchTree<T>::remove(const T &t)
{
    remove(t,root);
}


template <typename T>
void BinarySearchTree<T>::clear()
{
    if(isEmpty()) {

    } else {
        clear(root);
        root = NULL;
    }

}

template <typename T>
void BinarySearchTree<T>::clear(node *p)
{
    if (p->lc != NULL) {
        clear(p->lc);
    }

    if (p->rc != NULL) {
        clear(p->rc);
    }

    delete p;
}


template <typename T>
inline
bool BinarySearchTree<T>::isEmpty() const
{
    return root == NULL;
}

template <typename T>
void BinarySearchTree<T>::insert(const T &t, node *&p)
{
    if (p == NULL) {
        p = new node(t);
    } else {
        if (t < p->data) {
            insert(t,p->lc);
        } else {
            insert(t,p->rc);
        }
    }

}

template <typename T>
bool BinarySearchTree<T>::find(const T &t, node *p) const
{
    bool re = false;
    if (p == NULL) {
    } else {
        if (t < p->data) {
            re = find(t,p->lc);
        } else {
            if (t > p->data) {
                re = find(t,p->rc);
            } else {
                re = true;
            }
        }
    }
    return re;
}

template <typename T>
void BinarySearchTree<T>::remove(const T &t, node *&p)//在处理关系时看成线,在处理值时p看成点,线向下指向的点,
{
    if (p == NULL) {

    } else {
        if (t == p->data) {
            if (p->lc != NULL && p->rc != NULL) {//两个子节点
                node *q = p->rc;
                while (q->lc != NULL) q = q->lc;//右子树最左的节点也就是右子树最小节点代替根节点
                p->data = q->data;//节点值改变就行
                remove(q->data,p->rc);//在右子树中删除替换的节点
            } else {
                if (p->lc == NULL || p->rc == NULL) {//一个子节点
                    node *q = p;
                    p = (p->lc != NULL) ? p->lc : p->rc;
                    delete q;

                } else {
                    delete p;
                    p = NULL;
                }

            }
        } else {
            if (t < p->data) {
                remove(t,p->lc);
            } else {
                remove(t,p->rc);
            }
        }
    }

}

template <typename T>
void BinarySearchTree<T>::levelTraverse(std::ostream &os) const
{
    LinkQueue<node*> queue;
    queue.enqueue(root);
    while(!queue.isEmpty()) {
        node *t = queue.dequeue();
        if (t != NULL) {
            os << t->data << "  ";
            queue.enqueue(t->lc);
            queue.enqueue(t->rc);
        }
    }
}

#endif // BINARYSEARCHTREE_HPP


© 著作权归作者所有

首席吹牛官
粉丝 9
博文 368
码字总数 191938
作品 0
闵行
程序员
私信 提问
【javascript实现】几道题目带你学习二叉搜索树

二叉树大家都知道,二叉搜索树满足以下特征: 节点的左子树只包含小于当前节点的数 节点的右子树只包含大于当前节点的数 所有左子树和右子树自身必须也是二叉搜索树 二叉搜索树也叫二叉排序树...

陈小俊
2018/11/27
0
0
自己动手实现java数据结构(六)二叉搜索树

1.二叉搜索树介绍   前面我们已经介绍过了向量和链表。有序向量可以以二分查找的方式高效的查找特定元素,而缺点是插入删除的效率较低(需要整体移动内部元素);链表的优点在于插入,删除元...

小熊餐馆
01/24
0
0
数据结构-二叉搜索树和二叉树排序算法(python实现)

今天我们要介绍的是一种特殊的二叉树——二叉搜索树,同时我们也会讲到一种排序算法——二叉树排序算法。这两者之间有什么联系呢,我们一起来看一下吧。 开始之前呢,我们先来介绍一下如何创...

浩然haoran
08/05
0
0
B树文件系统树

二叉排序树或者二叉搜索树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其...

满小茂
2016/01/09
255
0
javascript算法之二叉搜索树

什么是二叉树 二叉树就是树的每个节点最多只能有两个子节点 什么是二叉搜索树 二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否...

光哥很霸气
2017/09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部