1

私の質問は、二分木でレベル順トラバーサルをどのように実行するのですか? que を使用することは理解していますが、これを再帰的に行うにはどうすればよいでしょうか? 要するに、ツリーの内容を次のようにレベル順に出力しようとしています。

     3
    / \
   2   1
  / \   \
 4   6   10

次のように出力します: 3 2 1 4 6 10

私は多くの失敗した試みを試みましたが、セグメンテーション違反が発生し、イライラしてそれらを削除しました。私はループを使用せず、再帰のみを使用してこれを実行しようとしています。ループは悪くありませんが、最近再帰を学び始めたので、再帰のみを使用してこのメ​​ソッドを終了したいと考えています。正しく動作しないと、非常にイライラします。助けてくれてありがとう。

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およびフラグはb、ツリーの剪定 (NULLノード) がヒットしたことを示します。

于 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 に答える