Java实现二叉树

理论不说了，直接上代码

首先是定义一个结点类

public class Node {
    String data;
    Node left;
    Node right;

    public Node(String d) {
        this.data = d;
        this.left = null;
        this.right = null;
    }

    public Node() {
        this.data = null;
        this.left = null;
        this.right = null;
    }
}

这里没有封装，只是简单的表示结点的数据结构

树类

public class Tree {

    //创建根节点
    Node root = new Node();

    //创建一棵二叉树
    public Node create(Node node) {
        Scanner sc = new Scanner(System.in);
        String value = sc.next();

        if (value.trim().equals("#")) {
            node = null;

        } else {
            node = new Node();
            node.data = value;
            node.left = create(node.left);
            node.right = create(node.right);
            return node;
        }

        return node;
    }

    //先序遍历
    public void PreOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + "  ");
            PreOrder(node.left);
            PreOrder(node.right);
        }
    }

    //中序遍历
    public void InOrder(Node node) {
        if (node != null) {
            InOrder(node.left);
            System.out.print(node.data + "  ");
            InOrder(node.right);
        }
    }

    //后序遍历
    public void PostOrder(Node node) {
        if (node != null) {
            PostOrder(node.left);
            PostOrder(node.right);
            System.out.print(node.data + "  ");
        }
    }

}

注意：如果在在判断输入是否为"#"，不能使用==，详见Java中==和equals的区别

测试类：

public class TreeTest {
    public static void main(String[] args) {
        Tree tree = new Tree();
        //先序遍历创建  ：根左右
        tree.root = tree.create(tree.root);
        //先序遍历
        System.out.println("先序遍历");
        tree.PreOrder(tree.root);
        System.out.println();
        System.out.println("中序遍历");
        tree.InOrder(tree.root);
        System.out.println();
        System.out.println("后序遍历");
        tree.PostOrder(tree.root);
    }
}

如果我们建立一个这样的二叉树

那么它的输入为: ABD##FE###CG#H##I##

输出结果：

先序遍历
A  B  D  F  E  C  G  H  I  
中序遍历
D  B  E  F  A  G  H  C  I  
后序遍历
D  E  F  B  H  G  I  C  A