二叉搜索树也是二叉树，不过多了一些限定，根节点值大于左子树小于右子树，子树递归定义。
/************************************************
*
*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