先中后序遍历

节点

public class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private Object value;

    static {
        System.out.println("Node --> static--一个系统内只执行一次, 次序：1");
    }

    {
        //System.out.println("Node -->{}, 每实例化一次都调用，次序：2");
    }

    /**
     * 构造方法
     * @param value
     */
    public TreeNode(Object value) {
        //System.out.println("constructor, 每实例化一次都调用，次序：3");
        this.value = value;
    }

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

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

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getRight() {
        return right;
    }

    public Object getValue() {
        return value;
    }

    public String toString()
    {
        return value + ",";
    }

}

树查询

public class Tree {

    static StringBuffer preOrderStr = new StringBuffer("先序遍历结果：");
    static StringBuffer preOrderStr2 = new StringBuffer("棧先序遍历结果：");
    static StringBuffer inOrderStr = new StringBuffer("中序遍历结果：");
    static StringBuffer postOrderStr = new StringBuffer("后序遍历结果：");
    static StringBuffer levelOrderStr = new StringBuffer("层次遍历结果：");

    {
        System.out.println("{}, 每实例化一次都调用，次序：2");
    }

    /**
     * 构造方法
     */
    public Tree() {
        System.out.println("constructor, 每实例化一次都调用，次序：3");
        //this.getValue() = value;
    }

    static {
        System.out.println("static--一个系统内只执行一次, 次序：1");
    }


    /**
     * 创建树模型
     */
    public static TreeNode buildTree() {
        TreeNode root = new TreeNode(1);

        TreeNode rLeft1 = new TreeNode(2);
        rLeft1.setLeft(new TreeNode(4));
        rLeft1.setRight(new TreeNode(5));

        TreeNode rRight1 = new TreeNode(3);
        rRight1.setLeft(new TreeNode(6));
        rRight1.setRight(new TreeNode(7));

        root.setLeft(rLeft1);
        root.setRight(rRight1);
        return root;
    }

    public static TreeNode buildTree2() {
        TreeNode rootTree = new TreeNode("A");
        TreeNode tLeft1 = new TreeNode("B");
        TreeNode dTree = new TreeNode("D");
        dTree.setLeft(new TreeNode("H"));
        TreeNode kTree = new TreeNode("K");
        dTree.setRight(kTree);
        tLeft1.setLeft(dTree);
        TreeNode eTree = new TreeNode("E");
        eTree.setRight(new TreeNode("I"));
        tLeft1.setRight(eTree);
        TreeNode tRight1 = new TreeNode("C");
        tRight1.setLeft(new TreeNode("F"));
        tRight1.setRight(new TreeNode("G"));
        rootTree.setLeft(tLeft1);
        rootTree.setRight(tRight1);
        return rootTree;
    }
    /**
     * 先序排列--递归遍历
     * 根 -> 左 -> 右
     * @param t
     */
    public static void preOrderTravRecu(TreeNode t) {

        if(t == null) return;

        preOrderStr.append(t.getValue());
        preOrderTravRecu(t.getLeft());
        preOrderTravRecu(t.getRight());
    }

    /**
     * 先序排列: 用Stack来存储元素，根据后进先出原则
     * 根 -> 左 -> 右
     * @param t
     */
    public static void preOrderTrav(TreeNode t) {

        if(t == null) return;
        Stack<TreeNode> st = new Stack<TreeNode>();
        TreeNode temp;
        st.push(t);
        while (!st.empty()) {
            temp = st.pop();
            preOrderStr2.append(temp.getValue());
            if(temp.getRight() != null)
                st.push(temp.getRight());
            if(temp.getLeft() != null)
                st.push(temp.getLeft());
        }
    }

    /**
     * 中序遍历 -- 递归
     * 左 -> 根 -> 右
     * @param t
     */
    public static void inOrderTrav(TreeNode t){
        if(t == null) return;
        inOrderTrav(t.getLeft());
        inOrderStr.append(t.getValue());
        inOrderTrav(t.getRight());
    }

    /**
     * 后序遍历
     * 左 -> 右 -> 根
     * @param t
     */
    public static void PostOrderTrav(TreeNode t) {
        if(t == null) return;
        PostOrderTrav(t.getLeft());
        PostOrderTrav(t.getRight());
        postOrderStr.append(t.getValue());

    }

    /**
     * 层次遍历: 一层一层从上往下，从左到右
     * @param t
     */
    public static void levelOrderTrav(TreeNode t) {
        if(t == null) return;
        TreeNode temp;
        //Queue：队列, FIFO-> 先进先出原则
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(t); //添加元素到尾部
        while (q.peek() != null) {//获取头部元素但不称除
            temp = q.poll(); //从头部取出元素
            levelOrderStr.append(temp.getValue());
            if(temp.getLeft() != null)
                q.offer(temp.getLeft());
            if(temp.getRight() != null)
                q.offer(temp.getRight());
        }

    }

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        TreeNode t = buildTree();
        preOrderTravRecu(t);
        System.out.println(preOrderStr);

        preOrderTrav(t);
        System.out.println(preOrderStr2);

        inOrderTrav(t);
        System.out.println(inOrderStr);

        PostOrderTrav(t);
        System.out.println(postOrderStr);
        levelOrderTrav(t);
        System.out.println(levelOrderStr);
    }

}

java集合类——Stack栈类与Queue队列 参考： https://www.cnblogs.com/interdrp/p/8039490.html

先中后序遍历

原文：https://www.cnblogs.com/unclelearning/p/14024099.html