需要關於C樹的一些解釋

Question

Leaf *findLeaf(Leaf *R,int data) 
{ 
    if(R->data >= data) 
    { 
    if(R->left == NULL) return R; 
    else return findLeaf(R->left,data); 
    } 
    else 
    { 
    if(R->right == NULL) return R; 
    else return findLeaf(R->right,data); 
    } 
} 


void traverse(Leaf *R) 
{ 
if(R==root){printf("ROOT is %d\n",R->data);} 
if(R->left != NULL) 
{ 
    printf("Left data %d\n",R->left->data); 
    traverse(R->left); 
} 
if(R->right != NULL) 
{ 
    printf("Right data %d\n",R->right->data); 
    traverse(R->right); 
} 
} 

這些代碼片段工作正常，但我不知道它們是如何工作的？ 我需要一個關於遞歸的簡單解釋。我很感謝你的幫助。

Answer 1

一個Leaf結構將是這個樣子：

typedef struct struct_t { 
    int data; 
    Leaf * left; //These allow structs to be chained together where each node 
    Leaf * right; //has two pointers to two more nodes, causing exponential 
} Leaf;   //growth. 

該函數接受一個指向我們稱之爲R葉和一些數據進行搜索對，它返回一個指向葉

Leaf *findLeaf(Leaf *R,int data){ 

這段代碼決定我們應該向左還是向右，因爲插入函數遵循相同的左右規則，因此已知樹被排序。

if(R->data >= data){ 

這是函數的遞歸性的優勢情況下，如果我們已經達到樹中的最後一個節點，稱爲葉，返回葉。

遞歸函數的邊緣情況具有結束遞歸併返回結果的任務。沒有這個，該功能將無法完成。

if(R->left == NULL) return R; 

這是我們如何穿過樹，在這裏，我們正在遍歷左側，因爲數據較大。 （更大的數據總是插在左側以保持排序。） 發生了什麼事情是，現在我們調用findLeaf（）與R->left，但想象一下，如果我們在下次調用中再次獲得此點。

它會變成R->left->left參照第一個電話。如果數據比我們正在操作的當前節點更小，那麼我們會選擇正確的。

else return findLeaf(R->left,data); 

現在我們在那裏的數據是比當前節點小的情況下，所以我們要正確。

} else { 

這和左邊是完全一樣的。

 if(R->right == NULL) return R; 
    else return findLeaf(R->right,data); 
    } 
} 

最後，函數的返回可以概念化爲類似R->right->right->left->NULL的東西。

讓我們拿這棵樹並用findLeaf（）對它進行操作;

findLeaf(Leaf * root, 4) //In this example, root is already pointing to (8)

我們從根開始，在樹，其中包含8

首先的頂部，我們檢查R->data >= data我們知道R->data是(8)和data是(4)。由於我們知道data小於R->data（當前節點），因此我們輸入if語句。

這裏我們對左邊的Leaf進行操作，檢查它是否爲NULL。這不是，所以我們跳到else。

現在我們返回findLeaf(R->left, data);，但要返回它，我們必須先解決它。這導致我們進入第二次迭代，我們將(3)與(4)進行比較，然後重試。

再次審查整個過程，我們會比較(6) to (4)，然後最終找到我們的節點，當我們comepare (4) to (4)。現在，我們將回溯通過函數並返回一個鏈條是這樣的：

R(8)->(3)->(6)->(4)

編輯：另外，巧合的是，我寫了一篇博客文章遍歷鏈表來解釋二叉搜索樹here的性質。

Answer 2

一些關於遞歸和評論，然後關於搜索在樹上一個小注釋：

讓我們假設你想計算出n！你可以這樣做（僞）

fac 0  = 1 
fac (n+1) = (n+1) * fac n 

所以遞推通過操縱一個較小的數據解決同一問題的結果，解決問題。請參閱http://en.wikipedia.org/wiki/Recursion。

所以，現在，讓我們假設我們有一個數據結構樹

T = (L, e, R) 

以L左子樹，e是根，R是右子樹......所以我們說你要查找的值v IN那棵樹，你會做

find v LEAF  = false // you cant find any value in an empty tree, base case 
find v (L, e, R) = 

if v == e 
    then something(e) 
else 
    if v < e 
    find v L (here we have recursion, we say 'go and search for v in the left subtree) 
    else 
    find v R (here we have recursion, we say 'go and search for v in the right subtree) 
    end 
end 

Answer 3

遞歸是一種向下突破的問題到2種變體功能：

的

1. 一步解決問題，並與問題
2. 解決問題

遞歸的最後一步的剩餘自稱是簡單地通過代碼循環的方式不同。

Answer 4

遞歸算法通常與某種形式的數據結構一起工作 - 在您的案例樹中。你需要想象遞歸 - 非常高的層次 - 就是「在問題的一個子集上重新應用相同的邏輯」。

在你的情況下，問題的子集是右邊三個分支或左邊三個分支。

那麼，讓我們來看看在遍歷算法：

這需要你傳遞給該方法的葉 - 如果它的根葉指出它 然後，如果有一個「左」分葉其顯示器附加到它的數據並重新啓動算法（遞歸），這意味着...在左節點上 如果左節點是ROOT，則表明它（在ROOT位於頂部後的第一次遞歸後沒有機會） 然後，如果我們的左節點上有一個「左」子葉片，則顯示它並重新啓動左邊的算法，左邊

當到達左下角時，即當沒有左邊的葉子（跟隨？ :)），然後它在第一個右邊的葉子上也是這樣。如果既沒有左葉也沒有右葉，這意味着我們在沒有子葉的真葉中，遞歸調用結束，這意味着算法從遞歸之前的地方再次開始變量處於他們所在的狀態。

第一次遞歸終止之後，您將從左下角的葉子上移一片葉子，並在右葉子上下移（如果有），然後再次開始打印並在左側移動。

總而言之 - 最終的結果是，你以左第一種方式穿過整棵樹。

告訴我，如果它不是很清晰，並嘗試在findLeaf遞歸算法上應用相同的模式。

Answer 5

每個葉包含三個值：

• data - 的整數
• left和right，兩個指針到另一個葉。

left，right或兩者都可能爲NULL，這意味着在該方向上沒有另一葉。

這是一棵樹。根目錄中有一個Leaf，您可以按照left或right指針的軌跡行進，直到達到NULL。

以遞歸的關鍵是，如果你通過一個葉遵循的路徑，剩下的問題是完全相同（但「一小」），當你在根你有問題。所以你可以調用相同的函數來解決這個問題。最終，例程將在一個以NULL爲指針的Leaf上，並且你已經解決了這個問題。

在理解樹之前理解列表可能是最容易理解的。因此，代替具有兩個指針的葉，left和right，您只有一個指針的節點，next。以遞歸方式跟隨列表到最後：

Node findEnd(Node node) { 
    if(node->next == NULL) { 
     return node; // Solved!! 
    } else { 
     return findEnd(node->next); 
    } 
} 

你的findLeaf有什麼不同？那麼，它使用data參數來決定是否遵循left或right指針，但其他情況完全相同。

你應該能夠理解traverse()這個知識。它使用遞歸的原理來訪問結構中的每個葉。