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);
    }
}

好吧，在我编写这个小函数时，Samuel 已经告诉过你关于广度优先遍历的内容，但仍然......我认为这就是你要找的。

于 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 回答