print Binary search tree

[sivaslieko++]

hi,
I have a problem with BST. For example after the insertions of below numbers,
23 1 45 2 3 5 52 234 31

The output should be like this way:

23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

I have no problem in insertion but
I could not developed any method to output in this format:((
Is there anyone who can help me :sad:

Hint:

You need a Level order traversal algo. To implement a level-order traversal, you need a first-in first-out queue--not a stack.

You might also need to find out the maximum height of your tree.

No idea if that is actually correct but it seems logical ???

You could also look at the algorithm of REINGOLD AND TILFORD, maybe?

That might be beyond the scope of what you're trying to do though.;)

[sivaslieko++]

Hi,
actually I implemented Level order traversal successfull but I could not print like this way :

23
1,45
-,2 | 31,52
-,- | -,3 | -,- | -,234
-,- | -,- | -,- | -,5 | -,- | -,- | -,- | -,-

How can I insert "-" for null subtrees properly?
Thaks..

Erm, this is just pure guesswork (and could be completely wrong) but if you encounter a null thingy couldn't you just print a -, ?

visitlevel(S)
  T = Set()
  for each node in S   
    print node.Value
    if (node->left != null)
       T.insert(node->left)
    if (node->right != null)
       T.insert(node->right)
  if ( T.empty() != true)
    visitlevel(T)

visit(root)
  S = Set()
  S.insert(root)
  visitlevel(S)

if node is empty Then
   print "-,"
EndIf

23 1 45 2 3 5 52 234 31

And the tree:

23
              /    \
             1      45
              \     / \
               2   31  52
                \       \
                 3      234
                  \
                   5

[mkt193]

i need to understand how this function work

void BinarySearchTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}

[lotrsimp12345]

template <class KT, class DT>
void my_bst<KT,DT>::printLevelOrderAux(my_bst_node<KT,DT>* t, int level)
{
	if(t) 
	{
		if(level == 1) 
		{
			printf(" %d ", t->key);
		}
		else if (level > 1) 
		{
			printLevelOrderAux(t->left, level-1);
			printLevelOrderAux(t->right, level-1);
		}
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::printLevelOrder(my_bst_node<KT,DT>* t,int height) 
{
	int i;

	for(i = 1; i <=height; i++) 
	{
		printLevelOrderAux(t, i);
	}
}

template <class KT, class DT>
void my_bst<KT,DT>::show(int height)
{
	printLevelOrder(root,height);
}