Итерационных Каскадный Binary Tree обходе только с постоянным дополнительным пространством

Question

Как пересекать резьбовых бинарное дерево не рекурсивно О (п) без использования стеки (только разрешено использовать постоянное дополнительное пространство для временных переменных, поэтому мы можем 't добавить флаг посещения для каждого узла в дереве). Я хорошо провел время, думая об этом, но мне кажется, что мне не кажется выполнимым , если только мы не будем перемещать места памяти, у которых есть данные дерева. Предположим, что мы используем множественное представление массива для реализации указателей, тогда мы можем пересечь дерево в O (n), имеет ли кто-нибудь что-то еще в виду?

Примечание Это не домашнего задания, чтобы сэкономить энергию некоторых штрихов клавиатуры писать комментарии о домашнем задании!

Answer 1

Давайте предположим, что мы имеем следующее резьбовое представление дерева в C:

typedef struct threaded_binary_tree { 
    int value; 

    // Flag that tells whether right points to a right child or to a next 
    // node in inorder. 
    bool right_is_child; 

    struct threaded_binary_tree *left, *right; 
} threaded_binary_tree; 

Затем, пересекая ее в O(1) памяти может выглядеть следующим образом:

void inorder(threaded_binary_tree *node) 
{ 
    threaded_binary_tree *prev = NULL; 

    // Ignore empty trees 
    if (node == NULL) 
     return; 

    // First, go to the leftmost leaf of the tree 
    while (node->left != NULL) 
     node = node->left; 

    while (node != NULL) { 
     // Nodes are visited along going upward in the tree 
     printf("%d\n", node->value); 

     prev = node; 
     node = node->right; 

     if (prev->right_is_child) { 
      // We're descending into tree 

      if (node != NULL) { 
       // Again, go to the leftmost leaf in this subtree 
       while (node->left != NULL) 
        node = node->left; 
      } 
     } 
     // else, we're climbing up in the tree 
    } 
} 

Предупреждения: Я не запускать этот код.

Answer 2

Это код, написанный на Java:

public void inOrder() { 
    Node<T> curr = root; 
    boolean visited = false; //I haven't come across the node from which I came 

    while (curr != null) { 
     if (!visited && curr.left != null) { //Go to leftmost node 
      curr = curr.left; 
     } else { 
      System.out.println(curr.head + " "); 
      if (curr.right != null) { //I prioritize having childs than "threaded sons" 
       curr = curr.right; 
       visited = false; 
      } else { 
       curr = curr.rightThreaded; 
       visited = true; //Means that I will come back to a node I've already looped, but now i'll print it, except if i'm at the last node 
      } 
     } 
    } 
} 

Узел представляет собой внутренний класс ThreadedBinaryTree:

private static class Node<T> { 
    private T head; 
    private Node<T> left; 
    private Node<T> right; 
    private Node<T> leftThreaded; 
    private Node<T> rightThreaded; 

    public Node(T head, Node<T> leftThreaded, Node<T> rightThreaded) { 
     this.head = head; 
     this.leftThreaded = leftThreaded; 
     this.rightThreaded = rightThreaded; 
    } 
}