[TOC]
写在前面
本篇文章整理《数据结构(C++语言版)》关于二叉树这种线性结构知识点。
整个数据结构部分章节列表如下:
1 向量
-- 1.1 遍历
-- 1.2 唯一化
-- 1.3 查找
2 列表
-- 2.1 列表节点
---- 2.1.1前插入算法
-- 2.2 列表模板类
---- 2.2.1 列表初始化
3 栈
-- 3.1 栈应用
---- 3.1.1 括号匹配
---- 3.1.2 栈混洗甄别
---- 3.1.3 中缀表达式
4 队列
5 二叉树
-- 5.1 二叉树节点
-- 5.2 遍历算法
---- 5.2.1 先序遍历
---- 5.2.2 中序遍历
5 二叉树
关于二叉树的概念,图论中有详细说明,这里不过多解释。
结构上而言,二叉树与列表类似。可以将二叉树理解为半线性结构。
5.1 二叉树节点
与列表节点的前驱后继相似,二叉树也有祖先parent,左孩子lChild,右孩子rChild以及存储具体值的data。
二叉树节点结构
因此,二叉树节点BinNode实现如下:
#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}。随后,再将当前节点的左孩子指向新建的节点即可。
具体代码如下:
template <typename T>
BinNodePosi(T) insertAsLC(T const& e) {
return lChild = new BinNode(e, this);
}
5.2 遍历算法
5.2.1 先序遍历
先序遍历,即先访问根节点,再依次访问左子树与右子树。
算法1:借助栈结构。访问当前根节点,随后先将其右子树压入栈中,再将左子树压入栈中,随后弹出栈顶元素(左孩子),重复上述操作。
代码实现如下:
//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(推广至中序遍历甚至后序遍历等):如下图所示,整个二叉树遍历可以看做是一个简化的左子树链。对于每个节点而言,先扫描当前节点,继而扫描其左孩子,当所有左子树的左孩子扫描完成后,以当前节点的右孩子当做新的左子树链,重复上述操作。
代码实现:
//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();
}
}
5.2.2 中序遍历
中序遍历,即依次访问左孩子,当前节点,右孩子。
算法:如下图所示,节点优先权会依次传递给左子树链最后一个左孩子,随后,访问其右子树,重复操作。
image.png
网友评论