1

さて、簡単にするために呼び出されたクラスを使用して、基本的な二分探索ツリーを構築します。ノードNodeに使用されるコア メソッドを含めます。insert

public function addNode($node)
    {
        if ($this->left == null && $node->getValue() < $this->value) {
            $this->left = $node;
            $this->left->parent = $this;
            return;
        }

        if ($this->right == null && $node->getValue() > $this->value) {
            $this->right = $node;
            $this->right->parent = $this;
            return;
        }

        if ($node->getValue() < $this->getValue()) {
            $this->left->addNode($node);
            return;
        }

        if ($node->getValue() > $this->getValue()) {
            $this->right->addNode($node);
            return;
        }

    }

Node クラスにこれらの基本メンバー変数があります

    private $left = null;

private $right = null;

private $value = null;

private $parent = null;

ノードを追加するだけでツリーを構築できます。

$node = new Node(5);
$node->addNode(new Node(7));
$node->addNode(new Node(3));
$node->addNode(new Node(4));

問題は、ツリーの素敵なテキスト図を印刷したい場合、どのようにツリーをトラバースするかです。ツリーの特定のレベルを右にトラバースする方法がわかりません。ツリーを構築するときに重要な変数を見逃していませんか?

4

2 に答える 2

4

幅優先トラバーサルは、あなたが探しているものです:

printTree($root) {
    $queue = array($root);
    while ( count($queue) ) {
        $node = array_shift($queue);
        echo $node;
        if($node->left != null)
            array_unshift($node->left);
        if($node->right != null)
            array_unshift($node->right);
    }
}

サミュエルは、私がこの小さな関数を書いているときに幅優先トラバーサルについて既に説明しましたが、それでも...それがあなたが探しているものだと思います。

于 2013-07-24T12:27:08.110 に答える
3

答えは、ツリーをトラバースする順序によって異なりますが、一般的な深さ優先トラバーサルは次のようになります。

function traverseTree($rootNode) {
    if($rootNode->left != null)
        traverseTree($rootNode->left);
    if($rootNode->right != null)
        traverseTree($rootNode->right);
    echo $rootNode->value;
}

幅優先のトラバーサルが必要なコメントから。Java での幅優先トラバーサルに関するこの質問を参照してください。同じアルゴリズムを適用できます。幅優先走査をどのように実装しますか?

于 2013-07-24T12:06:38.233 に答える