tree - 再帰とスタックを使用せずに、バイナリ ツリーの順序どおりのトラバーサルを行うことはできますか?

Question

再帰やスタックを使用せずにバイナリツリーを順番にトラバースするための解決策を誰かに教えてもらえますか?

Answer 1

2番目の編集：これは正しいと思います。通常の node.left_child と node.right_child に加えて、node.isRoot、node.isLeftChild、および node.parent が必要です。

state = "from_parent"
current_node = root
while (!done)
  switch (state)
    case "from_parent":
      if current_node.left_child.exists
        current_node = current_node.left_child
        state = "from_parent"
      else
        state = "return_from_left_child"
    case "return_from_left_child"
      if current_node.right_child.exists
        current_node = current_node.right_child
        state = "from_parent"
      else
        state = "return_from_right_child"
    case "return_from_right_child"
      if current_node.isRoot
        done = true
      else
        if current_node.isLeftChild
         state = "return_from_left_child"
        else
         state = "return_from_right_child"
        current_node = current_node.parent

Answer 2

1. ダブル スレッド ツリー

ツリー ノードに親参照/ポインターがある場合は、トラバーサル中にどのノードから来たかを追跡して、次にどこに行くかを決めることができます。

Python の場合:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = None
        if self.left:
            self.left.parent = self
        if self.right:
            self.right.parent = self

    def inorder(self):
        cur = self
        pre = None
        nex = None
        while cur:
            if cur.right and pre == cur.right:
                nex = cur.parent
            elif not cur.left or pre == cur.left:
                yield cur.value  # visit!
                nex = cur.right or cur.parent
            else:
                nex = cur.left
            pre = cur
            cur = nex

root = Node(1,
            Node(2, Node(4), Node(5)),
            Node(3)
        )

print([value for value in root.inorder()])  # [4, 2, 5, 1, 3]

2.シングルスレッドツリー

ツリー ノードに親参照/ポインターがない場合は、いわゆるモリス トラバーサルを実行できます。これは一時的にツリーを変更し、right適切な子を持たないノードのプロパティを一時的にそのインオーダー サクセサーを指すようにします。ノード：

Python の場合:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def inorder(self):
        cur = self
        while cur:
            if cur.left:
                pre = cur.left
                while pre.right:
                    if pre.right is cur:
                        # We detect our mutation. So we finished
                        # the left subtree traversal.
                        pre.right = None
                        break
                    pre = pre.right
                else:  # prev.right is None
                    # Mutate this node, so it links to curr
                    pre.right = cur
                    cur = cur.left
                    continue
            yield cur.value
            cur = cur.right

root = Node(1,
            Node(2, Node(4), Node(5)),
            Node(3)
        )

print([value for value in root.inorder()])

Answer 3

はい、できます。これを行うには、ツリーを昇るために親ポインターが必要です。

Answer 4

二分木をたどるには、再帰によって暗示される（または配列によって明示的に）スタックによって提供される可能性のあるある種の状態（ノードがサクセサーを訪問した後に戻る）が必要になるためです。

答えはノーです。できません。(古典的な定義によると)

反復的な方法での二分木トラバーサルに最も近いのは、おそらくヒープを使用することです

編集：または、すでにスレッド化されたバイナリツリーを示しているように、

Answer 5

ここで誰かがすでに述べたように、それは可能ですが、親ポインタなしではできません。親ポインターを使用すると、必要に応じて基本的に「パス」をトラバースできるため、ノードを出力できます。しかし、再帰が親ポインターなしで機能するのはなぜですか? 再帰を理解していれば、次のようになります (再帰スタックを想像してください)。

  recursion //going into
   recursion
    recursion
     recursion 
     recursion //going back up
    recursion
   recursion
  recursion

したがって、再帰が終了すると、バイナリツリーの選択された側が逆の順序で出力されます。