如何從預訂器和孩子形成二叉樹charsequence

問題是從預訂器列表和每個節點所擁有的子數的序列構建二叉樹。例如：「BAC」和「200」可能是一個輸入，導致「ABC」的中序列表。如何從預訂器和孩子形成二叉樹charsequence

我目前的方法是檢查'2'的第二個charsequence（帶數字的那個），它有兩個孩子，'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序列，以確定樹的每個分支中斷的位置。問題是，對於較大的樹木，它只處理前幾個項目，然後崩潰。（較大的樹的示例是：帶有子代碼「220022002200LRR20RLL0」的「ABCDEFGHIJKLMNOPQRSTU」）

來源

2012-09-26 user1699453

如果您從右向左移動，則不需要執行任何遞歸。

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-26 12:47:47

如何從預訂器和孩子形成二叉樹charsequence

回答

相關問題