1

问题是从预排序列表和每个节点具有的子节点数量的序列构建二叉树。例如：“BAC”和“200”可能是一个输入，导致“ABC”的有序列表。

我目前的方法是检查'2'的第二个字符序列（带有数字的那个），它有两个孩子，'0'，它没有孩子，'L'，它有一个左孩子，和'R'，它有一个正确的孩子。为此，我使用以下方法：

public static BinaryTree preOrderBuild(CharSequence charElements,
        CharSequence childCodes) {
    // TODO Auto-generated method stub.
    BinaryTree build = new BinaryTree();
    char first;
    if (childCodes.length() == 0) {
        return new BinaryTree();
    } else {
        first = childCodes.charAt(0);
    }
    if (first == '2') {
        int sum = 1;
        for (int i = 1; i < childCodes.length(); i++) {
            if (childCodes.charAt(i) == 'R' || childCodes.charAt(i) == 'L')
                sum += 0;
            else if (childCodes.charAt(i) == '2')
                sum += 1;
            else if (childCodes.charAt(i) == '0')
                sum--;
            if (sum == 0) {
                BinaryTree Left = preOrderBuild(
                        charElements.subSequence(1, i + 1),
                        childCodes.subSequence(1, i + 1));
                BinaryTree Right = preOrderBuild(
                        charElements.subSequence(i + 1,
                                charElements.length()),
                        childCodes.subSequence(i + 1, childCodes.length()));
                build.merge(charElements.charAt(0), Left, Right);
            }
        }
    } else if (first == 'R' || first == 'r') {
        BinaryTree right = preOrderBuild(
                charElements.subSequence(1, charElements.length()),
                childCodes.subSequence(1, childCodes.length()));
        build.merge(charElements.charAt(0), new BinaryTree(), right);
    } else if (first == 'L' || first == 'l') {
        BinaryTree left = preOrderBuild(
                charElements.subSequence(1, charElements.length()),
                childCodes.subSequence(1, childCodes.length()));
        build.merge(charElements.charAt(0), left, new BinaryTree());
    } else {
        build.merge(charElements.charAt(0), new BinaryTree(),
                new BinaryTree());
    }
    return build;
}

它基本上处理 childCodes 序列以确定树的每个分支在哪里中断。问题是对于较大的树，它只处理前几个项目，然后折叠。（较大树的示例是：“ABCDEFGHIJKLMNOPQRSTU”，子代码为“220022002200LRR20RLL0”）

4

1 回答 1

2

如果你从右到左，你不需要做任何递归。

Stack<BinaryTree> stack = new Stack<BinaryTree>();

for (int i = childCodes.length() - 1; i >= 0; i--) {
    char code = childCodes.charAt(i);
    char name = charElements.charAt(i);
    if (code == '0') {
        stack.push(new BinaryTree(name, null, null));
    }
    else if (code == 'L') {
        stack.push(new BinaryTree(name, stack.pop(), null));
    }
    else if (code == 'R') {
        stack.push(new BinaryTree(name, null, stack.pop()));
    }
    else if (code == '2') {
        stack.push(new BinaryTree(name, stack.pop(), stack.pop()));
    }
}

return stack.pop();

使用您的数据，它会生成以下树：

A
+-B
| +-C
| '-D
'-E
  +-F
  | +-G
  | '-H
  '-I
    +-J
    | +-K
    | '-L
    '-M
      +-N
      | +-(null)
      | '-O
      |   +-(null)
      |   '-P
      |     +-Q
      |     '-R
      |       +-(null)
      |       '-S
      |         +-T
      |         | +-U
      |         | '-(null)
      |         '-(null)
      '-(null)
于 2012-09-26T12:47:47.653 回答