树

树形结构的相关术语

• 结点：树里面的元素
• 父子关系：结点之间相连的边
• 子树：当结点大于1时，其余结点分为的互不相交的集合
• 度：一个结点拥有的子树数量称为结点的度
• 叶子：度为0的结点
• 孩子：结点的子树
• 双亲：子树的根节点
• 兄弟：同一个双亲结点
• 森林：由N个互不相交的树构成深林
• 结点的高度：结点到叶子结点的最长路径
• 结点的深度：根结点到该结点的边的个数
• 结点的层度：结点的深度+1
• 树的高度：根节点的高度

图

满二叉树：除叶子结点外，其他的结点都有两个子结点
完全二叉树：除去最后一层外，其余层为满二叉树状态，并且最后一层的叶子结点都往左排列
完全二叉树是满二叉树的一个子集

实现方式

• 数组：推导公式，当前结点：i 两个子结点：i*2 i*2+1 ,适用于满二叉树和完全二叉树
• 链表：left right

树的遍历

• 前序遍历 根（输出） 左 右
• 中序遍历 左 根（输出） 右
• 后序遍历 左 右 根（输出）

根（输出）：表示遇到根节点则输出

代码实现

public class MyTree<E> {

    public void print(TreeNode<E> treeNode) {
        System.out.print(treeNode.getData());
    }

    //前序遍历 根 左 右
    public void pre(TreeNode<E> treeNode) {
        print(treeNode);
        if (treeNode.getLeftNode() != null)
            pre(treeNode.getLeftNode());
        if (treeNode.getRightNode() != null)
            pre(treeNode.getRightNode());
    }

    //中序遍历 左 根 右
    public void mid(TreeNode<E> treeNode) {
        if (treeNode.getLeftNode() != null) {
            mid(treeNode.getLeftNode());
        }
        print(treeNode);
        if (treeNode.getRightNode() != null)
            mid(treeNode.getRightNode());
    }

    //后序遍历 左 右 根
    public void post(TreeNode<E> treeNode) {
        if (treeNode.getLeftNode() != null) {
            post(treeNode.getLeftNode());
        }
        if (treeNode.getRightNode() != null) {
            post(treeNode.getRightNode());
        }
        print(treeNode);
    }

    //层序遍历
    public void level(TreeNode<E> treeNode) {
        MyQueue<TreeNode<E>> queue = new MyQueue<>(20);
        levelRecursion(queue, treeNode);
    }

    private void levelRecursion(MyQueue<TreeNode<E>> queue, TreeNode<E> treeNode) {
        print(treeNode);
        if (treeNode.getLeftNode() != null) {
            queue.push(treeNode.getLeftNode());
        }
        if (treeNode.getRightNode() != null) {
            queue.push(treeNode.getRightNode());
        }
        while (!queue.isEmpty()) {
            levelRecursion(queue, queue.pop());
        }
    }
}