Jak zrobić przejście w kolejności BST bez rekurencji lub stosu, ale za pomocą wskaźników nadrzędnych?

Oto inny sposób, aby to zrobić. Myślę, że jest to zasadniczo odpowiednik odpowiedzi svicka, ale unika dodatkowej zmiennej. Ta wersja jest zaimplementowana w Pythonie:

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

Niezależnie od węzła, który ostatnio odwiedziłeś, określa następny węzeł, który musisz odwiedzić. Jeśli właśnie odwiedziłeś węzeł X, musisz odwiedzić najbardziej lewy węzeł po prawej stronie X. Jeśli X nie ma prawego potomka, następnym węzłem jest pierwszy przodek, gdzie węzeł X nie pochodził z prawej strony.

Używając poprawnego pomysłu svick (Zobacz jego odpowiedź ), jest to przetestowany kod W C++. Zauważ, że nie testowałem jego kodu, ani nawet na niego nie spojrzałem, po prostu wziąłem jego pomysł i zaimplementowałem własną funkcję.

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;
}

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;
        }
    }
}

Moje rozwiÄ ... zanie Java bez wprowadzania znacznikăłw na istniejÄ ... cym drzewie. I nie ma też wskaźnika rodzica. Takie podejście utrzyma węzły do wysokości drzewa. Proszę spojrzeć.

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

Krok 1: napisz funkcję, która zwraca następcę w kolejności

Krok 2: zaczynając od lewego węzła, znajdź następcę w kolejności, dopóki nie ma żadnego

    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;
      }
    }

Kluczem jest wskaźnik nadrzędny( lub zdolność do mutacji drzewa), ale potrzebujesz stałej ilości dodatkowego stanu(np. licznik programu następującego coroutine).

1. Ustaw v na root.
2. Gdy v ma lewe dziecko, Ustaw v na lewe dziecko.
3. Yield V.
4. Jeśli v jest korzeniem, to return.
5. Ustaw P na rodzica V.
6. Jeśli prawym potomkiem p jest v, Ustaw v na p i przejdź do kroku 4.
7. Yield p.
8. Jeśli p ma właściwe dziecko, to ustaw v do prawego dziecka p i przejdź do kroku 2.
9. Ustaw v na p i przejdź do kroku 4.

To jest w 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;
     }
  }
}