二叉树分析

二叉树分类

• 满二叉树： 除最后一层无任何子外，每一层上的所有结点都有两个子结点二叉树。

• 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

• 平衡二叉树：称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

对于完全二叉树，若某个节点数为i，左子节点位2i+1，右子节点为2i+2。

二叉树实现

通过以下代码实现一个二叉树的基本结构

public class BinaryNode {
    public BinaryNode(Object data) {
        //节点数据
        this.data = data;
        //左孩子
        this.left = null;
        //右孩子
        this.right = null;
    }
}

构造完全二叉树

完全二叉树.png

    public void creatNode() {
        BinaryNode a1 = new BinaryNode("1");
        BinaryNode a2 = new BinaryNode("2");
        BinaryNode a3 = new BinaryNode("3");
        BinaryNode a4 = new BinaryNode("4");
        BinaryNode a5 = new BinaryNode("5");
        BinaryNode a6 = new BinaryNode("6");
        this.left = a1;
        this.right = a2;
        a1.left = a3;
        a1.right = a4;
        a2.left = a5;
        a2.right = a6;
    }

二叉树遍历

节点遍历

• 前序遍历 访问根节点，前序遍历左子书，前序遍历又子树

    public static void preOrder(BinaryNode root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
0,1,3,4,2,5,6

• 中序遍历 中序遍历左子树，访问根节点，中序遍历右子书

    public static void midOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        midOrder(root.left);
        System.out.println(root.data);
        midOrder(root.right);
    }
3,1,4,0,5,2,6

• 后序遍历 后续遍历左子树，后续遍历又子树，访问根节点

    public static void postOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.data);
    }
3,4,1,5,6,2,0

• 前序遍历（压栈法）

    /**
     * 前序遍历
     */
    public static void preorderTraversal(BinaryNode root) {
        //节点为空直接返回
        if (root == null) {
            return;
        }
        //创建栈
        Stack<BinaryNode> stack = new Stack<BinaryNode>();
        //将根节点放入栈中
        stack.push(root);
        //当栈不为空时循环
        while (!stack.isEmpty()) {
            //出栈
            BinaryNode binaryNode = stack.pop();
            //打印出栈的data
            System.out.println(binaryNode.data);
            //先压入右节点，先进后出
            if (binaryNode.right != null) {
                stack.push(binaryNode.right);
            }
            //再压入左节点
            if (binaryNode.left != null) {
                stack.push(binaryNode.left);
            }
        }
    }

层次遍历

二叉树的层次遍历可以分为深度优先遍历跟广度优先遍历

• 深度优先遍历：实际上就是上面的前序、中序和后序遍历，也就是尽可能去遍历二叉树的深度。
• 广度优先遍历：实际上就是一层一层的遍历，按照层次输出二叉树的各个节点。
  广度优先遍历
  所谓广度优先遍历就是一层一层的遍历，所以只需要按照每层的左右顺序拿到二叉树的节点，再依次输出就OK了

    public static void levelOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        LinkedList<BinaryNode> queue = new LinkedList<>();
        //把根节点放进linked中
        queue.push(root);
        while (!queue.isEmpty()) {
            // 打印linkedList的第一次元素，并移除
            BinaryNode binaryNode = queue.removeFirst();
            System.out.print(binaryNode.data + " ");
            // 依次添加每个节点的左节点
            if (binaryNode.left != null) {
                queue.add(binaryNode.left);
            }
            // 依次添加每个节点的右节点
            if (binaryNode.right != null) {
                queue.add(binaryNode.right);
            }
        }
    }