查找二叉樹的根值？

我已存儲值的關係數組，這使得幾棵樹是這樣的：查找二叉樹的根值？

enter image description here

因此，在這種情況下，我的陣列將是（根，掛）

（ 8,3）（8,10）（3,1）（3,6）（6,4）（6,7）（10,14）（14,13）

，我想設置數組的主根在樹中的所有根值（在所有樹）：

（8,3）（8,1）（8,6）（8,4）（8,7）（8,10）（8,14）（8,13）

我應該調查哪些算法？

來源

2012-02-19 Gabriel A. Zorrilla

「主」根是從來沒有在右側出現的唯一價值。 – 2012-02-19 20:44:18

1）列出元組中所有唯一的第一個元素。

2）刪除任何也顯示爲元組的第二個元素的東西。

3）你會留下根（8在這裏）。用這個值替換所有元組的第一個元素。

編輯：

一個更復雜的方法，將多樹木的工作情況如下。

首先，轉換到父查找表：

1 -> 3 
3 -> 8 
4 -> 6 
6 -> 3 
7 -> 6 
10 -> 8 
13 -> 14 
14 -> 10

接下來，運行各元件上的「找到路徑壓縮父」：

1）

1 -> 3 -> 8

給出

1 -> 8 
3 -> 8 
4 -> 6 
...

3）

3 -> 8

4）

4 -> 6 -> 3 -> 8

給出

1 -> 8 
3 -> 8 
4 -> 8 
6 -> 8 
7 -> 6 
...

6）

6 -> 8 (already done)

7）

7 -> 6 -> 8

等

結果：

1 -> 8 
3 -> 8 
4 -> 8 
6 -> 8 
7 -> 8 
...

然後將此轉換回元組列表：

(8,1)(8,3)(8,4)...

與路徑壓縮算法發現父母是find_set將是不相交集森林，例如

int find_set(int x) const 
{ 
    Element& element = get_element(x); 
    int& parent = element.m_parent; 
    if(parent != x) 
    { 
     parent = find_set(parent); 
    } 
    return parent; 
}

關鍵是路徑壓縮可以幫助您避免大量工作。例如，在上面的例子中，當您查找4時，您將存儲6 -> 8，這使得後面的查找更快速地引用6。

來源

2012-02-19 20:45:34

他可以使用BFS來創建列表嗎？ – Bytemain 2012-02-19 21:12:36

@使用BFS的大衛意味着你必須準備一些圖結構，在這種情況下，這將是一種矯枉過正。這裏唯一需要的是一個包含某種contains的集合（） – soulcheck 2012-02-19 22:37:18

簡單的方法是使用類似於std :: set（用C++）的東西，或者你的語言的等價物。 – 2012-02-19 23:10:09

所以假設你有代表點元組的列表：

def find_root(ls): 
    child, parent, root = [], [], [] 
    for node in ls: 
    parent.append(node[0]) 
    child.append(node[1]) 

    for dis in parent: 
    if (!child.count(dis)): 
     root.append(dis) 

    if len(root) > 1 : return -1 # failure, the tree is not formed well 

    for nodeIndex in xrange(len(ls)): 
    ls[nodeIndex] = (root[0], ls[nodeIndex][1]) 

    return ls

來源

2012-02-20 07:58:35 Noxville

查找二叉樹的根值？

回答

相關問題