PHP的二叉搜索树，如何遍历

问题描述

嗯，我建立使用一类叫做节点为了简单起见，我将包括用于插入节点

Well i build a basic Binary Search Tree using a class called Node for simplicity i will include the core method that is used to insert Nodes

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类

我有这些基本的成员瓦尔

i have these basic member vars in the Node class

    private $left = null;

private $right = null;

private $value = null;

private $parent = null;

我可以通过简单地将节点添加到它构建一个树。

I can construct a tree by simply adding nodes to it.

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

现在的问题是我如何遍历树，如果我想打印树的一个很好的文字图。我很困惑如何遍历对上树的特定水平。我错过一个重要的变量构造树是什么时候？

Now the question is how do i traverse the tree if i want to print a nice text diagram of the tree. I am confused on how to traverse right on a specific level of the tree. did i miss an important variable when constructing the tree?

推荐答案

答案将取决于要遍历树什么样的顺序，而是一般深度优先遍历看起来像：

The answer would depend on what order you want to traverse the tree, but a general depth-first traversal would look like:

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

在注释你想要的广度优先遍历。请参阅有关Java中的广度优先遍历这个问题。您可以使用相同的算法。 如何实现广度优先遍历？

这篇关于PHP的二叉搜索树，如何遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！