バイナリツリーの同じレベルでノードを接続する

Question

同じレベルにあるバイナリツリーのノードをどのように接続するかについての記事やページがありますが、これらの記事のどれもプロセス/アルゴリズムをはっきりと説明していません。誰かがこれを受け入れることができたら、私は感謝します。コードは必要ではありませんが、疑似コードで説明するといいでしょう。議論の便宜上

、私たちのようにツリーを考えてみましょう：上記の場合

   0 
      1  2 
     3  4 5 6 
    7      9 

：

0 should point to null. 
1 should point to 2. 
3 should point to 4. 
.... 
7 should point to 9. 
9 should point to NULL. 

基本的なツリー構造は、次のとおりです。

class Tree { 
    public: 
    int data; 
    Tree* left; 
    Tree* right; 
    Tree* next; 
} 

Answer 1

誘導性の一種である余分なメモリ、使用していない興味深いアプローチがあります：最初のレベルがすでに接続されている

1. は（それが一つのノードのみを持っている）

2. のレベルを言ってみましょうiが接続されています。そして、次の操作を実行レベルi+1を接続するには：

   a）をnull

   Bにノードlst（私たちは、後に使用するだけで、中間変数）を初期化する）レベルi上の最初のノードで起動します。

   c）最初のノードからレベルiのノードを走査します。ノードがすでに接続されているため、レベルがiのノードを簡単に通過できるため、各ノードに兄弟ポインタがあります。

   d）各ノードのレベルiは、左の子を最初に、次に右の子を調べます。ヌルでない各子について、lstがnullでない場合は、その子にlstを接続します。次に、その子にlstを設定します。

レベルi + 1を接続したら、次のレベルに進むことができます。レベルlstがまだヌルである場合は、このレベルのノードには子=>これが最後のレベルではなかったことを意味します。アルゴリズムを停止できます。

これがなぜ機能するかは簡単にわかります。線形時間と一定の空間が必要なので、リニアメモリを使用するキューを持つBFSよりも厳密に優れています。

Answer 2

使用BFS示唆したようにコメントの中で。 次に、ルートから各ノードの距離を取得します。

擬似コード：

vis[1..n] = false // mark each node as un-visited 
dis[1..n] = 0 
Queue q 
dis[root] = 0 
vis[root] = true 
q.push(root) 
while !q.empty() 
    node x = q.front() 
    children[] = children nodes of node x 
    for each child in children 
      !vis[child] 
      dis[child] = dis[x] + 1 
      vis[child] =true 
      q.enqueue(child) 
    q.pop() 

今、あなたは、ルートから各ノードの距離を持っていた距離に基づいて、各ノードを集約し、あなたの要件に応じてノードに参加することができます。

Answer 3

Ishamaelのアイデアに続いて、私はあなたが[幅優先探索]を使用して、ツリーlevelwiseを横切ることができる

void link_levels(Tree* t){ 
    Tree *head, *tail, *end_of_row; 
    assert (t != 0); 
    t->next = 0; 
    head = tail = end_of_row = t; 
    while(head != 0){ 
     if(head->left != 0){ 
      tail->next = head->left; 
      tail = tail->next; 
      tail->next = 0; 
     } 
     if(head->right != 0){ 
      tail->next = head->right; 
      tail = tail->next; 
      tail->next = 0; 
     } 
     if(head == end_of_row){ 
      head = head->next; 
      end_of_row->next = 0; 
      end_of_row = tail; 
     } 
     else { 
      head = head->next; 
     } 
    } 
}