0

二分木の単一レベルでノードを印刷（訪問）する必要があります。
これがどのように行われるかはわかりませんが、一般的なアルゴリズムについてはあまり熟練していません。
幅優先探索では、キューを使用し、ルートノードをキューに入れることから始めて、ルートノードをデキューして子をエンキューし、最初にエンキューされた子をキューから外して、子をエンキューすることを知っています。 on ...
そして私の理解では、バイナリツリーが作成されたときに各ノードにレベルを割り当ててから、幅優先探索を実行しているときにレベルを確認しない限り、あるレベルがいつ終了し、別のレベルがいつ開始するかを正確に知ることは不可能です。 。

このようなもの（コードはPHPですが、これはPHP関連の質問ではありません。これは一般的なアルゴリズム関連の質問です。これは、各ノードが追加されたときにノードのレベルを格納するバイナリツリーにノードを追加する関数の一部です。 ）：：

if($this->root == null)
    {
        $this->root = $node;
                    $this->root->level = 1;
        return;
    }

    $nextnode = $this->root;

            $level = 1;

    while (true)
    {
        if($node->value > $nextnode->value)
        {
                        if($nextnode->right != null)
                        {
                            $nextnode = $nextnode->right;
                            $level++;
                        }
                        else
                        {
                            $nextnode->right = $node;
                            $nextnode->right->level = ++$level;
                            return;
                        }
        }
        else if($node->value < $nextnode->value) 
        {
                        if($nextnode->left != null)
                        {
                            $nextnode = $nextnode->left;
                            $level++;
                        }
                        else
                        {
                            $nextnode->left = $node;
                            $nextnode->left->level = ++$level;
                            return;
                        }
        }
        else if($node->value == $nextnode->value)
            return;
    }

だから私の質問は：

これは、バイナリツリーの単一レベルでノードを印刷する唯一の方法ですか？
別の方法はありますか？
ツリーを作成するときにレベルを保存せずに別の方法はありますか？

4

2 に答える 2

3

再帰的なソリューションはあなたに適していますか？私はこれをCで書きました、これがあなたにとって問題ではないことを願っています。

void traverse_tree_rec(TreeNode *ptn, int current_level, int targeted_level, (void*)(pVisit)(TreeElement*)){    
    if (ptn==NULL)
        return;
    else if(current_level == targeted_level)
        pVisit(ptn->entry);
    else{
        traverse_tree_rec(ptn->left, current_level+1, targeted_level, pVisit);
        traverse_tree_rec(ptn->right, current_level+1, targeted_level, pVisit);
    }
}

void traverse_level(Tree *pTree, int level, (void*)(pFunction)(TreeElement)){
    traverse_level_rec(pTree->root, 0, level, pFunction);
}
于 2010-01-23T08:33:40.087 に答える
0

@パラ、

これにより、あるレベルがいつ終了し、別のレベルがいつ開始するかを正確に知ることは不可能になります。

実行しようとしているBFSトラバーサル中に、ツリー全体をトラバースする必要はありません。配列レベル[]を導入することにより、wikiで提供されているBFS疑似コードを変更できます。あなたはこれらをしなければなりません：

  1. 各ノードのレベルを0として初期化します。

  2. uが行にoをマークするときはいつでも：o ← G.opposite(t,e)level [o] = level[t]+1を割り当てます。

  3. 後t ← Q.dequeue()の場合level[t] > targeted_level break;

于 2012-09-10T14:53:31.870 に答える