[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}。随后，再将当前节点的左孩子指向新建的节点即可。

insertAsLC操作

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