1

完全な開示のために、これはHWでしたが、割り当てはすでに期限が切れていました。

単純なツリーを次のように定義すると、次のようになります。

class Tree (object):
    __slots__ = "node","children"
    def __init__(self,node,children=[]):
        self.node = node
        self.children = children

文字列からツリーを構築するにはどうすればよいですか？文字列モデルでは、「NIL」はツリーの終わりを意味します。したがって、文字列1 2 5 NIL 3 4 NIL NIL NIL NILはのような形のツリーを返しt = Tree(1, [Tree(2, [Tree(5, []), Tree(3, [Tree(4)])])])ます。このソリューションでは、再帰やスタックを使用できます。スタックと再帰は理解できたと思いましたが、この問題は理解できません。何か案は？

編集
さらに情報を追加するために、次のようにツリーを印刷できます。

def __str__(self):
    return "(%s)" % " ".join(map(str,[self.node]+self.children))

ツリーを作成して印刷することに近づくことができませんでした。私が考えることができたのは、ツリーを作成するための文字列のように見える文字列を作成することだけでした。私は持っています：

def delinearize(self, linear_string):
    @staticmethod
    tree_data = linear_string.split()
    tree_str = ""
    if tree_data[0] == "NIL":
        print "Tree needs initial root node"
        return
    for entry in tree_data:
        if entry != "NIL":
                tree_str += "Tree("+entry+", ["
        elif entry == "NIL":
                tree_str += "]),"
4

3 に答える 3

2

あなたの例では、この入力に対して：

1 2 5 NIL 3 4 NIL NIL NIL NIL

これが結果になるはずだとあなたは言います（理解を容易にするためにあなたのバージョンをフォーマットしたことに注意してください）：

Tree(1, [
    Tree(2, [
        Tree(5, []),
        Tree(3, [
            Tree(4)
        ])
    ])
])

これは「次のように見えます」：

  1
  |
  2
 / \
5   3
    |
    4

これ (および nneonneo の有益なコメント) から、これらのツリーが文字列からどのように構築されているかを判断できます。次のように動作するようです：

  1. 「現在の」ノードと見なされる、理論上のルート ノードから始めます。
  2. 非 NIL 値ごとに、それを現在のノードの子として追加し、新しい現在のノードとしてマークします。つまり、下ります。
  3. NIL 値ごとに、現在のノードの親を新しい現在のノードとしてマークします。つまり昇天。
  4. 理論上のルート ノードに再び到達すると、完了です (文字列は完全に消費されます)。

スペースを節約したい場合は、ルートに戻るための末尾の NIL を省略できることに注意してください。一方、それらを含めると、最後にサニティ チェックがサポートされます。

上記の概要を使用すると、再帰なしで反復的に実装できます。再帰的な解決策を好む人もいますが、どちらの方法も同じように強力なので、後者は演習として残します!

于 2013-02-10T02:40:26.120 に答える
0

したがって、次の 2 つのことがわかっているとします。

  • 入力文字列からNILを読み取った場合、ツリーを読み取って空にしたことがわかります。
  • 数値を読み取る場合、ルートにその数値を含む空でないツリーがあり、入力文字列から 2 つのツリー (左の子用と右の子用) を読み取る必要があります。

これで、ツリーを読み取る準備が整いました:)。次の C のような構造を想定します (演習として Python でこれを行うことができますが、Python の方がずっときれいです)。

struct tree {
   int value;
   tree *left;
   tree *right;
}

基本的に、char* を受け取り、最初のトークンを返し、入力文字列を次のトークンを指すように変更するメソッドを手を振って、入力ストリームで次のことができます。

tree *readTree(char *&inputString) {
   char *token = read_next_token(inputString); 
   if (strcmp(token, "NIL") {
      // empty tree .. we return
      return NULL;
   }

   struct tree* node = malloc(sizeof(struct tree));
   node->value = token_as_int(token);

   // note that after the readTree is called the inputString will be modified
   // that's why i defined it to take a reference to a pointer of chars.
   node->left = readTree(inputString);
   node->right = readTree(inputString);
   return node; 
}

read_next_token は次のように定義されます。

char *read_next_token(char*&inputString) {
  char *token = inputString;

  while ( *inputString != ' ' )
    inputString++;

  *inputString = 0; // make the token a null terminated string.

  while ( *inputString == ' ' ) inputString++;

  return token;
}
于 2013-02-10T02:40:53.037 に答える
0

多分このようなもの：

#! /usr/bin/python3.2

class Tree:
    def __init__ (self, value):
        self.value = value
        self.parent = None
        self.children = []

    def __iadd__ (self, child):
        child.parent = self
        self.children.append (child)
        return self

    def fromString (string):
        return Tree.fromList (string.split () ) [0]

    def fromList (list):
        node = Tree (list [0] )
        list = list [1:]
        while list [0] != 'NIL':
            child, list = Tree.fromList (list)
            node += child
        return node, list [1:]

    def __repr__ (self):
        return '{}{}'.format (self.value, ': {}'.format (self.children) if self.children else '')

t = Tree.fromString ('1 2 5 NIL 3 4 NIL NIL NIL NIL')
print (t)

t = Tree.fromString ('1 2 NIL 3 4 NIL 5 NIL 6 NIL NIL 7 NIL NIL')
print (t)
于 2013-02-10T06:05:21.493 に答える