在二叉樹的同一級別連接節點

我已經看到一些關於如何連接二級樹的節點的文章/頁面，它們處於同一級別，但沒有一篇文章清楚地解釋過程/算法。如果有人能夠接受這一點，我將不勝感激。代碼不是必需的，但用僞代碼解釋會很好。在二叉樹的同一級別連接節點

爲了便於討論，讓我們考慮樹：

在上述情況下：

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

來源

2017-01-17 Hemant Bhargava

行的程序可以使用[廣度優先搜索]遍歷樹levelwise（https://en.wikipedia.org/wiki/廣度優先搜索）算法，並在每個級別上臨時存儲前一個節點。然後''前一個節點'的'next'將是'當前解析'節點。 – sameerkn

是的，使用在圖層中遍歷的bfs或寬度優先搜索，所以基本上，您將在與根相同的距離處具有處於相同級別的節點。 –

@sameerkn，我明白這一點。你介意寫一些僞代碼嗎？ –

有不使用額外的內存，一個有趣的方法是那種感性的：

第一級已經連接（它只有一個節點）
假設水平連接了i。然後連接i+1水平做到以下幾點：

一）初始化節點lst（只是稍後我們將使用一箇中間變量）null

二）在上i級別的第一個節點開始。

c）遍歷從第一個節點開始的級別i的節點。請注意，您可以輕鬆遍歷i級別的節點，因爲它已連接，因此您在每個節點中都有兄弟指針。

d）對於級別爲i的每個節點，首先查看其左側的孩子，然後查看其右側的孩子。對於非空的每個孩子，如果lst不是null，則將lst連接到該孩子。然後將lst設置爲該孩子。

一旦你連接水平i + 1，你可以移動到下一個級別。如果在遍歷lst級別後仍然爲空，則表示此級別上沒有節點有孩子=>這是最後一級，則可以停止算法。

這很容易證明它爲什麼起作用，它需要線性時間和恆定的空間，所以它比帶隊列的BFS（需要線性內存）嚴格得多。

來源

2017-01-17 07:41:53 Ishamael

這種變體就是簡單地使用節點本身作爲隊列項目他們下一個指針。我們只需要保留一個指向下一行的指針，因爲在處理當前行的結尾時，隊列的尾部指向下一行的結尾。 – Gribouillis

使用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()

現在你將有每個節點距離根，合計基於距離的每個節點，並可以加入節點按您的要求。

來源

2017-01-17 07:26:49

節點可以在同一個循環中鏈接在一起，因爲它們將按順序出現在隊列中。0 1 2 3 4 5 6 7 9. – Gribouillis

繼Ishamael的想法，我建議沿着

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

來源

2017-01-17 08:35:27 Gribouillis

在二叉樹的同一級別連接節點

回答

相關問題