「树（Tree）」 是 n(n>=0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中，有且仅有一个特定的称为根的结点。当 n>1 时，其余结点可分为 m (m>0) 个互不相交的有限集 T1、T2、……、Tm。其中每一个集合本身又是一棵树，并且称为根的「子树（SubTree）」
- 结点间关系
结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent） 。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点.
- 结点的层次
结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层，其双亲在同一层的结点互为堂兄弟。
- 结点n的高度: n 结点到叶子结点所有路径上包含结点个数的最大值。叶子结点的高度为 1，往上结点的高度依次递增。
- 结点n的深度: 从根结点到结点n唯一的路径的长，根结点深度为1
- 层数：根结点为第一层，往下一次递增。
- 树中结点的最大层数称之为树的深度或者高度，所以在基数为1时树的深度=树的高度=最大层数
- 结点的度：结点拥有的子树的个数，度为0的结点称之为叶子结点
- 树的度：是树内所有结点度的最大值
- 树的深度：树内所有结点深度的最大值，也就是所有叶子结点深度的最大值，也就是树的层数
- 树的高度：树内所有结点高度的最大值，也就是根结点的高度，也就是数的层数
二叉树
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点). 二叉树的子树有左子树、右子树。其次序不能颠倒。所以二叉树是一棵严格的有序树。
5种形态
二叉树的分类
二叉树的重要特性
- 一颗树深度为 h，最大层数为k，深度与最大层数相同，k=h;
- 二叉树的第 层上结点数最多为 ；
- 高度为 h 的二叉树中，最多有 个结点；
- 对任何一棵二叉树, 如果叶结点数为 , 度为2的结点数为 , 则一定满足
- 具有n个结点的完全二叉树的深度为;
- 有n个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
- 若i为结点编号则 如果i>1，则其父结点的编号为i/2
- 如果2i <= n，则其左儿子（即左子树的根结点）的编号为2i；若2i>n，则无左儿子；
- 如果2i+1<=n，则其右儿子的结点编号为2i+1；若2i+1>N，则无右儿子。
- 给定n个结点，能构成h(n)种不同的二叉树，其中h(n)为卡特兰数的第n项，h(n)=C(2*n, n)/(n+1)。
- 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
- 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
- 若 2i+1>n，则该结点无右孩子结点， 否则，编号为 2i+1 的结点为其右孩子结点。
满二叉树 完美二叉树 (perfect binary tree)
每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
一棵深度为 k 且有 个结点的二又树称为满二叉树。
完全二叉树
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
二叉树的遍历
- 前序遍历
遍历顺序为：「根结点–>左子树–>右子树」.
- 中序遍历
遍历顺序为：「左子树–>根结点–>右子树」
- 后序遍历
遍历顺序为：「左子树–>右子树–>根结点」
- 层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
2019 CSF-J 14. 假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为( )。
A. ABCDEFGHIJ B. ABDEGHJCFI
C. ABDEGJHCFI D. ABDEGHJFIC答案：B
试题分析
考察二叉树的遍历，后序遍历决定根是A，中序遍历中看A的左边DBGEH是左子树，右边CIF是右子树，依次类推可画出完整的树，再求先序遍历。