二叉搜索树源码分享
#include <iostream>
using namespace std;
//枚举类,前中后三种遍历方式
enum ORDER_MODE
{
ORDER_MODE_PREV = 0,
ORDER_MODE_MID,
ORDER_MODE_POST
};
//树节点的结构体
template <class T>
struct BinaryNode
{
T element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const T& theElement,
BinaryNode *lt,
BinaryNode *rt):
element(theElement),
left(lt),
right(rt)
{
}
};
template <class T>
class BinarySearchTree
{
private:
BinaryNode<T> *m_root;
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree& rhs);
~BinarySearchTree();
const T& findMin() const;
const T& findMax() const;
bool contains(const T& x) const;
void printTree(ORDER_MODE eOrderMode = ORDER_MODE_PREV) const;
void makeEmpty();
void insert(const T& x);
void remove(const T& x);
private:
void insert(const T& x, BinaryNode<T>* &t) ;
void remove(const T& x, BinaryNode<T>* &t) ;
BinaryNode<T>* findMin( BinaryNode<T>* t) const;
BinaryNode<T>* findMax( BinaryNode<T>* t) const;
bool contains(const T& x, const BinaryNode<T>* t) const;
void makeEmpty(BinaryNode<T>* &t);
void printTreeInPrev(BinaryNode<T>* t) const;
void printTreeInMid(BinaryNode<T>* t)const;
void printTreeInPost(BinaryNode<T>* t)const;
};
//构造方法
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
m_root = NULL;
}
//使用另一棵二叉搜索树的构造函数
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
m_root = rhs.m_root;
}
//析构函数,释放内存
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
makeEmpty();
}
// 判断x元素是否存在
template <class T>
bool BinarySearchTree<T>::contains(const T& x) const
{
return contains(x, m_root);
}
//递归调用
template <class T>
bool BinarySearchTree<T>::contains(const T& x, const BinaryNode<T>* t) const
{
if (!t)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (x > t->element)
return contains(x, t->right);
else
return true;
}
// 寻找树中的最小值
template <class T>
const T& BinarySearchTree<T>::findMin() const
{
return findMin(m_root)->element;
}
//递归搜索树中最小值
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMin( BinaryNode<T>* t) const
{
//二叉树的一个特点就是左子叶的值比根节点小, 右子叶的比根节点的大
if (!t)
return NULL;
if (t->left == NULL)
return t;
else
return findMin(t->left);
}
// 寻找树中最大值
template <class T>
const T& BinarySearchTree<T>::findMax() const
{
return findMax(m_root)->element;
}
//递归寻找树中最大值
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMax( BinaryNode<T>* t) const
{
//二叉树的一个特点就是左子叶的值比根节点小, 右子叶的比根节点的大
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
// 插入元素
template <class T>
void BinarySearchTree<T>:: insert(const T& x)
{
insert(x, m_root);
}
//递归插入
template <class T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
t = new BinaryNode<T>(x, NULL, NULL);//注意这个指针参数是引用
else if (x < t->element)
insert(x, t->left);
else if (x > t->element)
insert(x, t->right);
else
;//do nothing
}
//移除元素
template <class T>
void BinarySearchTree<T>::remove(const T& x)
{
return remove(x, m_root);
}
//递归移除
template <class T>
void BinarySearchTree<T>::remove(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
return;
if (x < t->element)
remove(x, t->left);
else if (x > t->element)
remove (x, t->right);
else // now ==
{
if (t->left != NULL &&
t->right != NULL)//two child
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode<T> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
}
//清空二叉树
template <class T>
void BinarySearchTree<T>::makeEmpty()
{
makeEmpty(m_root);
}
//递归清空
template <class T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
if (t)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
// 打印二叉搜索树
template <class T>
void BinarySearchTree<T>::printTree(ORDER_MODE eOrderMode /*= ORDER_MODE_PREV*/) const
{
if (ORDER_MODE_PREV == eOrderMode)
printTreeInPrev(m_root);
else if (ORDER_MODE_MID == eOrderMode)
printTreeInMid(m_root);
else if (ORDER_MODE_POST == eOrderMode)
printTreeInPost(m_root);
else
;//do nothing
}
//前序打印
template <class T>
void BinarySearchTree<T>::printTreeInPrev(BinaryNode<T>* t) const
{
if (t)
{
cout << t->element;
printTreeInPrev(t->left);
printTreeInPrev(t->right);
}
}
//中序打印
template <class T>
void BinarySearchTree<T>::printTreeInMid(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPrev(t->left);
cout << t->element;
printTreeInPrev(t->right);
}
}
//后序打印
template <class T>
void BinarySearchTree<T>::printTreeInPost(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPost(t->left);
printTreeInPost(t->right);
cout << t->element;
}
}
```
测试代码
===
```C++
#include "BinarySearchTree.h"
int main()
{
BinarySearchTree<int> binaryTree;
binaryTree.insert(5);
binaryTree.insert(1);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(6);
binaryTree.insert(8);
//测试前中后序打印
cout <<endl<<"前序:"<<endl;
binaryTree.printTree(ORDER_MODE_PREV);
cout <<endl<<"中序:"<<endl;
binaryTree.printTree(ORDER_MODE_MID);
cout <<endl<<"后序:"<<endl;
binaryTree.printTree(ORDER_MODE_POST);
cout <<endl;
//测试基本操作
bool b = binaryTree.contains(1);
cout<< "是否存在1:"<<b<<endl;
int x = binaryTree.findMin();
cout << "最小值为:"<< x <<endl;
x = binaryTree.findMax();
cout << "最大值为:"<< x <<endl;
binaryTree.remove(2);
cout << "移除元素2之后"<<endl;
//测试前中后序打印
cout <<endl<<"前序:"<<endl;
binaryTree.printTree(ORDER_MODE_PREV);
cout <<endl<<"中序:"<<endl;
binaryTree.printTree(ORDER_MODE_MID);
cout <<endl<<"后序:"<<endl;
binaryTree.printTree(ORDER_MODE_POST);
cout <<endl;
return 0;
}
相关文章
- 这篇文章主要给大家介绍了关于如何利用JavaScript实现二叉搜索树的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-03
- 这篇文章主要介绍了C#创建二叉搜索树的方法,涉及C#二叉搜索树的实现技巧,非常具有实用价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细介绍了JavaScript实现二叉搜索树,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-03-07
- 这篇文章主要介绍了Java 求解把二叉搜索树转换为累加树的代码,总之需要观察示例节点的规律,需要记录上个节点的情况,注意引入前驱节点pre,具体实例代码跟随小编一起看看吧...2021-11-03
- 这篇文章主要介绍了C++实现LeetCode(98.验证二叉搜索树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-20
- 这篇文章主要介绍了二叉搜索树源码,需要的朋友可以参考下...2020-04-25
C++实现LeetCode(109.将有序链表转为二叉搜索树)
这篇文章主要介绍了C++实现LeetCode(109.将有序链表转为二叉搜索树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-23- 这篇文章主要介绍了C语言判定一棵二叉树是否为二叉搜索树的方法,结合实例形式综合对比分析了C语言针对二叉搜索树判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#二叉搜索树插入算法,实例分析了C#二叉树操作的相关技巧,需要的朋友可以参考下...2020-06-25
- 添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构...2020-04-25
- 跟着思路走,之后从简单题入手,反复去看,做过之后可能会忘记,之后再做一次,记不住就反复做,反复寻求思路和规律,慢慢积累就会发现质的变化...2022-03-18
剑指Offer之Java算法习题精讲字符串操作与数组及二叉搜索树
跟着思路走,之后从简单题入手,反复去看,做过之后可能会忘记,之后再做一次,记不住就反复做,反复寻求思路和规律,慢慢积累就会发现质的变化...2022-03-18- 二叉树是一种非常重要的数据结构,它同时具有数组和链表各自的特点,下面这篇文章主要给大家介绍了关于java基础二叉搜索树的相关资料,文中通过实例代码介绍的非常详细,需要的朋友可以参考下...2022-03-10