|
树的递归定义：
树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
（1）有且仅有一个特定的称为根（Root）的结点
（2）其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树。
注意：树的递归定义刻画了树的固有特性：一颗非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。
若某结点在第 L 层，则其子树的根就在第 L 1层。
树中结点的最大层次称为树的深度或高度。
树的度是所有结点度里的最大值。
| 双亲 |
上层的结点（直接前驱） |
| 孩子 |
下层结点的子树的根（直接后驱） |
| 兄弟 |
同一双亲下的同层结点 |
| 堂兄弟 |
双亲位于同一层的结点（但并非同一双亲） |
| 祖先 |
从根到该结点所经分支的所有结点 |
| 子孙 |
该结点下层子树中的任一结点 |
---------------------------------------------------------------------------------------------------------------------------------------
树具有如下最基本的性质:
  有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。
注意：若不特别指明，一般讨论的树都是有序树。
森林：森林是 m（m>=0）棵互不相交的树的集合。
树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
---------------------------------------------------------------------------------------------------------------------------------------
二叉树的定义：二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此，我们把二叉树作为重点。
二叉树是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成（子树也为二叉树）。
二叉树的特点及与树的异同：
二叉树的五种基本形态：
二叉树可以是空集；根可以有空的左子树和右子树；或者左，右子树皆为空。
二叉树的性质：
   
---------------------------------------------------------------------------------------------------------------------------------------
特殊二叉树：
左斜树：所有的结点只有左子树。
右斜树：所有的结点只有右子树。
特点：每层只有一个结点，结点的个数与二叉树的深度相同。
满二叉树：一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。
特点：
（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一 一对应时，称为完全二叉树。
完全二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上。
特点：
（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
完全二叉树的性质：
---------------------------------------------------------------------------------------------------------------------------------------
二叉树的顺序存储：该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。
---------------------------------------------------------------------------------------------------------------------------------------
二叉树的链式存储：
二叉树链式存储形象对比图
带双亲指针的二叉链表：经常要在二叉树中寻找某节点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。
---------------------------------------------------------------------------------------------------------------------------------------
我们来几道例题：
方法二：n0 = n2 1
设第 i 层为最后一层，i - 1 层为满结点.
最后一层结点数量为1，2，4，8，16，32，64，128，256，512
768 - 511 = 257 （第 i 层结点数）
257 / 2 = 129（向上取整） （第 i - 1 层度数为2或1的结点数）
256 - 129 = 127 （第 i - 1 层度数为0的结点数）
127 257 = 384
配合图像理解
---------------------------------------------------------------------------------------------------------------------------------------
二叉树遍历
遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅一次访问。
访问结点所做的操作依赖于具体的应用问题。
1.遍历方案
（1）访问结点本身（N）
（2）遍历该结点的左子树（L）
（3）遍历该结点的右子树（R）
注意：这种遍历方法的时间复杂度是：O(N)
---------------------------------------------------------------------------------------------------------------------------------------
先序递归遍历算法
如果二叉树为空，什么也不做。否则：
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
先序非递归遍历算法
（1）首先申请一个新的栈，记为stack。
（2）将头结点head压入stack中。
（3）每次从stack中弹出栈顶结点，记为cur，然后打印cur的值，如果cur右孩子不为空，则将右孩子压入栈中；如果cur的左孩子不为空，将其压入stack中。
（4）重复步骤3，直到stack为空。
---------------------------------------------------------------------------------------------------------------------------------------
中序递归遍历算法
如果二叉树为空，什么也不做。否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
---------------------------------------------------------------------------------------------------------------------------------------
后序递归遍历算法
如果二叉树为空，什么也不做。否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
---------------------------------------------------------------------------------------------------------------------------------------
层次遍历二叉树
要进行层次遍历需要借助一个队列。先将二叉树根结点入队，然后出队，访问该结点，如果它有左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空。
---------------------------------------------------------------------------------------------------------------------------------------
遍历构造二叉树
注意：前序遍历序列和中序遍历序列或者中序遍历序列和后序遍历序列可以唯一地构造一棵二叉树
例1：
前序遍历序列:ABCDEF
中序遍历序列：CBDAEF
后序遍历序列：CDBFEA
前序遍历先访问根结点，因此前序遍历序列的第一个字母肯定就是根结点，即A是根结点；然后，由于中序遍历先访问左子树，再访问根结点，最后访问右子树，所以我们找到中序遍历中A的位置，然后A左边的字母就是左子树了，也就是CBD是根结点的左子树；同样的，得到EF为根结点的右子树。将前序遍历序列分成BCD和EF，分别对左子树和右子树应用同样的方法，递归下去。
例2：
先序序列：ABCDEFGHI
中序序列：BCAEDGHFI
由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列，EDGHFI为右子树的中序序列。然后由先序序列可知B是左子树的根结点，D是右子树的根结点。依此类推，就能将剩下的结点继续分解下去，最后得到二叉树。
例3：
中序序列：HDMIBJNEAFKCG
后序序列：HMIDNJEBKFGCA
由后序遍历可知A是根结点，由中序遍历可知HDMIBJE是A的左子树部分，FKCG是右子树部分。由后序遍历可知B是A的左子树，A的右子树部分KFGC，C是根。由中序遍历可知，FK是C的左子树部分，G是右子树部分。由后序遍历可知，F是C的左子树，K是F的右子树。
---------------------------------------------------------------------------------------------------------------------------------------
二叉树线索化
遍历二叉树就是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到二叉树结点的各种遍历序列。
其实质就是对一个非线性结构进行线性化操作，使在这个访问序列中每一个结点（除第一个和最后一个）都有一个直接前驱和直接后继。
传统的二叉链表只能反映父子关系，不能直接得到遍历中的前驱和后继。
---------------------------------------------------------------------------------------------------------------------------------------
线索二叉树的概念
n个结点的二叉链表中含有n 1个空指针域。
N个结点有2n个指针，有N-1个非空指针。
利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为“线索”）。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
根据线索性质的不同，线索二叉树可分为前序线索二叉树，中序线索二叉树和后序线索二叉树三种。
---------------------------------------------------------------------------------------------------------------------------------------
线索二叉树的结点结构
---------------------------------------------------------------------------------------------------------------------------------------
线索化建立过程（中序）
记ptr指向二叉链表中的一个结点，以下是建立线索的规则：
（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱节点。这个结点称为ptr的中序前驱。
（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继节点。这个结点称为ptr的中序后继。
显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志，注意ltag和rtag只是区分0和1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。
在中序线索二叉树上查找任意结点的中序前驱结点
对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况：
（1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点。
（2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。
在中序线索二叉树上查找任意结点的中序后继结点
对于中序线索二叉树上的任一结点，寻找其中序的后继结点，有以下两种情况：
（1）如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继结点。
（2）如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，它的后继结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。
例1：
后序序列：dbca
d没有左子树和右子树，所以d的左指针域指向它的前驱结点，但是d没有前驱结点，所以指向NULL。
d的右指针域指向它的后继结点，即指向b结点。
此时pre在d处。
b没有左子树，所以b的左指针域指向它的前驱结点，即指向d。
此时pre在b处。
c没有左子树和右子树，所以c的左指针域指向它的前驱结点，即指向b结点。
c的右指针域指向它的后继结点，即指向a结点。
此时pre在c处。
a有左子树和右子树。
选D。
来源：https://www./content-4-255451.html
|
