0

これは、Python でバイナリ ツリーをトラバースする方法です。

def binary_tree(root):
  if root.left:
    binary_tree(root.left)
  print root
  if root.right:
    binary_tree(root.right)

通過したパスを返す必要がある場合:

def binary_tree(node, path):
  if root.left:
    binary_tree(root.left)
  path.append(root)
  if root.right:
    binary_tree(root.right)
  return path

わかりました、簡単です。木のトラバーサルには自信があるので、以下をやってみます。

def nary_tree(root, value):
    """return True if there is a node with value exists in root"""
    if not root: #empty tree
        return False
    if root.left:
        nary_tree(root.left, value)
    if root.data == value: #recurse up until the current node has a right child
        return True
    if root.right:
        nary_tree(root.right, value)
    return False

これは、True を返す必要があるときに True を返しません。そのため、関数にステップインしてデバッグを試みます。値を返すだけで再帰を回避することは想定されていないことに気付きました。一致するノードがある場合、上記のコードはTrue1 回およびFalse何度も返され、ほとんどの場合False. だから私は次のことを試します：

def nary_tree(root, value):
    """return True if there is a node with value exists in root"""
    if not root: #empty tree
        return False
    if root.left:
        return nary_tree(root.left, value)
    if root.data == value:
        #but in this case, this is never executed
        return True 
    if root.right:
        return nary_tree(root.right, value)
    return False #how was this being executed in above example then?

質問:

  1. 私は何を誤解していますか？
  2. 上記のコードをどのように修正しますか？

私は再帰関数を書くことにかなり慣れてきましたが、まだ混乱しているようです。

4

1 に答える 1

0

現在のノードにデータがある場合でも、左のノードがある場合は、関数から戻っています。理想的には、これはこうあるべきだった

def nary_tree(root, value):
    """return True if there is a node with value exists in root"""
    if not root: #empty tree
        return False
    if root.data == value:
        return True 
    if nary_tree(root.left, value):
        return True
    if nary_tree(root.right, value):
        return True
    return False #how was this being executed in above example then?
于 2013-11-15T02:28:25.653 に答える