0

非再帰的なポストオーダー バイナリ ツリー トラバーサルのこの疑似コードっぽいアルゴリズムを使用して、実際にコードに実装することを想定しています。基本的に、ノードへの参照を保存するためのスタックと、整数値 1 または 2 を保存するための 2 つの並列スタックを作成して、左または右のサブツリーにアクセスしたかどうかを確認します。私は彼らが私にくれたものに基づいてアルゴリズムを作成しましたが、何らかの理由で数字の一部のみを印刷し、正しい順序ではありません.

彼らが私にやりたいことは次のとおりです。

1.create stack(s)
2. current = root;
3.v = 0;
4. if (current is null)
    the binary tree is empty
5. if (current is not null)
    a. push current onto stack;
    b. push 1 onto stack;
    c. current = current.lLink;
6. while (stack is not empty)
      if (current is not null and v is 0)
      {
          push current and 1 onto stack;
          current = current.lLink
      }
      else
      {
          pop stack into current and v;
          if ( v == 1)
          {
              push current and 2 onto stack;
              current = current.rLink;
              v = 0;
          }
          else
              visit current;
      }

そして、これが私の実装です:

public void nonRecursivePostTraversal()
{
    LinkedStackClass<BinaryTreeNode<T> > stack
    = new LinkedStackClass<BinaryTreeNode<T> >();//create stack

    //create parallel stack of integers
    LinkedStackClass<Integer> stackInt = new LinkedStackClass<Integer>();

    BinaryTreeNode<T> current;
    current = root;

    Integer v = 0;

    if (current == null)
        stack = null;

    if   (current != null)
    {
        stack.push(current);
        v = 1;
        stackInt.push(v);
        current = current.lLink;
    }


    while (!stack.isEmptyStack())
        if (current != null && v == 0)
        {
            stack.push(current);
            v = 1;
            stackInt.push(v);
            current = current.lLink;

        }
        else
        {
            current = (BinaryTreeNode<T>) stack.peek();
            stack.pop();
            v = (Integer) stackInt.peek();
            stackInt.pop();
            if (v == 1)
            {
                stack.push(current);
                v = 2;
                stackInt.push(v);
                current = current.rLink;
                v = 0;
            }
            else
                System.out.print(current.info + " ");
        }

}//end alg
4

1 に答える 1