17

フラグや？nullを使用せずに、ノードに親ポインター（ルートの親は）を持つBSTで反復的な順序トラバーサルを実行することは可能ですか？visitedstack

グーグルで返信が見つかりませんでした。重要なのは、特定のノードで、私がちょうどそこに来たのか、その下のすべてを終えたのかをどうやって知ることができるのかということです。

4

8 に答える 8

18

これを行うことができます。最後にアクセスしたノードと現在のノードを覚えておく必要があります。これを行うことは、問題ステートメントによって禁止されていません。visited各ノードのフラグとaのstack両方が（最悪の場合）O（n ）であり、最後のノードがO （1）であることを思い出してください。

C＃では、アルゴリズムは次のようになります。

static void Walk(Node node)
{
    Node lastNode = null;
    while (node != null)
    {
        if (lastNode == node.Parent)
        {
            if (node.Left != null)
            {
                lastNode = node;
                node = node.Left;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Left)
        {
            Output(node);

            if (node.Right != null)
            {
                lastNode = node;
                node = node.Right;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Right)
        {
            lastNode = node;
            node = node.Parent;
        }
    }
}
于 2012-04-29T12:27:16.030 に答える
14

これを行う別の方法があります。私はそれが本質的にsvickの答えと同等であると思いますが、余分な変数を避けます。このバージョンはPythonで実装されています：

node=root
if node is not None:
  while node.left is not None:
    node=node.left
  while node is not None:
    output(node)
    if node.right is not None:
      node=node.right
      while node.left is not None:
        node=node.left
    else:
      while node.parent is not None and node.parent.right is node:
        node=node.parent
      node=node.parent

最後にアクセスしたノードによって、次にアクセスする必要のあるノードが決まります。ノードXにアクセスしたばかりの場合は、Xの右側にある左端のノードにアクセスする必要があります。Xに右の子がない場合、次のノードは、ノードXが右から来なかった最初の祖先です。側。

于 2012-04-29T15:58:30.923 に答える
6

svickの正しい考え（彼の答えを参照）を使用して、これはC++でテストされたコードです。私は彼のコードをテストしたり、それを見たりしなかったことに注意してください。私は彼のアイデアを取り入れて、自分の関数を実装しただけです。

void in_order_traversal_iterative_with_parent(node* root) {
node* current = root;
node* previous = NULL;

while (current) {
    if (previous == current->parent) { // Traversing down the tree.
        previous = current;
        if (current->left) {
            current = current->left;
        } else {
            cout << ' ' << current->data;
            if (current->right)
                current = current->right;
            else
                current = current->parent;
        }
    } else if (previous == current->left) { // Traversing up the tree from the left.
        previous = current;
        cout << ' ' << current->data;
        if (current->right)
            current = current->right;
        else
            current = current->parent;
    } else if (previous == current->right) { // Traversing up the tree from the right.
        previous = current;
        current = current->parent;
    }
}

cout << endl;
}
于 2012-04-30T08:07:07.017 に答える
0 
public void inorderNoStack() {
    if (root == null) {
        return;
    }

    // use the previous to always track the last visited node
    // helps in deciding if we are going down/up
    Node prev = null;

    Node curr = root;

    while (curr != null) {
        // going down
        if (prev == null || prev.left == curr || prev.right == curr) {
            if (curr.left != null) {
                prev = curr;
                curr = curr.left;
                continue;
            } else {

                visitn(curr);

                if (curr.right != null) {
                    prev = curr;
                    curr = curr.right;
                    continue;
                } else {
                    // swap states
                    prev = curr;
                    curr = prev.parent;
                }
            }
        }

        // going up after left traversal
        if (curr != null && prev == curr.left) {

            visitn(curr);

            if (curr.right != null) {
                prev = curr;
                curr = curr.right;
                continue;
            } else {
                // swap states
                prev = curr;
                curr = prev.parent;
            }
        }

        // going up after right traversal
        if (curr != null && prev == curr.right) {
            // swap states
            prev = curr;
            curr = prev.parent;
        }
    }
}
于 2013-03-26T06:19:02.387 に答える
0

既存のTREEにフラグを導入しない私のJavaソリューション。また、親ポインタもありません。このアプローチでは、ノードをツリーの高さまで保持します。ご覧ください。

https://github.com/skanagavelu/Algorithams/blob/master/src/tree/InOrderTraversalIterative.java

于 2015-11-16T05:40:38.627 に答える
0

ステップ1：インオーダーサクセサを返す関数を記述します

ステップ2：左端のノードから始めて、次のノードがなくなるまで順番に後継ノードを見つけます

    public class TreeNode {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode parent;
    }

    public class TreeUtility {
      public void inorderNoRecursion(TreeNode root) {
        TreeNode current = leftmostNode(root);
        while(current != null) {
          System.out.println(current.data);
          current = inorderSuccessor(current);
        }
      }

      public TreeNode inorderSuccessor(TreeNode node) {
        if (node.right!=null) {
          return leftmostNode(node.right);
        }

        TreeNode p = node.parent;
        TreeNode c = node;
        while(p!=null && c != p.left) {
          c = p;
          p = p.parent;
        }
        return p;
      }

      private TreeNode leftmostNode(TreeNode node) {
        while (node.left != null) {
          node = node.left;
        }
        return node;
      }
    }
于 2016-02-06T04:44:42.340 に答える
-1

重要なのは親ポインター（またはツリーを変更する機能）ですが、一定量の追加の状態（たとえば、次のコルーチンのプログラムカウンター）が必要です。

  1. vをルートに設定します。
  2. vには左の子がありますが、vをその左の子に設定します。
  3. 収量v。
  4. vがルートの場合、戻ります。
  5. pをvの親に設定します。
  6. pの右の子がvの場合、vをpに設定し、ステップ4に進みます。
  7. 収量p。
  8. pに正しい子がある場合は、vをpの正しい子に設定して、手順2に進みます。
  9. vをpに設定し、ステップ4に進みます。
于 2012-04-29T12:35:31.803 に答える
-2

これはC++です：

void InOrder(Node *r)
{
   if(r==NULL)
         return;

   Node *t=r;

   while(t!=NULL)
       t=t->left;

  while(t!=r)
  {
     if(t==(t->parent->left))
     {
        cout<<t->parent->data;
        t=t->parent->right;
       if(t!=NULL)
      {
       while(t!=NULL)
          t=t->left;
      } 
      if(t==NULL)
          t=t->parent;
     }
     if(t==t->parent->right)
     {
        t=t->parent;
     }
  }
}
于 2012-08-14T22:18:48.480 に答える