数据结构-二叉树

本篇文章整理《数据结构(C++语言版)》关于二叉树这种线性结构知识点。

二叉树

关于二叉树的概念,图论中有详细说明,这里不过多解释。
结构上而言,二叉树与列表类似。可以将二叉树理解为半线性结构

二叉树节点

与列表节点的前驱后继相似,二叉树也有祖先parent,左孩子lChild,右孩子rChild以及存储具体值的data。
二叉树节点结构
因此,二叉树节点BinNode实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define BinNodePosi(T) BinNode<T>*

template<typename T>
struct BinNode<T> {
T data; //数值
BinNodePosi(T) parent; BinNodePosi(T) lChild; BinNodePosi(T) rChild; //祖先,左右孩子
int height; //高度
//构造函数,列表初始化
BinNode() :
parent(NULL), lChild(NULL), rChild(NULL) {}
BinNode(T e, BinNodePosi(T) p=NULL, BinNodePosi(T) lc=NULL, BinNodePosi(T) rc=NULL,
int h=0) :
data(e), parent(p), lChild(lc), rChild(rc), height(h) {}
//操作接口
int size(); //统计当前节点后代总数,亦即以其为根的子树的规模
BinNodePosi(T) insertAsLC ( T const& ); //作为当前节点的左孩子插入新节点
BinNodePosi(T) insertAsRC ( T const& ); //作为当前节点的右孩子插入新节点
BinNodePosi(T) succ(); //取当前节点的直接后继
template <typename VST> void travLevel ( VST& ); //子树层次遍历
template <typename VST> void travPre ( VST& ); //子树先序遍历
template <typename VST> void travIn ( VST& ); //子树中序遍历
template <typename VST> void travPost ( VST& ); //子树后序遍历
}

插入左孩子insertAsLC为例,介绍如何插入一个新的二叉树节点。
通过调用BinNode节点中的构造函数,新建一个BinNode节点,其中{data=e, parent=this, lChild=NULL, rChild=NULL}。随后,再将当前节点的左孩子指向新建的节点即可。
insertAsLC操作
具体代码如下:

1
2
3
4
template <typename T> 
BinNodePosi(T) insertAsLC(T const& e) {
return lChild = new BinNode(e, this);
}

遍历算法

先序遍历

先序遍历,即先访问根节点,再依次访问左子树与右子树。
算法1:借助栈结构。访问当前根节点,随后先将其右子树压入栈中,再将左子树压入栈中,随后弹出栈顶元素(左孩子),重复上述操作。
先序遍历
代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
//version 1
template<typename T, typename VST>
void travPre_I1(BinNodePosi(T) x, VST & visit) {
stack<BinNodePosi(T)> S; //辅助栈
if(x) S.push(x); //根节点入栈
while(!S.empty()) {
x = S.pop(); visit( x->data );
if( HasRChild(*x) ) S.push(x->rChild);
if( HasLChild(*x) ) S.push(x->lChild);
}
}

算法2(推广至中序遍历甚至后序遍历等):如下图所示,整个二叉树遍历可以看做是一个简化的左子树链。对于每个节点而言,先扫描当前节点,继而扫描其左孩子,当所有左子树的左孩子扫描完成后,以当前节点的右孩子当做新的左子树链,重复上述操作。
左侧链
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//version 2
//左子树链的实现
template<typename T, typename VST>
static void visitAlongLeftBranch(BinNodePosi(T) x,
VST & visit,
stack<BinNodePosi(T)> & S)
{
while(x) {
visit(x->data);
S.push(x->rChild); //右孩子入栈
x = x->lChild;
}
}

//主算法实现
template<typename T, typename VST>
void travPre_I2(BinNodePosi(T) x, VST & visit) {
stack<BinNodePosi(T) S;
S.push(x); //当前节点入栈
while(!S.empty()) {
visitAlongLfetBranch(x, visit, S);
//左子树链中所有左孩子遍历完成后,进入最后一个右孩子重新构造左子树链,重新遍历
x = S.pop();
}
}

中序遍历

中序遍历,即依次访问左孩子,当前节点,右孩子。
算法:如下图所示,节点优先权会依次传递给左子树链最后一个左孩子,随后,访问其右子树,重复操作。
image.png

本文标题:数据结构-二叉树

文章作者:Lumo Wang

发布时间:2018年03月05日 - 14:03

最后更新:2019年04月17日 - 20:04

原始链接:https://luameows.github.io/2018/03/05/学习笔记-数据结构-二叉树/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~