1

問題は、予約注文リストと各ノードが持つ子の数のシーケンスからバイナリ ツリーを構築することです。例: "BAC" と "200" は 1 つの入力で、"ABC" の順不同のリストになる可能性があります。

私の現在の方法は、2番目のcharsequence（数字のあるもの）で「2」をチェックすることです.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 に答える