1

BST のすべてのノードを削除するコードを作成しようとしています (各ノードには、左、右、およびデータの 3 つの属性のみがあり、親ポインターはありません)。次のコードは私が思いついたものです。ツリーの右半分のみを削除し、左半分はそのままにします。左半分も削除されるように変更するにはどうすればよいですか (したがって、最終的には、左サブツリーも右サブツリーも持たないルート ノードのみが残ります)。

def delete(root):
    global last
    if root:
     delete(root.left)
     delete(root.right)
     if not (root.left or root.right):
        last = root
     elif root.left == last:
        root.left = None
     else:
        root.right = None

第二に、スタックやその他の関連するデータ構造を使用して、反復的なアプローチを提案できる人はいますか?

4

4 に答える 4

4

両方のサブツリーを削除したい場合、再帰する必要はありません。root.leftand root.righttoを設定するだけNoneで、ガベージ コレクタに処理を任せることができます。delete実際、最初から関数を作成するのではなく、設定するだけroot = Noneで完了できます。

編集:データ値に対してクリーンアップ コードを実行する必要がある場合、GC が十分に機能しない場合は、ツリーを再帰的に取得してすべての値を取得することをお勧めします。ツリー内のリンクを破棄する必要はあまりないはずですが、適切な措置としてこれも行います。

def delete(node):
    if node:
        node.data.cleanup() # run data value cleanup code

        delete(node.left)   # recurse
        delete(node.right)

        node.data = None    # clear pointers (not really necessary)
        node.left = None
        none.right = None

また、ツリーをトラバースするための反復的なアプローチについて質問されましたが、これはもう少し複雑です。deque先祖を追跡するために (スタックとして) を使用してトラバーサルする方法を次に示します。

from collections import deque

def delete_iterative(node):
    stack = deque()
    last = None

    # start up by pushing nodes to the stack until reaching leftmost node
    while node:
        stack.append(node)
        node = node.left

    # the main loop
    while stack:
        node = stack.pop()

        # should we expand the right subtree?
        if node.right && node.right != last: # yes
            stack.append(node)
            node = node.right

            while node: # expand to find leftmost node in right subtree
                stack.append(node)
                node = node.left

        else: # no, we just came from there (or it doesn't exist)
            # delete node's contents
            node.data.cleanup()

            node.data = None # clear pointers (not really necessary)
            node.left = None
            node.right = None

            # let our parent know that it was us it just visited
            last = node
于 2012-10-13T10:58:28.507 に答える
4

Blckknght はガベージ コレクションについては正しいですが、例が示唆するよりも複雑なクリーンアップを実行したい場合、またはコードが機能しなかった理由を理解したい場合は、追加の回答を提供します。

あなたの問題はelif node.left == last小切手のようです。

last変数が何に使用されているのか、その背後にあるロジックが何なのかわかりません。
しかし、問題は、それnode.leftが等しいことはほとんどないことlastです(両方の子がすでに に設定されている場合にのみ、ノードをlast変数に割り当てますNone。これは、興味深いノード (子を持つノード) のいずれにも当てはまりません)。

コードを見ると、 if node.leftis not equal tolastで、右側の子のみが に設定されるためNone、サブツリーの右側の部分のみが削除されることがわかります。

私はpythonを知りませんが、これはうまくいくはずです：

def delete(node):
    if node:

        # recurse: visit all nodes in the two subtrees
        delete(node.left)           
        delete(node.right)

        # after both subtrees have been visited, set pointers of this node to None
        node.left = None
        node.right = None

（関数に指定されたノードはツリーのルートノードである必要はないため、rootパラメーターの名前を自由に変更しました。）node

于 2012-10-13T11:36:03.810 に答える
2

スタックを使用した反復的なポストオーダー トラバーサルは、次のようになります。

def is_first_visit(cur, prev):
    return prev is None or prev.left is cur or prev.right is cur

def visit_tree(root):
    if root:
        todo = [root]
        previous = None
        while len(todo):
            node = todo[-1]
            if is_first_visit(node, previous):
                # add one of our children to the stack
                if node.left: 
                    todo.append(node.left)
                elif node.right:
                    todo.append(node.right)
                # now set previous to ourself and continue
            elif previous is node.left:
                # we've done the left subtree, do right subtree if any
                if node.right:
                    todo.append(node.right)
            else: 
                # previous is either node.right (we've visited both sub-trees)
                # or ourself (we don't have a right subtree)
                do_something(node)
                todo.pop()
            previous = node

do_something「実際にこのノードを削除する」と呼びたいことは何でもします。

各ノードに属性を設定して、まだ呼び出されているかどうかを示すことで、もう少し簡単に行うことができますが、ノードに何かがある場合、または変更したくないdo_something場合は明らかにうまく機能しません。__slots__フラグを許可するノード タイプ。

于 2012-10-13T12:13:40.393 に答える
0

再帰呼び出しの後にこれらの条件で何をしているのかわかりませんが、これで十分だと思います:

def delete(root):
  if root:
    delete(root.left)
    delete(root.right)

    root = None

コメントで指摘されているように、Python は参照によってパラメーターを渡しません。その場合、次のように Python でこれを機能させることができます。

def delete(root):
  if root:
    delete(root.left)
    delete(root.right)

    root.left = None
    root.right = None

Usage:
delete(root)
root = None

反復的なアプローチについては、これを試すことができます。それは疑似コードです。私はpythonを知りません。基本的には BF 検索を行います。

delete(root):
  make an empty queue Q
  Q.push(root)
  while not Q.empty:
    c = Q.popFront()
    Q.push(c.left, c.right)
    c = None

繰り返しますが、ルートを関数として使用する場合、デフォルトではルートは変更されませんが、他のすべてのノードは削除されます。関数呼び出しの後にルートを None に設定するか、パラメーターを削除してグローバルルート変数で作業することができます。

于 2012-10-13T11:17:52.000 に答える