1. 树

树中的元素之间并不存在天然的直接后继或直接前驱。不过，只要附加某种约束（如遍历），也可以在树中的元素之间确定某种线性次序，因此树属于半线性结构（semi-linear structure）。

从图论的角度，树等价于连通无环图。树也由一组顶点(vertex) 以及连接于期间的若干条边(edge）组成。故任一节点与根节点之间存在着唯一路径。

从程序实现的角度，更多的将顶点称为节点（node）。

树
由上图：

深度(depth)：沿每个节点v到 根节点 的唯一通路所经过边的数目，称为 v的深度。【约定，根节点的深度为0，depth(r) = 0 故属于第0层】
祖先、后代：任一节点v在通往根节点沿途所经过的每个节点都是其祖先(ancestor），v是他们的后代(descendant）。【v的祖先/后代 包括其自身。v本身以外的祖先/后代称为 **真祖先(proper ancestor)/真后代(proper descendant)**】
- 父亲、孩子：特别的，如果节点u是节点v的祖先，且恰好比v高出一层，则称u是v的父亲(parent），v是u的孩子(child）。
子树(subtree)：v所有的后代及其之间的连边称作子树，记作subtree(v)。
高度（height）：数T中所有节点深度的最大值称为该树的高度，记作 height(T)。【本书约定，仅含单个节点的树的高度为0，空树的高度为 -1】

其他术语：

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
深度：对于任意节点n, n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n, n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；
2. 二叉树
2.1 二叉树的定义
二叉树( Bina叩 Tree) 是 n(n≥0) 个节点的有限几何，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2.2 二叉树的特点

每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点.注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
左子树和右子树是有顺序的，次序不能任意颠倒。这种二叉树称为：【有序二叉树】
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

2.3 特殊的二叉树

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

完全二叉树

对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i (l≤i≤n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如图 6-5-6 所示。

真二叉树

每个节点的（出）度都是偶数。

因为二叉树，所以节点的度只有三种可能：0、1、2；所以，偶数情况为：0或2。

2.4 二叉树的性质

1、在二叉树的第 i 层上至多有2``i``-1 个结点 (i≥1)。

2、深度为 k 的二叉树至多有**2**``****``**-1**个结点 (k≥1)。

3、对任何一棵二叉树 T，如果其终端结点数为n，度为 2 的结点数为n，则 n = n +1。

4、具有n个结点的完全二叉树的深度为（表示不大于x的最大整数)。

5、若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点；
当i>1时，该节点的双亲节点的编号为i/2；
若2i＞n，则节点i无左孩子（节点i为叶子节点）；否则其左孩子是2i；
若2i+1 >n，则节点i无右孩子；否则其右孩子是节点2i+1；

3. 二叉树的遍历

注意，在教材中约定： 1. 根节点的深度为 0； 1. 只含一个节点的数的高度为0； 1. 空树的高度为-1。

树是一种半线性结构，如何将其转变为线性结构。

方法就是：按照某种约定的次序，对节点各访问一次（且仅访问一次）。二叉树的这种访问也称作遍历(traversal)。

按照惯例：“左孩子”优先于“右孩子”。故将节点及其左、右孩子分别记为：V、L、R。
对应的遍历顺序有：

先序遍历（VLR）
中序遍历（LVR）
后序遍历（LRV）

3.1 先序遍历

3.1.1 递归版

先序遍历

template<typename T, typename VST> //元素类型、操作器
void travPre_R(BinNodePosi<T> x, VST& visit) //二叉树先序遍历（迭代版）
{
    if (!x) return; //递归基（当到达叶子节点时，递归结束）
    visit(x->data_);
    travPre_R(x->lc_, visit); //递归遍历左子树
    travPre_R(x->rc_, visit); //递归遍历右子树
}

3.1.2 迭代版

3.1.2.1 版本1

观察上面的递归版，可以发现：其中针对右子树的递归基属于尾递归（尾递归的概念），左子树则接近于尾递归。故可参照消除尾递归的一般方法，将其写成迭代版本：

template <typename T, typename VST> //元素类型、操作器
void travPre_I1 ( BinNodePosi<T> x, VST& visit ) { //二叉树先序遍历算法（迭代版#1）
   Stack<BinNodePosi(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 );
   }
}

注意，由于栈的“先进后出”的特性，左右孩子入栈时，应为：先右后左

3.1.2.1 版本2

该版本的先序遍历序列可分为两段：

沿最左侧通路自顶而下访问的各节点；
自底而上访问遍历的对应右子树；

最左侧通路（leftmost path）：在二叉树T中，从根节点出发沿着左分支一直下行的那条通路（以粗线示意），称作最左侧通路。最左侧通路

借助栈逆序记录最左侧通路上的节点的右子树，以确定对应右子树自底而上的遍历次序。

//自顶向下访问最左侧通路沿途的各个节点。
//使用辅助栈 逆序记录最左侧通路上的节点，以便确定其对应右子树自底而上的遍历次序
template<typename T, typename VST>
static void visitAlongLeftBranch(BinNodePosi<T> x, VST& visit, std::stack<BinNodePosi<T>> S)
{
    while (x)
    {
        visit(x->data_); //访问当前节点
        if (!x->rc_)    S.push(x->rc_); //右孩子入栈暂存
        x = x->lc_; //沿做分支深入一层
    }
}
//从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问
template<typename T, typename VST>
void travPre_I2(BinNodePosi<T> x, VST& visit)
{
    std::stack<BinNodePosi<T>> S;
    while (true)
    {
        visitAlongLeftBranch(x, visit, S); //从当前节点出发，逐批访问
        if(S.empty())    break; //栈空则停止
        x = S.pop(); //弹出下一批的起点
    }
}

3.2 中序遍历

3.2.1 递归版

中序遍历

template <typename T, typename VST> //元素类型、操作器
void travIn_R ( BinNodePosi<T> x, VST& visit ) { //二叉树中序遍历算法（递归版）
   if ( !x ) return;
   travIn_R ( x->lc, visit );
   visit ( x->data );
   travIn_R ( x->rc, visit );
}

3.2.2 迭代版

3.2.2.1 版本1

与之前的先序遍历算法不同，沿最左侧分支下行时只是将对应的节点压栈，并没有执行访问操作。

template <typename T> //从当前节点出发，沿左分支不断深入，直至没有左分支的节点
static void goAlongLeftBranch ( BinNodePosi(T) x, Stack<BinNodePosi(T)>& S ) {
   while ( x ) { S.push ( x ); x = x->lc; } //当前节点入栈后随即向左侧分支深入，迭代直到无左孩子
}
template <typename T, typename VST> //元素类型、操作器
void travIn_I1 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法（迭代版#1）
   Stack<BinNodePosi(T)> S; //辅助栈
   while ( true ) {
      goAlongLeftBranch ( x, S ); //从当前节点出发，逐批入栈
      if ( S.empty() ) break; //直至所有节点处理完毕
      x = S.pop(); visit ( x->data ); //弹出栈顶节点并访问之
      x = x->rc; //转向右子树
   }
}

3.2.2.1 版本2

将上一版等价地描述以下版本：

template<typename T, typename VST>
void travIn_I2(BinNodePosi<T> x, VST& visit)
{
    std::stack<BinNodePosi<T>> S;
    while (true)
    {
        if (x)
        {
            S.push(x); //根节点入栈
            x = x->lc_; //深入遍历左子树
        }
        else if (!S.empty())
        {
            x = S.pop(); visit(x); //尚未访问的最低祖先节点退栈；访问该节点
            x = x->rc_; //遍历祖先的右子树
        }
        else
            break;  //栈空，表示遍历完成
    }
}

3.2.2.1 版本3

以上版需借助辅助栈，所需辅助空间正比于二叉树的高度，在最坏情况下与节点数目相当。借助BinNode对象内部的parent_指针，以下版本仅需要常数辅助空间，属于就地算法。

该版本无需使用任何结构，总体仅需 chapter5 树 - 图8 的辅助空间。当然因为要反复调用succ()函数，时间效率有所倒退。

succ()：直接后继（中序遍历中）
与所有遍历一样，中序遍历实质功能也可以理解为：为所有节点赋予一个次序，从而将半线性的二叉树转化为线性结构。
一旦指定了遍历策略，即可像向量、列表一样，在二叉树的节点之间定义前驱、后继关系。其中没有前驱（后继）的节点称作：首、末节点。

template<class T>
BinNodePosi<T> BinNode<T>::succ() //中序遍历中的节点的直接后继
{
    BinNodePosi<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;
}

这里的直接后继分两种大类讨论：

当前节点有右孩子，则其直接后继必然在其右子树中。

此时只需转入右子树，再沿该字数的最左侧通路朝左下方深入，直到抵达子树中最靠左（最小）的节点。【如下图中的：节点b的直接后继为c】

当前节点无右孩子，则它的直接后继应该是其某一个祖先，且是将该节点纳入其左子树的最低祖先。

于是首先沿右侧通路朝左上方升，当不能继续前进时，再朝右上方移动一步即可。【如下图中的：节点e的直接后继为f】
该情况的一种特例是，出口时s可能为NULL。这意味着此前沿着右侧通路向上的回溯，抵达了树根。也就是说，当前节点是全书的末节点——它也是中序遍历的终点，没有后继。

中序遍历版本3：

template<typename T, typename VST>
void travIn_I3(BinNodePosi<T> x, VST& visit) //无需辅助栈
{
    bool backtrack = false; //将原辅助栈 替换为 标志位backtrack：标志前一步是否刚从 左子树 回溯
    while (true)
    {
        if (backtrack == false && HasLChild(*x)) //如果有左子树 且 刚刚没有回溯
        {
            x = x->lc_; //深入遍历左子树
        }
        else //否则——无左子树 或者 刚刚 回溯
        {
            visit(x->data_); //访问该节点
            if (HasRChild(*x)) //如果该节点有右子树，
            {
                x = x->rc_; //则 深入右子树遍历
                backtrack = false; //并 关闭回溯标志
            }
            else //如果没有右子树，则
            {
                x = x->succ(); //回溯
                if (!x) break; //如果其直接后继为空，表示其为 末节点（也就是说此时已经遍历完成）
                backtrack = true; //并设置回溯标志
            }
        }
    }
}

此版相当于将原辅助栈替换为一个标志位backtrack，标志是否有从下而上的回溯。若不是，则按照中序遍历的策略优先遍历左子树，否则，则意味着当前左子树已访问完毕，访问当前节点后深入右子树。

3.3 后序遍历

3.3.1 递归版

后序遍历

template <typename T, typename VST> //元素类型、操作器
void travPost_R ( BinNodePosi<T> x, VST& visit ) { //二叉树后序遍历算法（递归版）
   if ( !x ) return;
   travPost_R ( x->lc, visit );
   travPost_R ( x->rc, visit );
   visit ( x->data );
}

3.3.2 迭代版

如下图所示，将树T画在二维平面上，并假设所有节点和边均不透明。于是从左侧水平向右看去，违背遮挡的最高叶节点v——称作是 最高左侧可见叶节点（HLVFL）—— 也就是 后序遍历最先访问的节点。

注意，该HLVFL 既可能是左孩子、也可能是右孩子，所以，图种以垂直边示意它与父节点之间的联动。

考察联接于v 与根节点之间的唯一通路（以粗线示意）。与先序、中序遍历类似，自底而上的沿着该通路，整个后续遍历序列也可分解为若干个片段。每一段，分别起始于通路上的一个节点，并包括三步：

访问当前节点；
遍历以其右兄弟（若存在）为根的子树；
以及向上回溯至其父节点（若存在）并转入下一片段。 ```cpp template
//在以S栈顶节点为根的子树中，找到最高左侧可见叶节点 static void gotoHLVFL ( Stack
& S ) { //沿途所遇节点依次入栈 while ( BinNodePosi(T) x = S.top() ) //自顶而下，反复检查当前节点（即栈顶）
```
if ( HasLChild ( *x ) ) { //尽可能向左
   if ( HasRChild ( *x ) ) S.push ( x->rc ); //1.首先：若有右孩子，优先入栈
   S.push ( x->lc ); //然后才转至左孩子
} else //如果没有左孩子，
   S.push ( x->rc ); //2. 然后，才向右
```
S.pop(); //返回之前，弹出栈顶的空节点 }

template void travPost_I ( BinNodePosi(T) x, VST& visit ) { //二叉树的后序遍历（迭代版） Stack S; //辅助栈 if ( x ) S.push ( x ); //根节点入栈 while ( !S.empty() ) //当栈不空时 { if ( S.top() != x->parent ) //若栈顶非当前节点之父（那必然是其右兄弟（或者是它自己，如根节点的时候）），则 gotoHLVFL ( S ); //在以其右兄为根之子树中，找到HLVFL（相当于递归深入其中）

  //当栈顶元素是当前节点的父节点 或者 找到HLVFL之后
  x = S.pop(); visit ( x->data ); //弹出栈顶（即前一节点之后继），并访问之

} }

该算法，在每一棵（子）树的根节点，该算法都首先定位对应的HLVFL节点。同时在此过程中，依然利用辅助栈逆序的保存沿途所经各节点，已确定遍历序列各个片段在宏观上的拼接次序。

在后续遍历序列中，栈顶元素应后于栈顶子树访问，所以后序遍历序列并不是访问栈顶元素，而是先判断对应子树是否遍历，若遍历再访问栈顶元素。

在迭代版后序遍历算法运行中，树中每一层至多有两个节点存在栈中，故栈结构最大规模不超过二叉树深度的两倍，最坏情况下为O(n)。

<a name="4Mjxv"></a>
## 3.4 层次遍历
在** 广度优先遍历 **或 **层次遍历（level-order travseral）**中，节点访问次序可概括为：**“先上后下，先左后右”**—— 先访问根节点，在依次是左孩子、右孩子；左孩子的左孩子、左孩子的右孩子；右孩子的左孩子、右孩子的右孩子；...... 以此类推。

之前的 前、中、后序遍历，其迭代版本大多都是用了辅助栈。而**层次遍历的迭代版本使用的是 队列结构**。
```cpp
//层次遍历：迭代版
template<typename T, typename VST> //元素类型、操作器
void travLevel(BinNodePosi<T> x, VST& visit)
{
    std::queue<BinNodePosi<T>> Q; //辅助队列
    Q.push(x); //根节点入队

    while (!Q.empty()) //队列不空时
    {
        x = Q.pop();  //取出队首节点
        visit(x->data_); //并访问

        if(HasLChild(*x)) //如果有左孩子，则左孩子入队
            Q.push(x->lc_);
        if(HasRChild(*x)) //如果有右孩子，则左孩子入队
            Q.push(x->rc_);    
    }
}

初始化时先令树根入队，随后进入循环。每一步迭代中，首先取出并访问队首节点，然后其左孩子、右孩子（若存在）将顺序入队。一旦在试图进入下一迭代前发现队列为空，遍历即完成。

下图以左侧二叉树为例，给出了层次遍历辅助队列从初始化到再次变空的演变过程：

4. 二叉树的重构

可参考：https://zhuanlan.zhihu.com/p/83286120

如果已知某棵树的遍历序列，能否可以准确地还原出这棵树的拓扑结构。——重构

在什么情况下，可以重构成功？以下就是一些可以重构成功的结构：

4.1 【先序 | 后序】+中序

使用数学归纳法：假设对于： chapter5 树 - 图13 ，【先序+中序】可以重构出原二叉树。
则，当 chapter5 树 - 图14 时：

假设该树为此图所示
它的：

先序遍历

首先是访问根节点；然后访问左子树；最后访问右子树；

先序遍历

中序遍历

首先访问左子树；然后访问根节点；最后访问右子树；

中序遍历

后序遍历

首先访问左子树；然后访问右子树；最后访问根节点；

后序遍历

4.1.1 【先序+中序】

由上面所述可知，其大致思路为：

第一步：

前序遍历的第一个节点，即为根节点。

第二步：

由根节点，可以在中序遍历中，找到左子树对应的长度。

第三步：

根据左子树的长度，
可以在先序序列和中序序列中，找到左子树和右子树对应的先序序列和中序序列。

这样将整棵树的重构问题，分化为子树的重构问题，对于子树的重构与整棵树重构的步骤相同。子树的规模必定＜N，所以，归纳假设成立。

//1.先序+中序
template<typename T>
BinNode<T> buildBinTree1(vector<T> preOrder, vector<T> inOrder)
{
    return buildBinTree1(preOrder, 0, preOrder.size() - 1, inOrder, 0, inOrder.size());
}



template<typename T>
BinNode<T> buildBinTree1(vector<T> preOrder, int startPre, int endPre,
                        vector<T> inOrder, int startIn, int endIn)
{
    if (startPre > endPre) //如果先序遍历序列中的  开始序号>结束序号
        return NULL; //则返回NULL

    BinNode<T> root = new BinTree<T>(preOrder[startPre]); //创建根节点（先序序列中的第一个元素的值即是根节点的值）

    //在中序序列中找到根节点的位置
    for (int i = startIn; i < endIn; ++i)
    {
        if(inOrder[i] == preOrder[startPre]) //中序序列中等于先序序列首元素的值就是根节点的值
            break;
    }

    //接下来就是在每一个左子树、右子树中找到该子树的根节点
    root.lc_ = buildBinTree(preOrder, startPre + 1, startPre + (i - startIn), inOrder, startIn, i - 1); //递归遍历左子树，找到子树的根节点
    root.rc_ = buildBinTree(preOrder, (startPre + (i - startIn) + 1), endPre, inOrder, i + 1, endIn);   //递归遍历右子树，找到子树的根节点
    return root; //最后返回整个二叉树的根节点（知道根节点，根据BinNode类的父亲、左右孩子，就能推出整棵树）
}

4.1.2 【后序+中序】

大致思路：

由后序遍历，来确定根节点的值。
然后，从中序遍历中，找到左右子树的长度及对应的序列，
递归构造即可。 ```cpp template BinNode buildBinTree2(vector postOrder, vector inOrder) { if (postOrder.size() == 0 || inOrder.size() == 0) return NULL;

}

template BinNode buildBinTree2(vector postOrder, int startPost, int endPost, vector inOrder, int startIn, int endIn) { if (startPost > endPost || startIn > endIn) return NULL;

BinNode<T> root = new BinNode<T>(postOrder[endPost]); //后序序列中的末尾元素就是原二叉树的根节点的元素值

for (int i = startIn; i < endIn; ++i)
{//在中序序列中找到根节点的位置
    if(postOrder[endPost] == inOrder[i])
        break;
}
//接下来，从中序序列中找到左右子树长度及其序列，进行递归构造
root.lc_ = buildBinTree2(postOrder, startPost, startPost+(i-startIn)-1, inOrder, startIn, i - 1); //递归遍历左子树，找到子树的根节点
root.rc_ = buildBinTree2(postOrder, ((startPost + (i - startIn) -1)+ 1), endPost, inOrder, i + 1, endIn); //递归遍历右子树，找到子树的根节点
return root;

} ```

4.1.3 【先序+后序】：不能保证

【先序+后序】序列它们不能保证可以重构出原二叉树的拓扑结构。

因为：树的左子树或者右子树可能为空。

右子树为空时：
- 先序序列：

后序序列：

左子树为空时：
- 先序序列：

后序序列：

所以，由上面的左子树或右子树为空的情况来看：

这就引起了歧义。因为我们无法根据【先序+后序】来区分除去根节点之后剩下部分究竟是左子树、还是右子树。

4.1.3.1 特殊情况“真二叉树”

特殊情况该二叉树是“真二叉树”时：【先序+后序】时可以重构出该二叉树的。

由于是真二叉树，所以节点的度为：0 或 2

节点为0时，比较简单，就只有一个根节点。就能立刻重构出该二叉树。
节点为2时：

度为2的真二叉树
它的先序序列与后序序列如下所示：

先序序列、后序序列
如此看来：

可通过先序序列找出左子树的树根（l）；

可通过后序序列找出右子树的树根（r）；

然后在后序序列中找出树根（l）的位置，即可得到左子树的规模；

然后在先序序序列中找出树根（r）的位置，即可得到右子树的规模；

通过递归便可重构出二叉树。

chapter5 树