CODEWITHSUNDEEP
phpalgorithm
DevZer0
DevZer0

Reputation: 13535

PHP Binary Search Tree, How to Traverse

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

    }

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?

Upvotes: 1

Views: 9105

Answers (2)

Mash
Mash

Reputation: 1349

A breadth first traversal is what you looking for:

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

Well Samuel already told you about breadth first traversal as I was writing this little function but still... I think that's what you're looking for.

Upvotes: 4

Samuel
Samuel

Reputation: 17171

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

From the comment you want breadth-first traversal. See this question about breadth-first traversal in Java. You can apply the same algorithm. How do implement a breadth first traversal?

Upvotes: 4

Related Questions