|
【
????????写在前面的话：本专栏的主要内容：数据结构与算法。
????????1.对于???????初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到专栏前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们从本专栏的总揽???????按顺序进行学习；
???????????????2.对于想查询有关资料的小伙伴们，可以选择性地浏览。希望小伙伴们都能有所收获～
?? ???????】? ?
????????上一篇笔者介绍了二叉树的一些基本概念，本节主要介绍如何构建二叉树。
? ? ? ? 二叉树的构建相比前面学的数据结构更为复杂，代码中提供了详尽的注释，请读者细细体会。
? ? ? ? 二叉树中最重要的三种算法：先序遍历算法???????，中序遍历算法???????，后序遍历算法。
? ? ? ? 下面的BinNode.h描述了二叉树结点具有的基本的结构。
/*
*
* 作者：易果啥笔
* 时间：2021.8.20
* 内容：二叉树结点模版类
*
*
*/
#ifndef STACK_BINNODE_H
#define STACK_BINNODE_H
#include <cstdlib>
#include "Queue.h"
#include "Stack.h"
/******************************************************************************************
* BinNode状态与性质的判断
******************************************************************************************/
#define IsRoot(x) ( ! ( (x).parent ) )
#define IsLChild(x) ( ! IsRoot(x) && ( & (x) == (x).parent->lc ) )
#define IsRChild(x) ( ! IsRoot(x) && ( & (x) == (x).parent->rc ) )
#define HasParent(x) ( ! IsRoot(x) )
#define HasLChild(x) ( (x).lc )
#define HasRChild(x) ( (x).rc )
#define HasChild(x) ( HasLChild(x) || HasRChild(x) ) //至少拥有一个孩子
#define HasBothChild(x) ( HasLChild(x) && HasRChild(x) ) //同时拥有两个孩子
#define IsLeaf(x) ( ! HasChild(x) )
/******************************************************************************************
* 与BinNode具有特定关系的节点及指针
******************************************************************************************/
#define sibling( p ) ( IsLChild( * (p) ) ? (p)->parent->rc : (p)->parent->lc ) /*兄弟*/
#define uncle( x ) ( sibling( (x)->parent ) ) /*叔叔*/
#define FromParentTo( x ) /*来自父亲的引用*/ ( IsRoot(x) ? _root : ( IsLChild(x) ? (x).parent->lc : (x).parent->rc ) )
#define stature(p) ((p) ? (p)->height : -1) //其余BST中节点的高度（NUll视作空树，对应于-1）
template <typename T> struct BinNode { //二叉树节点模板类
// 成员
T data; //数值
BinNode<T>* parent;
BinNode<T>* lc;
BinNode<T>* rc; //父节点及左、右孩子
int height; //高度（通用）
// 构造函数
BinNode() :
parent (nullptr) , lc (nullptr) , rc ( nullptr ), height ( 0 ) { }
BinNode ( T e, BinNode<T>* p = nullptr, BinNode<T>* lc = nullptr, BinNode<T>* rc = nullptr,
int h = 0, int l = 1) :
data ( e ), parent ( p ), lc ( lc ), rc ( rc ), height ( h ){ }
// 操作接口
BinNode<T>* succ(); //取当前结点的直接后继
BinNode<T>* insertAsLC ( T const & ); //作为当前节点的左孩子插入新节点
BinNode<T>* insertAsRC ( T const & ); //作为当前节点的右孩子插入新节点
void travLevel ( void (* visit)(T&) ); //子树层次遍历
void travPre ( void (* visit)(T&) ); //子树先序遍历
void travIn ( void (* visit)(T&) ); //子树中序遍历
void travPost ( void (* visit)(T&) ); //子树后序遍历
};
/*
*
* 作者：易果啥笔
* 时间：2021.8.21
* 内容：二叉树结点模版类接口的实现
*
*
*/
template <typename T> BinNode<T>* BinNode<T>::insertAsLC ( T const& e )
{ return lc = new BinNode ( e, this ); } //将e作为当前节点的左孩子插入二叉树
template <typename T> BinNode<T>* BinNode<T>::insertAsRC ( T const& e )
{ return rc = new BinNode ( e, this ); } //将e作为当前节点的右孩子插入二叉树
template <typename T> BinNode<T>* BinNode<T>::succ() { //定位节点v的直接后继
BinNode<T> *s = this; //记录后继的临时变量
if (rc) { //若有右孩子，则直接后继必在右子树中，具体地就是
s = rc; //右子树中
while (HasLChild (*s)) s = s->lc; //最靠左（最小）的节点
} else { //否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”，具体地就是
while (IsRChild (*s)) s = s->parent; //逆向地沿右向分支，不断朝左上方移动
s = s->parent; //最后再朝右上方移动一步，即抵达直接后继（如果存在）
}
return s;
}
/*
*
* 先序遍历
*
*/
//递归版
template <typename T>
void travPre_R(BinNode<T>* x,void (* visit)(T&)){ //递归版
if(!x){ return;}
visit(x->data);
travPost_R(x->lc,visit);
travPost_R(x->rc,visit);
}
//迭代版1
template <typename T>
void travPre_I1(BinNode<T>* x,void (* visit)(T&)){
Stack<BinNode<T>*> S;
if(x){S.push(x); };
while(!S.Empty()){
x = S.pop();
visit(x->data);
if(HasRChild(*x)) S.push(x->rc);
if(HasLChild(*x)) S.push(x->lc);
}
}
//迭代版2
//从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问
template <typename T>
static void visitAlongVine ( BinNode<T>* x, void (* visit)(T&), Stack<BinNode<T>*>& S ) {
while ( x ) {
visit ( x->data ); //访问当前节点
S.push ( x->rc ); //右孩子入栈暂存（可优化：通过判断，避免空的右孩子入栈）
x = x->lc; //沿左分支深入一层
}
}
template <typename T>
void travPre_I2 ( BinNode<T>* x, void (* visit)(T&) ) {
Stack<BinNode<T>*> S; //辅助栈
while ( true ) {
visitAlongVine ( x, visit, S ); //从当前节点出发，逐批访问
if ( S.Empty() ) break; //直到栈空
x = S.pop(); //弹出下一批的起点
}
}
template <typename T>
void BinNode<T>::travPre ( void (* visit)(T&) ) { //二叉树先序遍历算法统一入口
switch ( rand() % 3 ) { //此处暂随机选择以做测试，共三种选择
case 0: travPre_I1 ( this, visit ); break; //迭代版1
case 1: travPre_I2 ( this, visit ); break; //迭代版2
default: travPre_R ( this, visit ); break; //递归版
}
}
/*
*
* 中序遍历
*
*/
//递归版
template <typename T> //元素类型、操作器
void travIn_R(BinNode<T>* x,void (* visit)(T&)){
if(!x){ return;}
travPost_R(x->lc,visit);
visit(x->data);
travPost_R(x->rc,visit);
}
//迭代版1
template <typename T> //从当前节点出发，沿左分支不断深入，直至没有左分支的节点
static void goAlongVine ( BinNode<T>* x, Stack<BinNode<T>*>& S ) {
while ( x ) { S.push ( x ); x = x->lc; } //当前节点入栈后随即向左侧分支深入，迭代直到无左孩子
}
template <typename T>
void travIn_I1 ( BinNode<T>* x, void (* visit)(T&) ) {
Stack<BinNode<T>*> S; //辅助栈
while ( true ) {
goAlongVine ( x, S ); //从当前节点出发，逐批入栈
if ( S.Empty() ) break; //直至所有节点处理完毕
x = S.pop(); visit ( x->data ); //弹出栈顶节点并访问之
x = x->rc; //转向右子树
}
}
//迭代版2
template <typename T>
void travIn_I2 ( BinNode<T>* x, void (* visit)(T&) ) {
Stack<BinNode<T>*> S; //辅助栈
while ( true )
if ( x ) {
S.push ( x ); //根节点进栈
x = x->lc; //深入遍历左子树
} else if ( !S.Empty() ) {
x = S.pop(); //尚未访问的最低祖先节点退栈
visit ( x->data ); //访问该祖先节点
x = x->rc; //遍历祖先的右子树
} else
break; //遍历完成
}
//迭代版3
template <typename T>
void travIn_I3 ( BinNode<T>* x, void (* visit)(T&) ) {
bool backtrack = false; //前一步是否刚从左子树回溯——省去栈，仅O(1)辅助空间
while ( true )
if ( !backtrack && HasLChild ( *x ) ) //若有左子树且不是刚刚回溯，则
x = x->lc; //深入遍历左子树
else { //否则——无左子树或刚刚回溯（相当于无左子树）
visit ( x->data ); //访问该节点
if ( HasRChild ( *x ) ) { //若其右子树非空，则
x = x->rc; //深入右子树继续遍历
backtrack = false; //并关闭回溯标志
} else { //若右子树空，则
if ( ! ( x = x->succ() ) ) break; //回溯（含抵达末节点时的退出返回）
backtrack = true; //并设置回溯标志
}
}
}
//二叉树中序遍历算法统一入口
template <typename T>
void BinNode<T>::travIn ( void (* visit)(T&) ) {
switch ( rand() % 4 ) { //此处暂随机选择以做测试，共四种选择
case 0: travIn_I1 ( this, visit ); break; //迭代版1
case 1: travIn_I2 ( this, visit ); break; //迭代版2
case 2: travIn_I3 ( this, visit ); break; //迭代版3
default: travIn_R ( this, visit ); break; //递归版
}
}
/*
*
* 后序遍历
*
*/
//递归版
template <typename T> //元素类型、操作器
void travPost_R(BinNode<T>* x,void (* visit)(T&)){
if(!x){ return;}
travPost_R(x->lc,visit);
travPost_R(x->rc,visit);
visit(x->data);
}
//迭代版
template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
static void gotoLeftmostLeaf ( Stack<BinNode<T>*>& S ) { //沿途所遇节点依次入栈
while ( BinNode<T>* x = S.top() ) //自顶而下，反复检查当前节点（即栈顶）
if ( HasLChild ( *x ) ) { //尽可能向左
if ( HasRChild ( *x ) ) S.push ( x->rc ); //若有右孩子，优先入栈
S.push ( x->lc ); //然后才转至左孩子
} else //实不得已
S.push ( x->rc ); //才向右
S.pop(); //返回之前，弹出栈顶的空节点
}
template <typename T>
void travPost_I ( BinNode<T>* x, void (* visit)(T&) ) { //二叉树的后序遍历（迭代版）
Stack<BinNode<T>*> S; //辅助栈
if ( x ) S.push ( x ); //根节点入栈
while ( !S.Empty() ) { //x始终为当前节点
if ( S.top() != x->parent ) 若栈顶非x之父（而为右兄）
gotoLeftmostLeaf ( S ); //则在其右兄子树中找到HLVFL（相当于递归深入）
x = S.pop(); visit ( x->data ); //弹出栈顶（即前一节点之后继），并访问之
}
}
template <typename T>
void BinNode<T>::travPost ( void (* visit)(T&) ) { //二叉树中序遍历算法统一入口
switch ( rand() % 2 ) { //此处暂随机选择以做测试
case 0: travPost_I ( this, visit ); break; //迭代版
default: travPost_R ( this, visit ); break; //递归版
}
}
/*
*
* 层次遍历
*
*/
template<typename T>
void BinNode<T>::travLevel(void (* visit)(T&)) { //二叉树层次遍历算法
Queue<BinNode<T>*> Q; //辅助队列
Q.enqueue(this); //根结点入队
while (!Q.empty()){
BinNode<T>* x = Q.dequeue();
visit(x->data);
if(HasLChild(*x)) Q.enqueue(x->lc);
if(HasRChild(*x)) Q.enqueue(x->rc);
}
}
#endif //STACK_BINNODE_H
? ? ? ? 在该算法中，对于先序遍历，中序遍历，后序遍历，笔者提供了多种实现（迭代+递归），请读者细细体会不同算法间有何相同，相异之处，效率是否相同。此外，算法中还包含了前面学过的Stack.h，Queue.h等头文件，具体可参考?Stack，Queue。
????????接着，来构建二叉树结点之间的逻辑关系：
/*
*
* 作者：易果啥笔
* 时间：2021.8.21
* 内容：二叉树模版类
*
*
*/
#ifndef STACK_BINTREE_H
#define STACK_BINTREE_H
#include "BinNode.h"
template <typename T> class BinTree {
protected:
int _size_; BinNode<T>* _root; //规模、根节点
virtual int updateHeight ( BinNode<T>* x ); //更新节点x的高度
void updateHeightAbove ( BinNode<T>* x ); //更新节点x及其祖先的高度
public:
BinTree() : _size_ ( 0 ), _root ( NULL ) { } //构造函数
~BinTree() { if ( 0 < _size_ ) remove ( _root ); } //析构函数
int size() const { return _size_; } //规模
bool empty() const { return !_root; } //判空
BinNode<T>* root() const { return _root; } //树根
BinNode<T>* insert ( T const & ); //插入根节点
BinNode<T>* insert ( T const &, BinNode<T>* ); //插入左孩子
BinNode<T>* insert ( BinNode<T>*, T const & ); //插入右孩子
int remove ( BinNode<T>* ); //子树删除
BinTree<T>* secede ( BinNode<T>* ); //子树分离
void travLevel ( void (* visit)(T&) ) { if ( _root ) _root->travLevel ( visit ); } //层次遍历
void travPre ( void (* visit)(T&) ) { if ( _root ) _root->travPre ( visit ); } //先序遍历
void travIn ( void (* visit)(T&) ) { if ( _root ) _root->travIn ( visit ); } //中序遍历
void travPost ( void (* visit)(T&) ) { if ( _root ) _root->travPost ( visit ); } //后序遍历
bool operator< ( BinTree<T> const& t ) //比较器
{ return _root && t._root && lt ( _root, t._root ); }
bool operator== ( BinTree<T> const& t ) //判等器
{ return _root && t._root && ( _root == t._root ); }
}; //BinTree
/*
*
* 作者：易果啥笔
* 时间：2021.8.21
* 内容：二叉树模版类接口的实现
*
*
*/
template <typename T> int BinTree<T>::updateHeight ( BinNode<T>* x ) //更新节点x高度
{ return x->height = 1 + max ( stature ( x->lc ), stature ( x->rc ) ); } //具体规则，因树而异
template <typename T> void BinTree<T>::updateHeightAbove ( BinNode<T>* x ) //更新高度
{ while ( x ) { updateHeight ( x ); x = x->parent; } } //从x出发，覆盖历代祖先。可优化
template <typename T> BinNode<T>* BinTree<T>::insert ( T const& e )
{ _size_ = 1; return _root = new BinNode<T> ( e ); } //将e当作根节点插入空的二叉树
template <typename T> BinNode<T>* BinTree<T>::insert ( T const& e, BinNode<T>* x )
{ _size_++; x->insertAsLC ( e ); updateHeightAbove ( x ); return x->lc; } //e插入为x的左孩子
template <typename T> BinNode<T>* BinTree<T>::insert ( BinNode<T>* x, T const& e )
{ _size_++; x->insertAsRC ( e ); updateHeightAbove ( x ); return x->rc; } //e插入为x的右孩子
template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
int BinTree<T>::remove ( BinNode<T>* x ) { //assert: x为二叉树中的合法位置
FromParentTo ( *x ) = NULL; //切断来自父节点的指针
updateHeightAbove ( x->parent ); //更新祖先高度
int n = removeAt ( x ); _size_ -= n; return n; //删除子树x，更新规模，返回删除节点总数
}
template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
static int removeAt ( BinNode<T>* x ) { //assert: x为二叉树中的合法位置
if ( !x ) return 0; //递归基：空树
int n = 1 + removeAt ( x->lc ) + removeAt ( x->rc ); //递归释放左、右子树
free ( x ); return n; //释放被摘除节点，并返回删除节点总数
}
template <typename T> //二叉树子树分离算法：将子树x从当前树中摘除，将其封装为一棵独立子树返回
BinTree<T>* BinTree<T>::secede ( BinNode<T>* x ) { //assert: x为二叉树中的合法位置
FromParentTo ( *x ) = NULL; //切断来自父节点的指针
updateHeightAbove ( x->parent ); //更新原树中所有祖先的高度
BinTree<T>* S = new BinTree<T>; S->_root = x; x->parent = NULL; //新树以x为根
S->_size_ = size(); _size_ -= S->_size_; return S; //更新规模，返回分离出来的子树
}
#endif //STACK_BINTREE_H
? ? ? ? 这样，二叉树便构建完毕。我们用一个main.cpp来测试一下：
/*
*
* 作者：易果啥笔
* 时间：2021.8.21
* 内容：二叉树模版类的使用
*
*
*/
#include <iostream>
#include "BinTree.h"
template<typename T> void print(T a){
std::cout<<a<<" ";
}
int main(){
//构建二叉树
BinTree<int> binTree;
//添加数据
binTree.insert(1);
binTree.insert(binTree.root(),3);
binTree.insert(2,binTree.root());
binTree.insert(4,binTree.root()->succ());
binTree.insert(binTree.root()->succ(),5);
binTree.insert(6,binTree.root()->succ()->succ());
binTree.insert(binTree.root()->succ()->succ(),7);
//remove()删除指定结点及其子树
binTree.remove(binTree.root()->succ()->succ());
//四种遍历方式
cout<<"层次遍历：";
binTree.travLevel(print);
cout<<endl;
cout<<"先序遍历：";
binTree.travPre(print);
cout<<endl;
cout<<"中序遍历：";
binTree.travIn(print);
cout<<endl;
cout<<"后序遍历：";
binTree.travPost(print);
cout<<endl;
//size()返回二叉树结点总数
cout<<"该二叉树共有"<<binTree.size()<<"个结点."<<endl;
//secede()分离子树
BinTree<int>* S = binTree.secede(binTree.root()->succ());
S->travLevel(print);
return 0;
}
????????
|