复习二叉树 层序遍历,前序遍历,中序遍历,后序遍历 java版本

最近偶尔看看算法方面的东西，最基础的就是二叉树，因此自己心血来潮先构建一颗二叉树，然后按各种方式进行遍历。构造的二叉树样子如下:

public class MyNode {

   private String data;
   private MyNode left;
   private MyNode right;

   public MyNode() {

   }

   public MyNode(String data) {
       this.data = data;
   }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public MyNode getLeft() {
        return left;
    }

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

    public MyNode getRight() {
        return right;
    }

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

    public static void main(String[] args) {
        MyNode rootNode = new MyNode("A");
        buildTree(rootNode);
        // 按层处理
        System.out.println("层序遍历");
        processNodeLayer(rootNode);
        System.out.println("\n");
        // 前序遍历
        System.out.println("前序遍历");
        preTraversal(rootNode);
        System.out.println("\n");

        System.out.println("中序遍历");
        middleTraversal(rootNode);
        System.out.println("\n");
    }

    /**
     *         A
     *       /   \
     *     B      C
     *    / \    / \
     *   D   E  X   Y
     *      / \
     *     F   G
     * 构造一个上面图形的树.
     *
     * @param node
     */
    public static void buildTree(MyNode node) {

        MyNode b = new MyNode("B");
        MyNode c = new MyNode("C");
        addChild(node, b, c);

        MyNode c1 = new MyNode("X");
        MyNode c2 = new MyNode("Y");
        addChild(c, c1, c2);

        MyNode d = new MyNode("D");
        MyNode e = new MyNode("E");
        addChild(b, d, e);

        MyNode f = new MyNode("F");
        MyNode g = new MyNode("G");
        addChild(e, f, g);
    }

    public static void addChild(MyNode node, MyNode left, MyNode right) {
        node.setLeft(left);
        node.setRight(right);
    }

    // 前序
    public static void preTraversal(MyNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getData());
        preTraversal(node.getLeft());
        preTraversal(node.getRight());

    }

    // 中序
    public static void middleTraversal(MyNode node) {
        if (node == null) {
            return;
        }
        middleTraversal(node.getLeft());
        System.out.print(node.getData());
        middleTraversal(node.getRight());


    }

    // 后序
    public static void postTraversal(MyNode node) {
        if (node == null) {
            return;
        }
        postTraversal(node.getLeft());
        postTraversal(node.getRight());
        System.out.println(node.getData());

    }



    // 按层遍历二叉树.
    public static void processNodeLayer(MyNode node) {
        if (null == node) {
            return;
        }

        LinkedList s = new LinkedList();
        s.add(node);

        while(!s.isEmpty()) {
            MyNode tmpNode = (MyNode) s.poll();
            System.out.print(tmpNode.getData());

            MyNode left = tmpNode.getLeft();
            MyNode right = tmpNode.getRight();

            if (null != left) {
                s.add(left);
            }

            if (null != right) {
                s.add(right);
            }
        }
    }

}

运行结果如下，实现了各种遍历：

From：一号门