二叉树总结

1. 树形结构：属于非线性结构，其子树之间不能有交集，除了根结点外每个节点有且仅有一个父节点。一棵有N个结点的树有N-1条边

2. 结点的度：一个结点含有子树的个数。如图所示A的度为2，B的度为3.

   树的度：一棵树中所有结点度的最大值。如图树的度为3

   叶子结点：度为0的结点。如图中的D H I F G

   孩子结点：B是A的孩子结点

   树的高度：树中结点的最大层次。如图高度为4

   森林：有M棵互不相交的树的集合。

3. 可以使用“孩子兄弟表示法”来表示树：

class Node{

        int val;//树中存储的数据

        Node firstChild;//第一个孩子引用

        Node nextBrother;//下一个兄弟引用

}

4. 一棵二叉树是指结点的一个有限集合，该集合要么为null，要么由一个根结点加上两颗别称为左子树和右子树的二叉树组成。

注意：二叉树的任意结点的度都不大于2，且子树有左右之分又称为有序树

5. 两种特殊的二叉树：

满二叉树：每层的结点数都能够达到最大值，即若层数为k则其树的总结点数为2^k-1。

完全二叉树： 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点能够一一对应时称之为完全二叉树。满二叉树是特殊的完全二叉树。

6. 二叉树的性质：

(5)  对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子

 7. 二叉树的遍历：

（1）前序遍历：根->左->右   以图为例：A B D E H C F G

// 前序遍历：根->左->右
void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preOrder(root.left);
    preOrder(root.right);
}

（2）中序遍历：左->根->右    以图为例：D B E H A F C G

// 中序遍历：左->根->右
void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

（3）后序遍历：左->右->根    以图为例：D H E B F G C A

// 后序遍历：左->右->根
void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val + " ");

}

（4）层序遍历：从左到右，遍历每一层（可以借助队列） 以图为例：ABCDEFG

//层序遍历
void levelOrder(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    if(root == null) return;
    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode cur = queue.poll();
        System.out.print(cur.val + " ");
        if(cur.left != null){
            queue.offer(cur.left);
        }
        if(cur.right != null){
            queue.offer(cur.right);
        }
    }
}

（5）分层遍历：

//分层遍历
public List<List<Character>> levelOrder2(TreeNode root) {
    List<List<Character>> ret = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if(root == null) return null;
    queue.offer(root);
    while(!queue.isEmpty()){
        List<Character> row = new ArrayList<>();
        int size = queue.size();
        while(size>0){
            TreeNode cur = queue.poll();
            row.add(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
            size--;
        }
        ret.add(row);
    }
    return ret;
}

 注意：根据前序和后序不能确定一个二叉树，因为其只能确定根而不能确定左右子树。