以下笔记为jjyaoao本人制作，欢迎借鉴学习和提出相关建议，转载需要标明出处www.jjyaoao.space

树

应用

有根树

有序树

凡是兄弟之间有明确次序的树，我们把它叫做有序树

任何一颗树中所含的边数 = 顶点数目-1 = 其中所有定点度数之和

这个结论之所以重要，是因为我们可以得到边数和顶点个数是同阶的

也就是说，如果一棵树的总体规模，如果可以度量为顶点数+边数，那么它从渐进的意义来讲，是与顶点个数同阶的，也就是我们后面评判一棵树的规模，可以以顶点的数目n作为参照

路径+环路

这里我们用边的数目来代表它的路径长度

连通+无环

深度+层次

何时取等号？

当节点v是深度最大的叶节点或祖先节点时，取等号

树的表示

ADT接口

父节点

孩子节点

父亲+孩子

整合了父亲和孩子的优点

长子+兄弟

反观父亲+孩子出现的问题

根源在于每一个节点的出度是不尽相同的

解决方案：每一个节点均设两个引用

这种方式是对树本质的深刻理解

二叉树

有根有序树

真二叉树

如果某一棵树原先度数是0，那么我们为他引入两个节点，如果原先度数是1，那么我们为他引入一个节点。

一方面从渐进的意义上讲，阶数相当
另一方面，当我们后续实现就能看出，这种添加完全是假象的，不需要实际的添加节点进入，只是方便理解，实现。
犹如虚拟实现，想象它背后的逻辑是对的，不需要实际的实现它

描述多叉树

表面上是不可能的，竟然用一个特例，来描述整个现象

这也解释了为何树会变成一个小的标题；：因为二叉树就可以代表树

二叉树实现

BinNode类

接口实现

BinTree类

虚方法updateHeight是为了，后面庞大的衍生类能对这个方法进行适当的重写

高度更新

未涉及到变种，仍采用常规定义

节点插入

通过调用binNode类的同名接口insertAsrc() 传入参数e，意味着创建一个e的节点，并且让x指向这个接口所返回的那个地址交给x此前为空的右孩子引用，从而使得引用能指向新晋生成的节点

子树接入

template <typename T> //将S当作节点x的左子树接入二叉树，S本身置空
0002 BinNodePosi<T> BinTree<T>::attach ( BinTree<T>* &S, BinNodePosi<T> x ) { //x->lc == NULL
0003    if ( x->lc = S->_root ) x->lc->parent = x; //接入
0004    _size += S->_size; updateHeightAbove ( x ); //更新全树规模与x所有祖先的高度
0005    S->_root = NULL; S->_size = 0; release ( S ); S = NULL; return x; //释放原树，返回接入位置
0006 }
0007 
0008 template <typename T> //将S当作节点x的右子树接入二叉树，S本身置空
0009 BinNodePosi<T> BinTree<T>::attach ( BinNodePosi<T> x, BinTree<T>* &S ) { //x->rc == NULL
0010    if ( x->rc = S->_root ) x->rc->parent = x; //接入
0011    _size += S->_size; updateHeightAbove ( x ); //更新全树规模与x所有祖先的高度
0012    S->_root = NULL; S->_size = 0; release ( S ); S = NULL; return x; //释放原树，返回接入位置
0013 }

子树删除

template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
0002 int BinTree<T>::remove ( BinNodePosi<T> x ) { //assert: x为二叉树中的合法位置
0003    FromParentTo ( *x ) = NULL; //切断来自父节点的指针
0004    updateHeightAbove ( x->parent ); //更新祖先高度
0005    int n = removeAt ( x ); _size -= n; return n; //删除子树x，更新规模，返回删除节点总数
0006 }
0007 template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
0008 static int removeAt ( BinNodePosi<T> x ) { //assert: x为二叉树中的合法位置
0009    if ( !x ) return 0; //递归基：空树
0010    int n = 1 + removeAt ( x->lc ) + removeAt ( x->rc ); //递归释放左、右子树
0011    release ( x->data ); release ( x ); return n; //释放被摘除节点，并返回删除节点总数
0012 } //release()负责释放复杂结构，与算法无直接关系，具体实现详见代码包

子树分离

template <typename T> //二叉树子树分离算法：将子树x从当前树中摘除，将其封装为一棵独立子树返回
0002 BinTree<T>* BinTree<T>::secede ( BinNodePosi<T> x ) { //assert: x为二叉树中的合法位置
0003    FromParentTo ( *x ) = NULL; //切断来自父节点的指针
0004    updateHeightAbove ( x->parent ); //更新原树中所有祖先的高度
0005    BinTree<T>* S = new BinTree<T>; S->_root = x; x->parent = NULL; //新树以x为根
0006    S->_size = x->size(); _size -= S->_size; return S; //更新规模，返回分离出来的子树
0007 }

