どのプリオーダートラバーサルによって与えられたビットシーケンスで再帰バイナリツリーを作成するには？

Question

私が問題を抱えている問題はこれです。

各ノードは、2ビットx1とx2で表されます。ノードが左の の子を有する場合、x1は1である。そうでない場合、x1は0である。同様に右の の子の場合、x2は1または0のいずれかである。この規則では、 二分木プリオーダートラバーサルによって形成されるビットシーケンス。 の例では、 "11010011001000"から、次のツリーを構築できます。 を与えられた特定のビットシーケンスをプリオーダートラバーサルで取り、バイナリツリーを構築する再帰関数を作成します。

今、私は同様の質問、Construct tree with pre-order traversal givenから情報を取得してきたが、この場合には、単一のノードに対してx1とx2の両方を考慮しなければならないので、それはとても異なっているようです...私はこれを何時間も考えてきましたが、再帰を使って良いロジックを思いつくことはできません。どんな助けもありがとう。ありがとう！

Answer 1

解決策は、preorderであなたのツリーを横断し、その間に（2つの値を取り出して削除する）、nodeを追加するだけです。 static String string = "11010011001000";

あなたが呼び出すことができます。文字列はちょうどグローバル変数である

private static void createTree(Node root) { 

    if(string.isEmpty() || root == null) { 
     return; 
    } 

    if(string.charAt(0) == '1') { 
     root.left = new Node(); 
    } 

    if(string.charAt(1) == '1') { 
     root.right = new Node(); 
    } 
    string = string.substring(2); 
    createTree(root.left); 
    createTree(root.right); 

} 

：

class Node { 
    int value; 
    public Node left; 
    public Node right; 
} 

あなたはこのようなツリーを作成することができます：あなたはこのNodeを持っていることを考えると

このような方法：

Node root = new Node(); 
createTree(root); 

rootは、ツリーの実際のルートになります。

Answer 2

あなたの質問は同類にこの1になります： http://www.geeksforgeeks.org/construct-a-special-tree-from-given-preorder-traversal/

私はあなたの例の特定の要件を満たすために与えられたコードを少し変更しました。私はあなたの質問のノード（手紙）の与えられた順序を無視し、ちょうど木の構造に焦点を合わせました。時間の複雑さは、期待通りにO(N)です。すべては明らかであるので私はそれ以上の情報を与えなかった。ご質問がある場合は、お気軽にコメントを残してください。

public class BinaryTree { 
    class Node { 
     char data; 
     Node left, right; 

     Node(char item) { 
      data = item; 
      left = right = null; 
     } 
    } 

    class Index { 
     int index = 0; 
    } 

    Node root; 
    Index i = new Index(); 

    Node constructTreeUtil(String bitSequence, Index index_ptr, int n, Node temp) { 
     int index = index_ptr.index; 

     String bits = bitSequence.substring(index * 2, index * 2 + 2); 

     if (index == n) 
      return null; 

     temp = new Node((char) (index + 65)); 
     (index_ptr.index)++; 

     if (bits.charAt(0) == '1') 
      temp.left = constructTreeUtil(bitSequence, index_ptr, n, temp.left); 

     if (bits.charAt(1) == '1') 
      temp.right = constructTreeUtil(bitSequence, index_ptr, n, temp.right); 

     return temp; 
    } 

    Node constructTree(String bitSequence, int n, Node node) { 
     int index = 0; 
     return constructTreeUtil(bitSequence, i, n, node); 
    } 

    public static void inorder(Node node) { 
     if (node == null) return; 
     System.out.println(node.data + "=> "); 

     if (node.left != null) 
      System.out.println("Left node: " + node.left.data); 

     if (node.right != null) 
      System.out.println("Right node: " + node.right.data); 

     System.out.println(); 
     inorder(node.left); 
     inorder(node.right); 
    } 

    public static void main(String args[]) { 
     BinaryTree tree = new BinaryTree(); 

     // Bit sequence 
     String bitSequence = "11010011001000"; 

     // Number of nodes 
     int n = bitSequence.length()/2; 

     // Tree construction 
     Node node = tree.constructTree(bitSequence, n, tree.root); 

     // Print tree nodes inorder 
     inorder(node); 
    } 
} 

Answer 3

私は私の答えの1行目にこのdeclaimerを入れています50評判到達する前に：

を私が代わりにコメントで簡単な応答をしたいが、私は十分な評判を持っていないので、私は完全な答えを作って、うまくいけば私の邪悪な答えはまだ助けになるでしょう。

---

DFSは、このタスクのために完全である - それはプリオーダートラバーサルが何をしているのか、基本的です：

def DFS(node): 
    if(node == NULL) return 
    sequence += notNull(node.l) 
    sequence += notNull(node.r) 
    DFS(node.l) 
    DFS(node.r) 

^^^これはあなたの順序を構築する方法です。

は幸い逆は非常に単純です：代わりに子供のexistanceによって、シーケンスの次の文字を決定する

が

def inverseDFS(node): 
    if(node == NULL) return 
    node.l = new Node() if(readBuffer(sequence) == '1') else NULL 
    node.r = new Node() if(readBuffer(sequence) == '1') else NULL 
    inverseDFS(node.l) 
    inverseDFS(node.r) 

^^^のみライン2と3に変更され、今、私たちが判断することができますこれはiff関係であるため、読み込まれた次の文字に基づいて子の存在が検出されます。

ここではより洗練されたC++コードがあります。はい、私のコーディングスタイルは他のものをうんざりさせるかもしれません。

/* Author haleyk10198 */ 
/* FOR ACM-ICPC WF*/ 
#include <bits/stdc++.h> 

using namespace std; 

struct Node{ 
    static int nodeCnt; 
    int id; 
    Node *l, *r; 
    Node(){ 
     l = r = nullptr; 
     this->id = nodeCnt++; 
    } 
    friend ostream& operator<<(ostream&, const Node); 
}*root = new Node(); 

ostream& operator<<(ostream &out, const Node node){ 
    cout << "Node id: " << node.id 
      << " | left child is " << (node.l? node.l->id: -1) 
      << " | right child is " << (node.r? node.r->id: -1) << endl; 
} 

int Node::nodeCnt, strStreamPos = 0; 
string str; 

void dfs(Node *node){ 
    if(not node) 
     return; 

    if(str[strStreamPos++] == '1') 
     node->l = new Node(); 
    if(str[strStreamPos++] == '1') 
     node->r = new Node(); 

    cout << *node << endl; 

    dfs(node->l); 
    dfs(node->r); 
} 

int main(){ 

    cin >> str; 

    dfs(root); 

    return 0; 
}