Use destructive inorder traversal by right rotations. A right tree rotation preserves inorder traversal but moves the first unvisited node closer to the root:
PROCEDURE InorderDestructive(t: Tree; p: Visit);
VAR q: Tree;
BEGIN
  WHILE t # NIL DO
    WHILE t.left # NIL DO
      q := t.left;
      t.left := q.right;
      q.right := t;
      t := q
    END;
    p(t.label);
    t := t.right
  END
END InorderDestructive;
The outer loop invariant states that the labels already passed to p, followed by the inorder traversal of t, equal the original inorder traversal. The remaining nodes form a binary tree disjoint from the nodes already visited. The inner loop invariant preserves the remaining inorder traversal: if the old root is , its left child is , and the three unchanged subtrees are , then both shapes have order .
Figure 1.
A right tree rotation preserves inorder traversal and exposes the next node
. Details.
At inner-loop exit, t.left = NIL, so the root is the first remaining node. Visiting it and replacing t by t.right preserves the outer loop invariant. The procedure changes child pointers and makes the old root reference unusable as the original binary tree. Assume p neither changes the binary tree nor depends on its old shape.
(1)

Ancestors (12)

  1. f
  2. 1
  3. Imperative programming (resit)
  4. 2015
  5. Past exam of the year 1 of the computer science course of the University of Oxford
  6. Year 1 of the computer science course of the University of Oxford
  7. Computer science course of the University of Oxford
  8. Undergraduate course of the University of Oxford
  9. Course of the University of Oxford
  10. University of Oxford
  11. List of universities
  12. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version