二叉树

节点类定义

class TreeNode {
    private String value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(String value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    public void setLeft(TreeNode left) {
        this.left = left;
    }
    public void setRight(TreeNode right) {
        this.right = right;
    }
    public String getValue() {
        return this.value;
    }
    public TreeNode getLeft() {
        return this.left;
    }
    public TreeNode getRight() {
        return this.right;
    }
}

构建二叉树

//例：根据 nodes={'a','b','c','#','#','d','e','#','g','#','#','f','#','#','#'} 构建
public static Main buildTree(char[] nodes) {
    char c = nodes[position];
    position++;//position定义为类静态变量
    if (c == '#') {
        return null;
    }

    TreeNode root = new TreeNode(c);
    root.setLeft(buildTree(nodes));
    root.setRight(buildTree(nodes));

    return root;
 }

//根据前序和中旭构造
public static TreeNode buildTree(String str1, String str2) {
    if (str1.length() == 0) {
        return null;
    }
    String c = str1.substring(0, 1);

    TreeNode root = new TreeNode(c);

    int position = str2.indexOf(c);

    root.setLeft(buildTree(str1.substring(1,position+1), str2.substring(0,position)));
    root.setRight(buildTree(str1.substring(position+1),str2.substring(position + 1)));

    return root;
 }

遍历

//前序遍历
public static void InOrder(Main root) {
   if (root == null) {
       return;
   }
   InOrder(root.left);
   System.out.printf("%c ", root.getValue());
   InOrder(root.right);
}

//后序遍历
public static void PostOrder(TreeNode root) {
   if (root == null) {
       return;
   }
   PostOrder(root.getLeft());
   PostOrder(root.getRight());
   System.out.printf("%s", root.getValue());
}