二叉树搜索遍历(Java版)

下面是一张表达式树的树图

为了用java代码构造树模型，我对树图的节点进行了编号：根结点R，左侧结点依次用L加上数字来表

示，右侧结点依次用R+数字来表示

结点类 

public class Node {
  private Object data;
    private Node leftNode;
    private Node rightNode;

    //适用于只有数据没有左右子结点的结点
    public Node(Object data) {
        this.data = data;
        this.leftNode = null;
        this.rightNode = null;
    }

    //适用于有或没有左右子结点的结点
    public Node(Object data, Node leftNode, Node rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    ...  //getter and setter method 
}

主类

public class BiaoDaShiTree {
    public static Node init()
    {
          Node L5 = new Node("c");
                    Node L4 = new Node("b");
                    Node L3 = new Node("*",L4,L5);
                    Node L2 = new Node("a");
                    Node L1 = new Node("+",L2,L3);

                    Node R7 = new Node("g");
                    Node R6 = new Node("f");
                    Node R5 = new Node("e");
                    Node R4 = new Node("d");
                    Node R3 = new Node("*",R4,R5);
                    Node R2 = new Node("+",R3,R6);
                    Node R1 = new Node("*",R2,R7);

          Node root = new Node("+",L1,R1);
          return root;
    }

    public static void main(String[] args)
    {
        Node root = init();
        System.out.println("前序遍历");
        preorderTravesal(root);
        System.out.println();
        System.out.println("中序遍历");
        inorderTravesal(root);
        System.out.println();
        System.out.println("后序遍历");
        postorderTravesal(root);

    }

    //前序遍历
    public static void preorderTravesal(Node root)
    {
        System.out.print(root.getData());
        Node leftNode = root.getLeftNode();
        Node rightNode = root.getRightNode();
        if(leftNode !=null)
        {
            preorderTravesal(leftNode);
        }

        if(rightNode != null)
        {
            preorderTravesal(rightNode);
        }
    }

    //中序遍历
    public static void inorderTravesal(Node root)
    {
        Node leftNode = root.getLeftNode();
        Node rightNode = root.getRightNode();
        if(leftNode !=null)
        {
            inorderTravesal(leftNode);
        }

        System.out.print(root.getData());

        if(rightNode != null)
        {
            inorderTravesal(rightNode);
        }
    }

    //后序遍历
    public static void postorderTravesal(Node root)
    {
        Node leftNode = root.getLeftNode();
        Node rightNode = root.getRightNode();
        if(leftNode !=null)
        {
            postorderTravesal(leftNode);
        }

        if(rightNode != null)
        {
            postorderTravesal(rightNode);
        }

        System.out.print(root.getData());
    }
}

打印结果：

规律总结：
前序遍历：对结点的处理工作（2个例子就是打印结点数据）在对结点诸儿子结点计算之前进行的。

 后序遍历：对结点的处理工作（2个例子就是打印结点数据）在对结点诸儿子结点计算之后进行的。

 中序遍历：对结点的处理工作（2个例子就是打印结点数据）在对结点诸儿子结点计算之间进行的。