遍历

递归—-》迭代是很有必要的，递归的过程只具有渐进意义的O(n)，因为它每一步所装的箱子都是一样的大小，我们完全可以根据实际情况，来把他箱子改小，这在实际应用具有巨大的意义，虽然只是常数的提升！

先中后都属于深度搜索

VST貌似是指针函数的引用

先序遍历

visit里面则放你需要做的事情（取来干嘛）

递归

迭代

为此，我们只需引入栈

版本1

思路

实现

实例

染黑来代表这个节点接受访问

迭代版2

为了推广到后面的中序，后序算法

新思路

实现

最好熟读，并且背下来！

//从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问
0002 template <typename T, typename VST> //元素类型、操作器
0003 static void visitAlongVine ( 
    BinNodePosi<T> x, 
    VST& visit, 
    Stack<BinNodePosi<T>>& S ) 
{ //这里的visitAlongVine就是上面那张图的....leftbrach
0004    while ( x ) {
0005       visit ( x->data ); //访问当前节点
0006       S.push ( x->rc ); //右孩子入栈暂存（可优化：通过判断，避免空的右孩子入栈）
0007       x = x->lc;  //沿左分支深入一层
0008    }
0009 }
0010 
0011 template <typename T, typename VST> //元素类型、操作器
0012 void travPre_I2 ( BinNodePosi<T> x, VST& visit ) { //二叉树先序遍历算法（迭代版#2）
0013    Stack<BinNodePosi<T>> S; //辅助栈
0014    while ( true ) {
0015       visitAlongVine ( x, visit, S ); //从当前节点出发，逐批访问
0016       if ( S.empty() ) break; //直到栈空
0017       x = S.pop(); //弹出下一批的起点
0018    }
0019 }

实例

中序遍历

递归

改写迭代难度比先序要大，因为它并不是全是尾递归！！！

难点

观察

思路

实现

与先序遍历的区别——-visit –> go（vine）

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

实例

分摊分析

难道我们的结论是总体需要n²的时间吗？？？

整个算法的确呈现迭代，而且每一步的goalongleftbranch或长或短，甚至有可能有达到Ω（n）的量级

不过我们不难发现，所有左侧链的长度加起来，也只是n 因此，我们刚才所得到的n²的结果只是一个假象

而我们得到n²的结论只是将估计量括起来当成一个方框，而累计的复杂度则是方框的面积

后序遍历

递归

思路

实现

template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
0002 static void gotoLeftmostLeaf ( Stack<BinNodePosi<T>>& S ) { //沿途所遇节点依次入栈
0003    while ( BinNodePosi<T> x = S.top() ) //自顶而下，反复检查当前节点（即栈顶）
0004       if ( HasLChild ( *x ) ) { //尽可能向左
0005          if ( HasRChild ( *x ) ) S.push ( x->rc ); //若有右孩子，优先入栈
0006          S.push ( x->lc ); //然后才转至左孩子
0007       } else //实不得已
0008          S.push ( x->rc ); //才向右
0009    S.pop(); //返回之前，弹出栈顶的空节点
0010 }
0011 
0012 template <typename T, typename VST>
0013 void travPost_I ( BinNodePosi<T> x, VST& visit ) { //二叉树的后序遍历（迭代版）
0014    Stack<BinNodePosi<T>> S; //辅助栈
0015    if ( x ) S.push ( x ); //根节点入栈
0016    while ( !S.empty() ) { //x始终为当前节点
0017       if ( S.top() != x->parent ) ////若栈顶非x之父（而为右兄）
0018          gotoLeftmostLeaf ( S ); //则在其右兄子树中找到HLVFL（相当于递归深入）
0019       x = S.pop(); visit ( x->data ); //弹出栈顶（即前一节点之后继），并访问之
0020    }
0021 }

表达式树(RPN)

盯住红色部分

仔细观察，这就是一个后序遍历

也可以理解为不断求值的过程

所以说RPN是不需要括号的，与其说是不需要，不如说是背后隐藏了一棵树在里面

层次遍历

实现

可以看到层次遍历的接口形式和其他遍历完全一致

template <typename T> template <typename VST> //元素类型、操作器
0002 void BinNode<T>::travLevel ( VST& visit ) { //二叉树层次遍历算法
0003    Queue<BinNodePosi<T>> Q; //辅助队列
0004    Q.enqueue ( this ); //根节点入队
0005    while ( !Q.empty() ) { //在队列再次变空之前，反复迭代
0006       BinNodePosi<T> x = Q.dequeue(); visit ( x->data ); //取出队首节点并访问之
0007       if ( HasLChild ( *x ) ) Q.enqueue ( x->lc ); //左孩子入队
0008       if ( HasRChild ( *x ) ) Q.enqueue ( x->rc ); //右孩子入队
0009    }
0010 }