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:

[iamthwee]

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 ???

[iamthwee]

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..

[iamthwee]

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