文中圖片來自 http://www.itdecent.cn/p/bf73c8d50dc2

基本概念

滿二叉樹

定義太復(fù)雜，簡單解釋：所有的非葉子節(jié)點(diǎn)都是2個(gè)子節(jié)點(diǎn)，如下圖中的ABC三個(gè)節(jié)點(diǎn)。

圖1 滿二叉樹

完全二叉樹

記憶方法：滿二叉樹或者滿二叉樹減去最后N（N>=0）個(gè)節(jié)點(diǎn)即是完全二叉樹（圖1圖2和圖3都是完全二叉樹）

圖2 完全二叉樹

遍歷方式

前序遍歷 中序遍歷 后序遍歷 層序遍歷

前序中序后序針對(duì)的都是跟節(jié)點(diǎn)來說，前代表根節(jié)點(diǎn)是第一個(gè)訪問的，然后左子節(jié)點(diǎn)，右子節(jié)點(diǎn)；中代表根節(jié)點(diǎn)是第二個(gè)訪問的，那就是先左后跟最后右，后代表根節(jié)點(diǎn)是第三個(gè)訪問的, 先左節(jié)點(diǎn) 后右 最后跟

針對(duì)圖2
前序遍歷
根節(jié)點(diǎn)第一個(gè) 所以是A，然后左節(jié)點(diǎn)樹（BDE）右節(jié)點(diǎn)樹（CF），左節(jié)點(diǎn)樹上 又是根節(jié)點(diǎn)是第一個(gè) 所以是B ，然后B的左節(jié)點(diǎn)樹只有D 那就是D，接著右子樹， 這時(shí)候順序是A->B->D->E,A的左子樹結(jié)束了，再看右子樹（CF），C是根節(jié)點(diǎn) 所以先C后F 連在一起 A->B->D->E-C-F

中序遍歷
D->B->E->A->F->C
解釋：中序遍歷 先左節(jié)點(diǎn) 接著跟節(jié)點(diǎn) 最后右節(jié)點(diǎn) 那就是先（BDE這棵樹） 再A 再（CF） ，針對(duì)(BDE) 來說 先D后B再E ，連在一起D->B-E-A-F-C
后序遍歷
D->E->B->F->C->A

再來一個(gè)復(fù)雜的練習(xí)一下

圖3 完全二叉樹

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

層序遍歷
層序遍歷比較簡單了 就是一層一層的訪問如圖中數(shù)字所示。

代碼測試一下 （先看TreeNode 類 創(chuàng)建一個(gè)節(jié)點(diǎn)類，然后用createNote方法構(gòu)造了一棵圖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;
        }
    }
}