Level order traversal using queue in php

Php program for Level order traversal using queue. Here problem description and other solutions.

<?php
/*
  Php program for
  Level order tree traversal using queue
*/
// Create Q node
class QNode
{
	public $data;
	public $next;

	function __construct($node)
	{
		$this->data = $node;
		$this->next = NULL;
	}
}
// Binary Tree Node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class MyQueue
{
	public $head;
	public $tail;
	public $count;
	public	function __construct()
	{
		$this->head = NULL;
		$this->tail = NULL;
		$this->count = 0;
	}
	public	function size()
	{
		return $this->count;
	}
	public	function isEmpty()
	{
		return $this->count == 0;
	}
	// Add new node of queue
	public	function enqueue($value)
	{
		// Create a new node
		$node = new QNode($value);
		if ($this->head == NULL)
		{
			// Add first element into queue
			$this->head = $node;
		}
		else
		{
			// Add node at the end using tail
			$this->tail->next = $node;
		}
		$this->count++;
		$this->tail = $node;
	}
	// Delete a element into queue
	function dequeue()
	{
		if ($this->head == NULL)
		{
			// Empty Queue
			return;
		}
		// Visit next node
		$this->head = $this->head->next;
		$this->count--;
		if ($this->head == NULL)
		{
			// When deleting a last node of linked list
			$this->tail = NULL;
		}
	}
	// Get front node
	public	function peek()
	{
		if ($this->head == NULL)
		{
			return NULL;
		}
		return $this->head->data;
	}
}
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	public	function levelOrder()
	{
		if ($this->root != NULL)
		{
			$q = new MyQueue();
			// Add first node
			$q->enqueue($this->root);
			$node = $this->root;
			while ($q->isEmpty() == false && $node != NULL)
			{
				if ($node->left != NULL)
				{
					// Add left child node
					$q->enqueue($node->left);
				}
				if ($node->right != NULL)
				{
					// Add right child node
					$q->enqueue($node->right);
				}
				// Display level node
				echo "  ".strval($node->data);
				// Remove current node
				$q->dequeue();
				// Get new head
				$node = $q->peek();
			}
		}
		else
		{
			echo "Empty Tree", "\n";
		}
	}
	public static
	function main($args)
	{
		// Create new tree
		$tree = new BinaryTree();
		/*
		  Make A Binary Tree
		  -----------------------
		         1
		       /   \
		      2     3
		     /     / \
		    4     5   6
		   /     / \
		  7     8   9
		*/
		// Adding tree nodes
		$tree->root = new TreeNode(1);
		$tree->root->left = new TreeNode(2);
		$tree->root->right = new TreeNode(3);
		$tree->root->right->right = new TreeNode(6);
		$tree->root->right->left = new TreeNode(5);
		$tree->root->left->left = new TreeNode(4);
		$tree->root->left->left->left = new TreeNode(7);
		$tree->root->right->left->left = new TreeNode(8);
		$tree->root->right->left->right = new TreeNode(9);
		// Display level order  element
		$tree->levelOrder();
	}
}
BinaryTree::main(array());

Output

  1  2  3  4  5  6  7  8  9



Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2022, kalkicode.com, All rights reserved