完全二叉树及遍历方式

文中图片来自 https://www.jianshu.com/p/bf73c8d50dc2

基本概念

满二叉树

定义太复杂，简单解释：所有的非叶子节点都是2个子节点，如下图中的ABC三个节点。

图1 满二叉树

完全二叉树

记忆方法：满二叉树或者满二叉树减去最后N（N>=0）个节点即是完全二叉树（图1图2和图3都是完全二叉树）

图2 完全二叉树

遍历方式

前序遍历中序遍历后序遍历层序遍历

前序中序后序针对的都是跟节点来说，前代表根节点是第一个访问的，然后左子节点，右子节点；中代表根节点是第二个访问的，那就是先左后跟最后右，后代表根节点是第三个访问的, 先左节点后右最后跟

针对图2
前序遍历
根节点第一个所以是A，然后左节点树（BDE）右节点树（CF），左节点树上又是根节点是第一个所以是B ，然后B的左节点树只有D 那就是D，接着右子树，这时候顺序是A->B->D->E,A的左子树结束了，再看右子树（CF），C是根节点所以先C后F 连在一起 A->B->D->E-C-F

中序遍历
D->B->E->A->F->C
解释：中序遍历先左节点接着跟节点最后右节点那就是先（BDE这棵树）再A 再（CF），针对(BDE) 来说先D后B再E ，连在一起D->B-E-A-F-C
后序遍历
D->E->B->F->C->A

再来一个复杂的练习一下

图3 完全二叉树

前序：ABDHIEJCFG
中序：HDIBJEAFCG
后序：HIDJEBFGCA

层序遍历
层序遍历比较简单了就是一层一层的访问如图中数字所示。

代码测试一下（先看TreeNode 类创建一个节点类，然后用createNote方法构造了一棵图2的树，frontList是遍历的算法）

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class TreeLearn {

    public static void main(String[] args) {
        List<Character> characterList = new LinkedList<>();
        /**----------前序遍历-----------**/
        System.out.println("/**----------前序遍历-----------**/");
        frontList(createNote(), characterList);
        characterList.forEach(c -> {
            System.out.print(c+" ");
        });
        System.out.println();
        System.out.println("/**----------中序遍历-----------**/");
        /**----------中序遍历-----------**/
        characterList = new LinkedList<>();
        midList(createNote(), characterList);
        characterList.forEach(c -> {
            System.out.print(c+" ");
        });
        System.out.println();
        System.out.println("/**----------后序遍历-----------**/");
        /**----------后序遍历-----------**/
        characterList = new LinkedList<>();
        backList(createNote(), characterList);
        characterList.forEach(c -> {
            System.out.print(c+" ");
        });
    }

    /**
     * 前序遍历
     *
     * @param treeNode
     * @return
     */
    public static void frontList(TreeNode treeNode, List<Character> characterList) {
        if (Objects.nonNull(treeNode)) {
            characterList.add(treeNode.getC());
            frontList(treeNode.getLeft(), characterList);
            frontList(treeNode.getRight(), characterList);
        }
    }

    /**
     * 中序遍历
     *
     * @param treeNode
     * @return
     */
    public static void midList(TreeNode treeNode, List<Character> characterList) {
        if (Objects.nonNull(treeNode)) {
            midList(treeNode.getLeft(), characterList);
            characterList.add(treeNode.getC());
            midList(treeNode.getRight(), characterList);
        }
    }

    /**
     * 后序遍历
     *
     * @param treeNode
     * @return
     */
    public static void backList(TreeNode treeNode, List<Character> characterList) {
        if (Objects.nonNull(treeNode)) {
            backList(treeNode.getLeft(), characterList);
            backList(treeNode.getRight(), characterList);
            characterList.add(treeNode.getC());
        }
    }

    public static TreeNode createNote() {
        TreeNode f = new TreeNode('f', null, null);
        TreeNode c = new TreeNode('c', f, null);
        TreeNode e = new TreeNode('e', null, null);
        TreeNode d = new TreeNode('d', null, null);
        TreeNode b = new TreeNode('b', d, e);
        TreeNode a = new TreeNode('a', b, c);
        return a;
    }

    static class TreeNode {
        private char c;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char c, TreeNode left, TreeNode right) {
            this.c = c;
            this.left = left;
            this.right = right;
        }

        public char getC() {
            return c;
        }

        public void setC(char c) {
            this.c = c;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}