「攀登」二叉樹

有沒有辦法直接爬樹而不去拜訪其他分支？例如，如果我有11號，我必須訪問它去2到5，而不是11沒有任何搜索。「攀登」二叉樹

        0 
          /  \ 
         /   \ 
         /   \ 
         1    2 
        / \   / \ 
        / \  / \ 
        3  4  5  6 
       /\ /\ /\ /\ 
       / \ / \ / \ / \ 
       7  8 9 10 11 12 13 14

我已經殺了很多的時間我現在唯一的事情是，拿到第一道（1或2）數目爲N，你必須（N-1）/ 2，直到n等於（2-1）/ 2 =>（5-1）/ 2 => 2.（7-1）/ 2 =>（3-1）/ 2 => 1.（（1-2） 11-1）/ 10 =>（2-1）/ 2 => 1. 但端那麼這將是正確切割根（0）和處理2像一個新的：

  2 
     /\ 
     / \ 
    / \ 
    5  6 
    /\ /\ 
/ \ / \ 
    11 12 13 14 

     to 

      0 
     /\ 
     / \ 
    / \ 
    1  2 
    /\ /\ 
/ \ / \ 
    3  4 5  6

解：

int climb(int ID, Tree<int> t) 
{ 

    int time = 0; 
    if (tree.exists()) { 
     time += t.value(); 
     tree t1, t2; 
     t.branches(t1, t2); 
     int branch = ID; 
     while (branch > 2) branch = (branch - 1)/2; 
     int offset = 1; 
     while (offset*2 < ID - 1) offset *= 2; 
     if (aux == 1) time += climb(ID - offset2/, a1); 
     if (aux == 2) time += climb(ID - offset, a2); 
    } 
    return time; 
}

您可以訪問完整二叉樹的ANY（1，5，13等）元素。

來源

2011-11-06 user1021852

我認爲你正在尋找的字是 '橫'，而不是「爬」。此外，遞歸是解決方案的通常本質。 – sehe

通常遍歷搜索槽直到找到，我知道如何做到這一點，但我建議「爬山」只訪問那些正在路上的樹。 – user1021852

這取決於，你的樹是一棵完美的二叉樹（所有樹葉都在同一深度，每個父母都有兩個孩子）？節點的值是否與示例中一樣？如果兩個問題的答案都是肯定的，那麼你可以做你想做的事。如果不是，那麼你不能。 – pnezis

如果您想跳過使用哈希容器（例如std::map或std::set）和哈希搜索之間的所有節點。二叉樹意味着遞歸遍歷。請注意，set不是關聯的，因此您必須稍微處理一下。

如果你努力向樹/樹節點添加自定義的代碼/成員變量，你最終可能會遇到一個內存沉重的樹impl（David的回答是一個非常明亮的例子）。

- 編輯 -

如果你的ID始終序列沒有太多窟窿（如0, 1, 2,..., 50 OR 68, 69,...,230,231）我建議普通的老陣！讓我知道你是否想知道更多。

一般來說，我的消息是先挑選合適的容器/結構，然後只在需要時對結構本身進行「微小」修改。

來源

2011-11-06 16:21:49 Kashyap

我不確定，我仍然是一個新手。我覺得我不是很清楚。 0 1 2 ... 2N-2只是參考，它們不存儲在樹內。這是關於存儲更少。 – user1021852

@ user1021852 ??哪部分你不確定？ – Kashyap

地圖，設置和其他。我正在閱讀關於它...... – user1021852

我假設你有一個完美的二叉樹（所有樹葉都在同一深度，每個父親有兩個孩子），所有節點的值就像你提供的例子。

在這種情況下，注意以下幾點：

節點n具有作爲孩子的節點與值2 * N + 1，2 * N + 2

如果你想去如果要訪問具有偶數值K的節點，其父節點爲節點（K-2）/ 2

從節點0開始重複相同的過程，並且擁有所有必須訪問的節點。

因此，對於你的榜樣，你要訪問的節點11

11 is odd so its parent is (11-1)/2 = 5 
5 is odd so its parent is (5-1)/2 = 2 
2 is even so its parent is (2-2)/0 = 0 

we have reached the root node, so you have to follow the path 0->2->5->11

來源

2011-11-06 16:22:45 pnezis

您認爲密鑰始終是完整的序列。在那種情況下，我建議一個普通的舊數組應該是最好的/最快的。 – Kashyap

我已經做到了這一點，我使用整數除法，所以我不在乎它是否奇怪。但thx任何方式。 – user1021852

@thekashyap完全同意集裝箱。 – pnezis

我想「爬」到任何分支或葉，而無需訪問不在的方式（分支，如果我爬到「4 '然後我直接去0 - > 2 - > 4）。只有我錯過的路徑被抵消，將「變形」分支到樹上（參見問題）。

我收到抵消這樣的：

int offset = 1; 
while (offset*2 < ID - 1) offset *= 2;

它適用於分支 '2' 和偏移/ 2將分支工作的 '1'。

int climb(int ID, Tree<int> t) 
{ 

    int time = 0; 
    if (tree.exists()) { 
     time += t.value(); 
     tree t1, t2; 
     t.branches(t1, t2); 
     int branch = ID; 
     while (branch > 2) branch = (branch - 1)/2; 
     int offset = 1; 
     while (offset*2 < ID - 1) offset *= 2; 
     if (aux == 1) time += climb(ID - offset2/, a1); 
     if (aux == 2) time += climb(ID - offset, a2); 
    } 
    return time; 
}

來源

2011-11-07 08:59:44 user1021852

另一種方法是做一個堆棧：

void solve(int n) 
{ 
    stack<direction> path; 
//Calculate the way 
    while (n > 0) 
    { 
    if (n & 1) // if n is odd; 
     path.push_back(left); 
    else 
     path.push_back(right); 

    n = (n - 1)/2; 
    } 

    //Do actual "climbing" 

    while (!path.empty()) 
    { 
    if (path.top() == left) 
    { 
     go left 
    } 
    else 
    { 
     go right 
    } 

    path.pop(); 
    } 
}

THX到Raving_Zealot從linux.org.ru

來源

2011-11-07 09:12:44 user1021852

「攀登」二叉樹

回答

相關問題