反復スレッドバイナリツリーは単なる一時変数のための一定の余分なスペースを使用することができ、私たちはできる（スタックを使用せずに<em>スレッドバイナリツリー</em>非再帰的<em>O（n）の</em>中を横断する方法だけで一定の余分なスペースと

Question

のトラバースツリーの各ノードに訪問フラグを追加しないでください）。私はそれについて考えて楽しい時間を過ごしましたが、のように私には見えません。木のデータを持つメモリの場所を横切る場合を除きます。私たちがポインタを実装するために複数の配列表現を使用しているとしたら、O（n）でツリーをたどることができます。

注これはちょうど宿題についてのコメントを書くために、いくつかのキーボードストロークのエネルギーを節約するために、ない宿題です！

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

警告：私は実行していない。このように見えるかもしれO(1)メモリにそれを通過、その後

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; 

：

Answer 1

のは、私たちはCで、次のねじ切りツリー表現を持っているとしましょうこのコード。

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