数据结构…本系列旨在对基础算法进行记录和学习,为了之后的面试一个弥补~~
本系列不是科普文,是为了找工作快速拾遗系列.
快速浏览,不会把学过的东西忘记~~
1.看图理解概念
图片已经经过原作者同意转载!
树的层次
树的结构
树的状态
二叉树
查找树
2.二叉查找树基本操作
简单的就不一一说明了,有几个难点会详细说明.
插入节点
遍历二叉树
前序遍历树a：10 5 4 3 6 15 16
前序遍历树b：5 3 2 4 8 7 9
中序遍历树a：3 4 5 6 10 15 16
中序遍历树b：2 3 4 5 7 8 9
后序遍历树a：3 4 6 5 16 15 10
后序遍历树b：2 4 3 7 9 8 5
中序前继
中序后继
先继和后继与遍历的方式联合起来说得,比如这里就是以中序遍历来说明情况.
这里与其用图来说明,不如直接上代码方便:
有左子树很简单就理解了,其它的两种情况是找规律问题,自己画个图结合代码一下子就理解了.
/*寻找中序遍历的前驱节点*/
/*
一个节点的前驱节点有3种情况：
1. 它有左子树，则左子树根节点为其前驱节点
2. 它没有左子树，且它本身为右子树，则其父节点为其前驱节点
3. 它没有左子树，且它本身为左子树，则它的前驱节点为“第一个拥有右子树的父节点”
*/
template <typename T>
BSNode<T>* BStree<T>::predecessor(BSNode<T>* pnode)
{
if (pnode->lchild != nullptr)
{//第一种情况
pnode = pnode->lchild;
while (pnode->rchild != nullptr)
{
pnode = pnode->rchild;
}
return pnode;
}
//第二/三种情况
BSNode<T>* pparent = pnode->parent;
while (pparent != nullptr && pparent->lchild == pnode)
{
pnode = pparent;
pparent = pparent->parent;
}
return pparent;
}
/*
一个节点的后继节点有3种情况：
它有右子树；则其后继节点为其右子树的最左节点
它没有右子树，但它本身是一个左孩子，则后继节点为它的双亲
它没有右子树，但它本身是一个右孩子，则其后继节点为“具有左孩子的最近父节点”
*/
template <typename T>
BSNode<T>* BStree<T>::successor(BSNode<T>* pnode)
{
if (pnode->rchild != nullptr)
{//第一种情况
pnode = pnode->rchild;
while (pnode->lchild != nullptr)
{
pnode = pnode->lchild;
}
return pnode;
}
BSNode<T>* pparent = pnode->parent;
while (pparent!=nullptr&& pparent->rchild == pnode)
{//第二/三种情况
pnode = pparent;
pparent = pparent->parent;
}
return pparent;
}
删除节点
这里是最难的一点,前面都很容易理解,这一点我看了好久.
先说一下原理,然后再结合代码看,那就容易理解了.
对与第二和第三种情况较为简单,这里只说明第一种情况.
解释说明
查找极值
总的代码:
#ifndef TREE_H
#define TREE_H
#include <iostream>
using namespace std;
//二叉查找树的节点结构
template<typename T>
struct BSNode
{
BSNode(T t):
value(t),lchild(nullptr),rchild(nullptr),parent(nullptr)
{}
BSNode() = default;
public:
T value;
BSNode<T>* lchild;
BSNode<T>* rchild;
BSNode<T>* parent;
};
//
template<typename T>
class BStree
{
public:
BStree();
~BStree();
void preOrder(); //前序遍历二叉树
void inOrder(); //中序遍历二叉树
void postOrder(); //后序遍历二叉树
//void layerOrder(); //层次遍历二叉树
BSNode<T>* search_recursion(T key); //递归地进行查找
//BSNode<T>* search_Iterator(T key); //迭代地进行查找
T search_minimun(); //查找最小元素
T search_maximum(); //查找最大元素
BSNode<T>* successor (BSNode<T>* x); //查找指定节点的后继节点
BSNode<T>* predecessor(BSNode<T>* pnode); //查找指定节点的前驱节点
void insert(T key); //插入指定值节点
void remove(T key); //删除指定值节点
void destory(); //销毁二叉树
//void print(); //打印二叉树
private:
BSNode<T>* root; //根节点
typedef BSNode<T>* pointer;//redefine
private:
BSNode<T>* search(BSNode<T>* & p, T key);
void remove(BSNode<T>* p, T key);
void preOrder(BSNode<T>* p);
void inOrder(BSNode<T>* p);
void postOrder(BSNode<T>* p);
//T search_minimun(BSNode<T>* p);
//T search_maximum(BSNode<T>* p);
void destory(BSNode<T>* &p);
};
/*默认构造函数*/
template<typename T>
BStree<T>::BStree():root(nullptr)
{}
/*析构函数*/
template<typename T>
BStree<T>::~BStree()
{
//destory(root);
}
/*插入函数*/
template<typename T>
void BStree<T>::insert(T key)
{
pointer pparent = nullptr;
pointer pnode = root;
//这里写的太复杂了,有很大的改进空间
//只讲原理和拾遗,不做过多说明
while (pnode != nullptr)
{//找到插入的母节点
pparent = pnode;
if (key>pnode->value)
pnode = pnode->rchild;
else if (key<pnode->value)
pnode = pnode->lchild;
else
break;
}
pnode = new BSNode<T>(key);
if(pparent == nullptr)
root = pnode;
else {//插入到母节点之后
if (key>pparent->value)
pparent->rchild = pnode;
else
pparent->lchild = pnode;
}
pnode->parent = pparent;//新节点指向母节点
}
/*前序遍历*/
template <typename T>
void BStree<T>::preOrder()
{
preOrder(root);
}
template <typename T>
void BStree<T>::preOrder(BSNode<T>* p)
{
if(p!=nullptr)
{
cout<<p->value<<endl;
preOrder(p->lchild);
preOrder(p->rchild);
}
}
/*中序遍历*/
template <typename T>
void BStree<T>::inOrder()
{
inOrder(root);
}
template<typename T>
void BStree<T>::inOrder(BSNode<T>* p)
{
if(p!=nullptr)
{
inOrder(p->lchild);
cout<<p->value<<endl;
inOrder(p->rchild);
}
}
/*后序遍历算法*/
template <typename T>
void BStree<T>::postOrder()
{
postOrder(root);
}
template <typename T>
void BStree<T>::postOrder(BSNode<T>* p)
{
if (p != nullptr)
{
postOrder(p->lchild);
postOrder(p->rchild);
cout << p->value<<endl;
}
}
/*寻找中序遍历的前驱节点*/
/*
一个节点的前驱节点有3种情况：
1. 它有左子树，则左子树根节点为其前驱节点
2. 它没有左子树，且它本身为右子树，则其父节点为其前驱节点
3. 它没有左子树，且它本身为左子树，则它的前驱节点为“第一个拥有右子树的父节点”
*/
template <typename T>
BSNode<T>* BStree<T>::predecessor(BSNode<T>* pnode)
{
if (pnode->lchild != nullptr)
{//第一种情况
pnode = pnode->lchild;
while (pnode->rchild != nullptr)
{
pnode = pnode->rchild;
}
return pnode;
}
//第二/三种情况
BSNode<T>* pparent = pnode->parent;
while (pparent != nullptr && pparent->lchild == pnode)
{
pnode = pparent;
pparent = pparent->parent;
}
return pparent;
}
/*
一个节点的后继节点有3种情况：
它有右子树；则其后继节点为其右子树的最左节点
它没有右子树，但它本身是一个左孩子，则后继节点为它的双亲
它没有右子树，但它本身是一个右孩子，则其后继节点为“具有左孩子的最近父节点”
*/
template <typename T>
BSNode<T>* BStree<T>::successor(BSNode<T>* pnode)
{
if (pnode->rchild != nullptr)
{//第一种情况
pnode = pnode->rchild;
while (pnode->lchild != nullptr)
{
pnode = pnode->lchild;
}
return pnode;
}
BSNode<T>* pparent = pnode->parent;
while (pparent!=nullptr&& pparent->rchild == pnode)
{//第二/三种情况
pnode = pparent;
pparent = pparent->parent;
}
return pparent;
}
/*销毁二叉树*/
template<typename T>
void BStree<T>::destory()
{
destory(root);
}
template <typename T>
void BStree<T>::destory(BSNode<T>* &p)
{
if (p != nullptr)
{
if (p->lchild != nullptr)
destory(p->lchild);
if (p->rchild != nullptr)
destory(p->rchild);
delete p;
p = nullptr;
}
}
/*删除指定节点*/
//---这里是最难理解的,文中会以图进行说明!
template <typename T>
void BStree<T>::remove(T key)
{
remove(root, key);
}
template <typename T>
void BStree<T>::remove(BSNode<T>* pnode, T key)
{
/*
//获取当前节点位置和前继信息
pointer new_temp = search(pnode,key);
pointer pre_temp = this->predecessor(new_temp);
if(new_temp->lchild==nullptr&&new_temp->rchild==nullptr)
{//没有子节点
bool flag =new_temp->parent->lchild==new_temp;
if (flag)
new_temp->parent->lchild = nullptr;
else
new_temp->parent->rchild = nullptr;
delete new_temp;
}
else if (new_temp->lchild==nullptr||new_temp->rchild==nullptr)
{
pointer next_child = new_temp->lchild==nullptr?new_temp->rchild:new_temp->lchild;
pointer pre_parent = new_temp->parent->lchild==new_temp?new_temp->rchild:new_temp->lchild;
pre_parent = next_child;
next_child->parent = pre_parent;
delete new_temp;
}
else
{
}*/
if (pnode != nullptr)
{
if (pnode->value == key)
{
BSNode<T>* pdel=nullptr;
if (pnode->lchild == nullptr || pnode->rchild == nullptr)
pdel = pnode; //情况二、三：被删节点只有左子树或右子树，或没有孩子
else
pdel = predecessor(pnode); //情况一：被删节点同时有左右子树，则删除该节点的前驱
//此时，被删节点只有一个孩子（或没有孩子）.保存该孩子指针
BSNode<T>* pchild=nullptr;
if (pdel->lchild != nullptr)
pchild = pdel->lchild;
else
pchild = pdel->rchild;
//让孩子指向被删除节点的父节点
if (pchild != nullptr)
pchild->parent = pdel->parent;
//如果要删除的节点是头节点，注意更改root的值
if (pdel->parent == nullptr)
root = pchild;
//如果要删除的节点不是头节点，要注意更改它的双亲节点指向新的孩子节点
else if (pdel->parent->lchild==pdel)
{
pdel->parent->lchild = pchild;
}
else
{
pdel->parent->rchild = pchild;
}
if (pnode->value != pdel->value)
pnode->value = pdel->value;
delete pdel;
}
//进行递归删除
else if (key > pnode->value)
{
remove(pnode->rchild, key);
}
else remove(pnode->lchild, key);
}
}
/*查找指定元素的节点（递归）*/
template <typename T>
BSNode<T>* BStree<T>::search_recursion(T key)
{
return search(root,key);
}
/*private:search()*/
/*递归查找的类内部实现*/
template <typename T>
BSNode<T>* BStree<T>::search(BSNode<T>* & pnode, T key)
{
pointer temp = pnode;
if (temp == nullptr)
return nullptr;
if (key > temp->value)
return search(temp->rchild,key);
else if(key<pnode->value)
return search(temp->lchild,key);
else
return temp;
}
#endif // TREE_H
注意C++的template只能在一个头文件,千万不要模块化编程一个在.h文件一个在.cpp文件!!!
参考资料:
