树-森林

概念

基本概念：
- 定义：n(n>=0)个结点的有限集合。当n=0时，称为空树，当n>0时，该集合满足如下条件:
  1. 其中必有一个称为根(root)的特定结点,它没有直接前驱，但有零个或多个直接后继。
  2. 其余n-1个结点可以划分成m(m>=0)个互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一颗树，称为根root的子树。每课子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。
- 结点:包含一个数据元素及若干指向其它结点的分支信息。
- 结点的度：一个结点的子树个数。
- 叶子结点：度为0的结点，即无后继的结点，也称为终端结点。
- 分支结点: 度不为0的结点，也称为非终端结点.
- 孩子结点：一个结点的直接后继称为该结点的孩子结点。
- 双亲结点：一个结点的直接前驱称为该结点的双亲结点。
- 兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。
- 堂兄弟：双亲在同一层的结点互为堂兄弟。
- 祖先结点：一个结点的祖先结点是指从根结点该结点的路径上的所有结点。
- 子孙结点：以某结点为根的子树中的任一结点都称为该结点的子孙。
- 结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。
- 树的度：树中所有结点的度的最大值。
- 树的高度(深度)：树中所有结点的层次的最大值。
- 有序数: 在树T中，如果各子树Ti之间是有先后次序的。
- 无序树: 在树T中，如果各子树Ti之间是没有先后次序的。
- 森林:m(m>=0)课互不相交的树的集合。

树的存储结构

双亲表示法
孩子表示法
孩子兄弟表示法

树与二叉的关系

树转化为二叉树
二叉树转化树

二叉树与森林的关系

森林转化二叉树
二叉树转化森林
关系

树与深林的关系

树的遍历

先根遍历 若树非空，则遍历方法为:
- (1)访问根结点
- (2)从左到右，依次先根遍历根结点的每一颗子树。
后根遍历 若树非空，则遍历方法为:
- (1)从左到右，依次后根遍历根结点的每一棵子树。
- (2)访问根结点。
关系
- 遍历关系
  - 树的先序遍历和对应的树转化为二叉树后的先序遍历结果相同。
  - 树的后序遍历和对应的树转化为二叉树后的中序遍历的结果相同。

森林的遍历

先序遍历 若森林非空，则遍历方法为:
- (1)访问森林中第一颗树的根结点。
- (2)先序遍历第一颗树的根结点的子树森林。
- (3)先序遍历除去第一棵树之后剩余的树构成的森林。
中序遍历 若森林非空，则遍历方法如下:
- 中序遍历森林中第一棵树的根结点的子树森林。
- 访问第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。
关系
- 遍历关系
  - 森林的先序遍历就是按先序遍历树的方式
  - 森林的中序遍历就是按中序遍历树的方式