2013-03-02 67 views
1

我的問題是如何在二叉樹上執行級別遍歷?我知道你會使用一個隊列,但我怎麼會遞歸呢?總之我想打印樹的層次順序的內容如下:僅使用que和遞歸進行級別遍歷的算法

 3 
    /\ 
    2 1 
/\ \ 
4 6 10 

將打印:3 2 1 4 6 10

我已經試了無數次失敗嘗試哪些段錯誤和感到沮喪並將其刪除。我試圖做這個使用NO循環,只有遞歸。循環它不壞,但我最近開始學習遞歸,並希望僅使用遞歸完成此方法。當你無法正常工作時,它非常令人沮喪。謝謝你的幫助。

+0

這似乎很清楚,遞歸不是一個很好的匹配這個問題。 – NPE 2013-03-02 07:31:49

+0

@NPE遞歸對於這個問題是完全可選的。你可以用它或不用它來做,但是子隊列是關鍵的。該算法是純尾遞歸,因此可以很容易地完成它,但也可以使用它。 – WhozCraig 2013-03-02 07:46:08

+0

如果您向我們展示了迄今爲止您嘗試的代碼的示例,它將會非常有用。 – Kev 2013-03-02 23:06:08

回答

1

我建議是這樣的:

struct node { 
    int isRoot; 
    int val; 
    struct node * left; 
    struct node * right; 
}; 

int printTree(node *root, int level){ 
    int a = 0,b = 0; 
    if(level > 0){ 
     if(root->left != NULL){ 
      a = printTree(root->left, level-1); 
     }else{ a = 1; } 
     if(root->right !=NULL){ 
      b = printTree(root->right, level-1); 
     }else{ b = 1: } 
    }else{ 
     printf("%i", root->val); 
     return 0; 
    } 
    if(isRoot && !(a && b)){ 
     printTree(root, level+1); 
    } 
    return a&&b; 
} 

int main(void){ 
    //get your tree somehow and put the root into 
    //node *head with only the root node having isRoot as true; 
    printTree(head, 0); 
} 

順便說一句,我不知道這隻會編譯,所以認爲這是僞僞代碼。

編輯:更新的代碼不被如此推遲。它通過級別,第一級0(root),然後級別1(root->left,root->right)等等。 ab標誌表示什麼時候修剪樹(NULL節點)。

+0

這是深度優先遍歷 – perreal 2013-03-02 07:19:04

+0

你是對的 – dudeofea 2013-03-02 07:20:21

+1

也,我的解決方案不使用隊列;因爲我討厭他們。 – dudeofea 2013-03-02 08:09:02

2

僞代碼:

Traverse (queue, t): 
    visit t 
    For each child c of t: 
     put c to queue 
    Traverse (queue, pop queue) 
0

你並不需要做遞歸,這將是慢!

看看在JavaScript中使用隊列的簡單示例!

function leverOrder(root) { 
    // Node struct -> { value, left, right } 

    if(!root) return; 

    var q = [ root ]; 

    while(q.length) { 
     var current = q.shift(); 

     // do stuff with value 
     console.log(current.value); 

     if(current.left) q.push(current.left); 
     if(current.right) q.push(current.right); 
    } 

}