C++二叉查找树实现及转化为双向链表
2024-08-25 19:46:40
二叉树首先要有树节点
template<class T>
class BinaryNode
{
public:
T element;
BinaryNode *left;
BinaryNode *right; public:
BinaryNode(T passelement);
~BinaryNode();
}; template<class T>
BinaryNode<T>::BinaryNode(T passelement)
{
this->element=passelement;
this->left=NULL;
this->right=NULL;
} template<class T>
BinaryNode<T>::~BinaryNode()
{
}
二叉树对象则比较复杂
template<class T>
class BinarySearchTree
{
private:
BinaryNode<T> *m_proot;
public:
const T findMin() const;//获取最小值
const T findMax() const;//获取最大值
bool contains(const T& xele) const;//判断是否包含
void makeEmpty();//清空二叉树
void insert(const T& xele);//插入
void remove(const T& xele);//删除
void inordertrav();//中序遍历
void toDoublelist();//转化为双向链表
void printDoublelist();//打印双向链表
public://构造与析构函数
BinarySearchTree();
BinarySearchTree(const BinarySearchTree& bst);
~BinarySearchTree();
private://全部用于递归调用
void makeEmpty(BinaryNode<T>* &t);
const T findMin(BinaryNode<T>* &t);
void remove(const T& xele, BinaryNode<T>* &t);
void insert(const T& xele, BinaryNode<T>* &t);
void inordertrav(BinaryNode<T>* &t);
void toDoublelist(BinaryNode<T>* &t);
BinaryNode<T>* getlLeftTail(BinaryNode<T>* &t);//获取左子树的最大节点
BinaryNode<T>* getlRightHead(BinaryNode<T>* &t);//获取右子树的最小节点
};
具体函数实现如下：
1.判断是否包含：
template<class T>
bool BinarySearchTree<T>::contains(const T& xele) const
{
BinaryNode<T>* pcurrent = m_proot;
while (true)
{
if (pcurrent == NULL)//指针为空
{
return false;
}
else if (xele < pcurrent->element)
pcurrent = pcurrent->left;
else if (xele > pcurrent->element)
pcurrent = pcurrent->right;
else
{
pcurrent = NULL;
return true;
}
} }
2.返回最小值：
template<class T>
const T BinarySearchTree<T>::findMin() const
{
BinaryNode<T>* m_pcurrent = m_proot;
while (m_pcurrent->left != NULL)
{
m_pcurrent = m_pcurrent->left;
}
return m_pcurrent->element;
}
或：
template<class T>
const T BinarySearchTree<T>::findMin(BinaryNode<T>* &t)
{
if (t == NULL)
return NULL;
if (t->left == NULL)
return t->element;
else
return findMin(t->left); }
template<class T>
const T BinarySearchTree<T>::findMin()
{
findMin(m_proot);
}
3.返回最大值：
template<class T>
const T BinarySearchTree<T>::findMax() const
{
BinaryNode<T>* m_pcurrent = m_proot;
while (m_pcurrent->right != NULL)
{
m_pcurrent = m_pcurrent->right;
}
return m_pcurrent->element;
}
4.清空：
template<class T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
if (t!=NULL)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
template<class T>
void BinarySearchTree<T>::makeEmpty()
{
makeEmpty(m_proot);
}
5.插入：
template<class T>
void BinarySearchTree<T>::insert(const T& xele, BinaryNode<T>* &t)
{
if (t == NULL)
t = new BinaryNode<T>(xele);
else if (xele < t->element)
return insert(xele, t->left);
else if (xele > t->element)
return insert(xele, t->right);
else
;
}
template<class T>
void BinarySearchTree<T>::insert(const T& xele)
{
insert(xele, m_proot);
}
6.删除:
template<class T>
void BinarySearchTree<T>::remove(const T& xele, BinaryNode<T>* &t)
{
if (t == NULL)
return;
else if (xele < t->element)
remove(xele, t->left);
else if (xele > t->element)
remove(xele, t->right);
else
{
if (t->left != NULL&&t->right != NULL)
{
t->element = findMin(t->right);
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>::remove(const T& xele)
{
remove(xele, m_proot);
}
7.中序遍历：
template<class T>
void BinarySearchTree<T>::inordertrav()
{
inordertrav(m_proot);
}
template<class T>
void BinarySearchTree<T>::inordertrav(BinaryNode<T>* &t)//参数是根节点
{
if (NULL == t)
return;
if (NULL != t->left)
inordertrav(t->left);
cout << t->element << "," << endl;
if (NULL != t->right)
inordertrav(t->right);
}
8.转换为双向链表，需要注意的是：不能使用中序遍历的方法去实现转换，这样会引起指针异常；转换后以前操作二叉树的函数全部失效
template<class T>
BinaryNode<T>* BinarySearchTree<T>::getlLeftTail(BinaryNode<T>* &t)
{
BinaryNode<T>* pC = t;
while (true)
if (NULL != pC->right)
pC = pC->right;
else
break;
return pC;
}
template<class T>
BinaryNode<T>* BinarySearchTree<T>::getlRightHead(BinaryNode<T>* &t)
{
BinaryNode<T>* pC = t;
while (true)
if (NULL != pC->left)
pC = pC->left;
else
break;
return pC;
}
template<class T>
void BinarySearchTree<T>::toDoublelist()
{
toDoublelist(m_proot);
}
template<class T>
void BinarySearchTree<T>::toDoublelist(BinaryNode<T>* &t)
{ if (NULL == t)
return;
if (NULL != t->left)
{
BinaryNode<T>* listtail = getlLeftTail(t->left);//先记录下来要与根节点的左指针相连的。
toDoublelist(t->left);
listtail->right = t;
t->left = listtail;
} /*这个方法会出现问题
//不为空
if (NULL != m_plist)
{
t->left = m_plist;
m_plist->right = t;
}
else//为空表示使双向链表的头
{
m_phead = t;
}
//为下一次连接做准备
m_plist = t; cout << m_plist->element << ",";*/ if (NULL != t->right)
{
BinaryNode<T>* listhead = getlRightHead(t->right);
toDoublelist(t->right);
listhead->left = t;
t->right = listhead; } }
9.打印链表：
template<class T>
void BinarySearchTree<T>::printDoublelist()
{
BinaryNode<T>* phead = m_proot;
while (true)
{
if (phead->left != NULL)
phead = phead->left;
else
break;
}
while (phead->right!=NULL)
{
cout << phead->element << ",";
phead = phead->right;
}
cout << phead->element;
}
最新文章
- .Net Core--目录
- IOS开发-第三方SDWebImage下载网络图片的使用
- C语言中的fread和fwrite
- 工作总结：VS2010/MFC编程入门之十六（对话框：消息对话框）
- JSON C# Class Generator是一个从JSON文本中生成C#内的应用程序
- SpringMVC轻松学习-环境搭建（二）
- iOS开发之计算文字尺寸
- 简单聊聊不可或缺的Nginx反向代理服务器--实现负载均衡【上篇】
- LNMP1.4 PHP升级脚本
- linux 下的文件目录操作之遍历目录
- Shell脚本实现文件遍历和删除操作
- Asp.Net Core&Docker部署到树莓派3B中
- Py之Crawler：爬虫利用随机选取代理访问服务器的方法实现下载某网址上所有的图片到指定文件夹——Jason niu
- openCV 简单实现身高测量（未考虑相机标定，windows）
- B. Vova and Trophies 字符串预处理+思维+贪心
- BZOJ4451 [Cerc2015]Frightful Formula 多项式 FFT 递推 组合数学
- 《图解Java多线程设计模式》读书笔记
- Windbg程序调试系列1-Mex扩展使用总结
- Turing equation
- SQL Server 并发死锁解决案例备忘