1

我的问题是如何在二叉树上执行级别顺序遍历？我知道您会使用 que，但是我将如何递归地执行此操作？简而言之，我正在尝试按级别顺序打印树的内容，如下所示：

     3
    / \
   2   1
  / \   \
 4   6   10

将打印：3 2 1 4 6 10

我尝试了无数次失败的尝试，这些尝试都出现了段错误并感到沮丧并删除了它们。我正在尝试使用 NO 循环来做到这一点，只有递归。使用循环它还不错，但我最近开始学习递归并希望仅使用递归来完成此方法。当您无法使其正常工作时，它会非常令人沮丧。谢谢你的帮助。

4

3 回答 3

2

伪代码：

Traverse (queue, t):
  visit t
  For each child c of t:
      put c to queue
  Traverse (queue, pop queue)
于 2013-03-02T07:18:31.163 回答
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)，依此类推。和标志表示何时修剪树（a节点）。bNULL

于 2013-03-02T07:06:53.853 回答
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);
    }

}
于 2015-12-23T12:05:18.217 回答