我的問題是如何在二叉樹上執行級別遍歷?我知道你會使用一個隊列,但我怎麼會遞歸呢?總之我想打印樹的層次順序的內容如下:僅使用que和遞歸進行級別遍歷的算法
3
/\
2 1
/\ \
4 6 10
將打印:3 2 1 4 6 10
我已經試了無數次失敗嘗試哪些段錯誤和感到沮喪並將其刪除。我試圖做這個使用NO循環,只有遞歸。循環它不壞,但我最近開始學習遞歸,並希望僅使用遞歸完成此方法。當你無法正常工作時,它非常令人沮喪。謝謝你的幫助。
我的問題是如何在二叉樹上執行級別遍歷?我知道你會使用一個隊列,但我怎麼會遞歸呢?總之我想打印樹的層次順序的內容如下:僅使用que和遞歸進行級別遍歷的算法
3
/\
2 1
/\ \
4 6 10
將打印:3 2 1 4 6 10
我已經試了無數次失敗嘗試哪些段錯誤和感到沮喪並將其刪除。我試圖做這個使用NO循環,只有遞歸。循環它不壞,但我最近開始學習遞歸,並希望僅使用遞歸完成此方法。當你無法正常工作時,它非常令人沮喪。謝謝你的幫助。
我建議是這樣的:
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
)等等。 a
和b
標誌表示什麼時候修剪樹(NULL
節點)。
僞代碼:
Traverse (queue, t):
visit t
For each child c of t:
put c to queue
Traverse (queue, pop queue)
你並不需要做遞歸,這將是慢!
看看在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);
}
}
這似乎很清楚,遞歸不是一個很好的匹配這個問題。 – NPE 2013-03-02 07:31:49
@NPE遞歸對於這個問題是完全可選的。你可以用它或不用它來做,但是子隊列是關鍵的。該算法是純尾遞歸,因此可以很容易地完成它,但也可以使用它。 – WhozCraig 2013-03-02 07:46:08
如果您向我們展示了迄今爲止您嘗試的代碼的示例,它將會非常有用。 – Kev 2013-03-02 23:06:08