33

再帰を使用せずにプレオーダートラバーサルを理解することはできますが、インオーダートラバーサルに苦労しています。おそらく、再帰の内部動作を理解していないために、私はそれを理解していないようです。

これは私がこれまでに試したことです：

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

内側のwhileループは正しく感じられません。また、一部の要素は2回印刷されています。そのノードが以前に出力されたかどうかを確認することでこれを解決できるかもしれませんが、これには別の変数が必要です。どこが間違っているのですか？

注文後のトラバーサルは試していませんが、似ていると思います。そこでも同じ概念上の障害に直面します。

御時間ありがとうございます！

LifoPS：との定義Node：

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

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo) == 0:
            return None
        ret, self.lifo = self.lifo
        return ret
4

15 に答える 15

89

再帰アルゴリズム (疑似コード) から始めます。

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

これは末尾再帰の明確なケースであるため、簡単に while ループに変換できます。

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

再帰呼び出しが残っています。再帰呼び出しが行うことは、新しいコンテキストをスタックにプッシュし、コードを最初から実行してから、コンテキストを取得して、それが行っていたことを続行することです。したがって、ストレージ用のスタックと、反復ごとに、「最初の実行」状況 (null 以外のノード) か「戻り」状況 (null ノード、空でないスタック) かを判断するループを作成します。 ) を実行し、適切なコードを実行します。

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we are now returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

把握するのが難しいのは「戻り」の部分です。ループ内で、実行中のコードが「関数に入る」状況にあるか、「呼び出しから戻る」状況にあるかを判断する必要があります。if/elseコードに非終端再帰があるのと同じ数のケースを持つチェーンがあります。

この特定の状況では、ノードを使用して状況に関する情報を保持しています。別の方法は、それをスタック自体に格納することです (コンピューターが再帰に対して行うのと同じように)。その手法では、コードは最適ではありませんが、従うのは簡単です

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state: 
       case 'entry': 
         if node == None do: break; // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break;
       case 'after-left-traversal': 
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile
于 2010-01-22T11:05:51.757 に答える
17

これは、単純な順序どおりの非再帰的なc++コードです。

void inorder (node *n)
{
    stack s;

    while(n){
        s.push(n);
        n=n->left;
    }

    while(!s.empty()){
        node *t=s.pop();
        cout<<t->data;
        t=t->right;

        while(t){
            s.push(t);
            t = t->left;
        }
    }
}
于 2011-02-06T19:55:31.000 に答える
3 
def print_tree_in（root）：
    スタック=[]
    現在=ルート
    Trueの場合：
        currentはNoneではありません：
            stack.append（current）
            current = current.getLeft（）;
        スタックしない場合：
            戻る
        current = stack.pop（）
        current.getValue（）を出力します
        current.getRightがNoneであり、スタックしている間：
            current = stack.pop（）
            current.getValue（）を出力します
        current = current.getRight（）;
于 2012-01-02T18:44:54.767 に答える
1

再帰を伴わない単純な反復順序トラバーサル

'''iterative inorder traversal, O(n) time & O(n) space '''

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

def inorder_iter(root):

    stack = [root]
    current = root

    while len(stack) > 0:
        if current:
            while current.left:
                stack.append(current.left)
                current = current.left
        popped_node = stack.pop()
        current = None
        if popped_node:
            print popped_node.value
            current = popped_node.right
            stack.append(current)

a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')

b.right = d
a.left = b
a.right = c

inorder_iter(a)
于 2016-10-08T14:06:34.420 に答える
1 
def traverseInorder(node):
   lifo = Lifo()

  while node is not None:
    if node.left is not None:
       lifo.push(node)
       node = node.left
       continue

   print node.value

   if node.right is not None:
      node = node.right
      continue

   node = lifo.Pop()
   if node is not None :
      print node.value
      node = node.right

PS: 私は Python を知らないので、構文の問題がいくつかあるかもしれません。

于 2010-01-22T11:06:20.063 に答える
1

以下は、C# (.net) でスタックを使用した順序でのトラバーサルのサンプルです。

(post order iterative については、次を参照してください: Post order traversal of binary tree without recursion )

