树

1.树的相关定义：

1.1树的定义：

树（tree）是包含n（n>=1）个结点，n-1条边的有穷集，其中：
（1）每个元素称为结点（node）。
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为个互不相交的集合，其中每一个集合本身也是一棵树，被称作原树的子树（subtree）。

1.2树的相关名词解释：

空集合也是树，称为空树。空树中没有结点；
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
结点的度：一个结点含有的子结点的个数称为该结点的度；
叶结点或终端结点：度为0的结点称为叶结点；
非终端结点或分支结点：度不为0的结点；
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；
树的度：一棵树中，最大的结点的度称为树的度；
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
树的高度或深度：树中结点的最大层次；
堂兄弟结点：双亲在同一层的结点互为堂兄弟；
结点的祖先：从根到该结点所经分支上的所有结点；
子孙：以某结点为根的子树中任一结点都称为该结点的子孙；
森林：由n(n>=0)棵互不相交的树的集合称为森林。

1.3树的种类：

无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树；
有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
二叉树：每个节点最多含有两个子树的树称为二叉树；
满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树；
完全二叉树：有2-1个节点的满二叉树称为完全二叉树；
哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树。

1.4树的深度：

定义一棵树的根结点层次为1，其他结点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。

2.树的遍历方法：

2.0二叉树定义代码：

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val=x;
    }
}

2.1先序遍历（先根遍历）：

中左右（根左右）
递归代码描述：

public List<Integer> PreOrder(TreeNode root,List<Integer> list){
    if(root==null)
        return null;
    list.add(root.val);
    PreOrder(root.left,list);
    PreOrder(root.right,list);
    return list;
}

2.2中序遍历（中根遍历）：

左中右（左根右）
递归代码描述：

public List<Integer> InOrder(TreeNode root,List<Integer> list){
    if(root==null)
        return null;
    InOrder(root.left,list);
    list.add(root.val);
    InOrder(root.right,list);
    return list;
}

2.3后序遍历（后根遍历）：

左右中（左右根）
递归代码描述:

public List<Integer> PostOrder(TreeNode root,List<Integer> list){
    if(root==null)
        return null;
    PostOrder(root.left,list);
    PostOrder(root.right,list);
    list.add(root.val);
    return list;
}

2.4层次遍历(广度优先搜索BFS)：

（迭代写法代码演示）

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)
        return Collections.emptyList();
        List<List<Integer>> list=new ArrayList<>();
        Deque<TreeNode> deque=new LinkedList<TreeNode>();
        deque.addLast(root);
        while(!deque.isEmpty()){
            List<Integer> list1=new ArrayList();
            int k=deque.size();
            for(int i=0;i<k;i++){
                if(deque.getFirst().left!=null)
                deque.addLast(deque.getFirst().left);
                if(deque.getFirst().right!=null)
                deque.addLast(deque.getFirst().right);
                list1.add(deque.removeFirst().val);
            }
            list.add(list1);
        }
        return list;
    }
}
/**
*注：目前queue已经被双端队列Deque所替代，相应的方法为addLast(),removeFirst()，getFirst()
*
*/

3.关于离散数学中的树:

部分定义：
(1) 无向树——连通无回路的无向图
(2) 平凡树——平凡图
(3) 森林——至少由两个连通分支（每个都是树）组成
(4) 树叶——1度顶点
(5) 分支点——度数2的顶点

定理16.1 设G=<_V_,_E_>是n阶m条边的无向图，则下面各命题
是等价的：
(1) G 是树
(2) G 中任意两个顶点之间存在惟一的路径.
(3) G 中无回路且 m=n1.
(4) G 是连通的且 m=n1.
(5) G 是连通的且 G 中任何边均为桥.
(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈（基本回路）.

定理16.2设T是n阶非平凡的无向树，则T 中至少有两片树叶.
定义16.2设G为无向图
(1) G的树——T 是G 的子图并且是树
(2) G的生成树——T 是G 的生成子图并且是树
(3) 生成树T的树枝——T 中的边
(4) 生成树T的弦——不在T 中的边
(5) 生成树T的余树 ——全体弦组成的集合的导出子图
定理16.3无向图G具有生成树当且仅当G连通.
推论1G为n阶m条边的无向连通图，则_m>=n-_1.
推论2 T的余树的边数为m-n+1
推论3 C为G中任意一个圈，则C和T的余树一定有公共边。

n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数。 N是总结点

在二叉树中：

n0=n2+1；

N=n0+n1+n2