public string InOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                var iterativeNode = this._root;
                while(iterativeNode != null)
                {
                    stack.Push(iterativeNode);
                    iterativeNode = iterativeNode.Left;
                }
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    nodes.Add(iterativeNode.Element);
                    if(iterativeNode.Right != null)
                    {
                        stack.Push(iterativeNode.Right);
                        iterativeNode = iterativeNode.Right.Left;
                        while(iterativeNode != null)
                        {
                            stack.Push(iterativeNode);
                            iterativeNode = iterativeNode.Left;
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

訪問済みフラグのサンプルを次に示します。

public string InorderIterative_VisitedFlag()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                BinaryTreeNode iterativeNode = null;
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if(iterativeNode.visted)
                    {
                        iterativeNode.visted = false;
                        nodes.Add(iterativeNode.Element);
                    }
                    else
                    {
                        iterativeNode.visted = true;
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        stack.Push(iterativeNode);
                        if (iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

binarytreenode、listtostring ユーティリティの定義:

string ListToString(List<int> list)
        {
            string s = string.Join(", ", list);
            return s;
        }


class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;        
    }
于 2014-07-13T05:02:54.740 に答える
0

@Victor、状態をスタックにプッシュしようとしている実装についていくつかの提案があります。必要ないと思います。スタックから取得するすべての要素は、すでにトラバースされたままになっているためです。したがって、情報をスタックに格納する代わりに、必要なのは、処理される次のノードがそのスタックからのものであるかどうかを示すフラグだけです。以下は、正常に機能する私の実装です。

def intraverse(node):
    stack = []
    leftChecked = False
    while node != None:
        if not leftChecked and node.left != None:
            stack.append(node)
            node = node.left
        else:
            print node.data
            if node.right != None:
                node = node.right
                leftChecked = False
            elif len(stack)>0:
                node = stack.pop()
                leftChecked = True
            else:
                node = None
于 2011-07-31T02:25:41.153 に答える
0

これは役立つかもしれません (Java 実装)

public void inorderDisplay(Node root) {
    Node current = root;
    LinkedList<Node> stack = new LinkedList<>();
    while (true) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else if (!stack.isEmpty()) {
            current = stack.poll();
            System.out.print(current.data + " ");
            current = current.right;
        } else {
            break;
        }
    }
}
于 2015-11-23T23:14:53.490 に答える
0

@Emadpresによる回答の少し最適化

def in_order_search(node):
    stack = Stack()
    current = node

    while True:
        while current is not None:
            stack.push(current)
            current = current.l_child

        if stack.size() == 0:
            break

        current = stack.pop()
        print(current.data)
        current = current.r_child
于 2015-09-11T03:37:17.047 に答える
0

状態は暗黙のうちに覚えることができ、

traverse(node) {
   if(!node) return;
   push(stack, node);
   while (!empty(stack)) {
     /*Remember the left nodes in stack*/
     while (node->left) {
        push(stack, node->left);
        node = node->left;
      }

      /*Process the node*/
      printf("%d", node->data);

      /*Do the tail recursion*/
      if(node->right) {
         node = node->right
      } else {
         node = pop(stack); /*New Node will be from previous*/
      }
    }
 }
于 2010-03-01T03:40:21.937 に答える
-2

問題の一部は、「prev」変数の使用にあると思います。スタック (Lifo) 自体で状態を維持できるはずの前のノードを保存する必要はありません。

Wikipediaから、あなたが目指しているアルゴリズムは次のとおりです。

  1. ルートにアクセスします。
  2. 左のサブツリーをたどる
  3. 右のサブツリーをたどる

疑似コード (免責事項、私は Python を知らないので、以下の Python/C++ スタイルのコードについては申し訳ありません!) では、アルゴリズムは次のようになります。

lifo = Lifo();
lifo.push(rootNode);

while(!lifo.empty())
{
    node = lifo.pop();
    if(node is not None)
    {
        print node.value;
        if(node.right is not None)
        {
            lifo.push(node.right);
        }
        if(node.left is not None)
        {
            lifo.push(node.left);
        }
    }
}

ポストオーダー トラバーサルの場合は、左右のサブツリーをスタックにプッシュする順序を入れ替えるだけです。

于 2010-01-22T11:07:05.503 に答える