binary tree

[lams]

Hello everybody, i need help on a binary tree am working on. The program should read a list of keys from a data file and insert the keys into an initially
empty tree in the order listed in the data file. The insert function should not allow duplicate key insertions. The function should print an error message if a duplicate key is found. The program
constructs a tree, traverses the tree and also display the height. the problem should also display a back slash if the tree is null or if any of the node is, my question is, where do i put the slashes in the code that i have displayed below

#include <iostream>
#include <cstddef>
using namespace std;

template <class Type>
struct NodeType {
Type key;
NodeType<Type> *lptr;
NodeType<Type> *rptr;
};
template <class Type>
class BST {// Binary search tree
public:
BST();
void insert(Type x);
void traverse ();
int height()const;
private:
NodeType<Type> *insert(Type x, NodeType<Type> *rot);
void traverse (NodeType<Type> *root);
int height(NodeType<Type> *root)const;
int max(int x, int y)const;
NodeType<Type> *root;
};

template <class Type>
BST<Type>::BST()
{
root = NULL;
}
template <class Type>
void BST<Type>::insert(Type x)
{
root = insert(x, root);
}

template <class Type>
NodeType<Type> *BST<Type>::insert(Type x, NodeType<Type> *root) // binary tree insert routine
// -- inserts key x into tree pointed to by root
{
// create new node
NodeType<Type> *n = new NodeType<Type>;
n->key = x;
n->lptr = n->rptr = NULL;

if(root == NULL)
root = n;
else {
NodeType<Type> *curr = root;
NodeType<Type> *prev; // behind curr
while(curr != NULL) { // loop for search process
prev = curr;
if(x < curr->key)
curr = curr->lptr; // go left
else
curr = curr->rptr; // go right
}
// insert (connect) new node
if(x < prev->key)

else
prev->rptr = n;
}
return root;
}
template <class Type>
void BST<Type>::traverse()
{
traverse(root);
}

template<class Type>
int BST<Type>::height()const
{
return height(root);
}

template<class Type>
int BST<Type>::height(NodeType<Type> *root)const
{
if(root==NULL)
return 0;
else
return 1 + max(height(root->lptr), height(root->rptr));
}

template<class Type>
int BST<Type>::max(int x, int y)const
{
if(x >= y)
return x;
else
return y;
}

template <class Type>
void BST<Type>:: traverse(NodeType<Type> *root) // inorder traversal routine
{
if(root != NULL) {
cout << root->key <<endl; //visit node (print key)
traverse(root->lptr); // traverse left subtree
traverse(root->rptr); // traverse right subtree
}
}


thank you.

[lams]

The display should look like this

Example :Preorder Traversal: 8 5 3 2 1 / / / 4 / / 7 / / 10 9 / / 12 / /

[snowright]

Here is your code indented. This will make the chance of someone helping you much better.

#include <iostream>
#include <cstddef>
using namespace std;

template < class Type > struct NodeType {
    Type key;
     NodeType < Type > *lptr;
     NodeType < Type > *rptr;
};
template < class Type > class BST {	// Binary search tree
  public:
    BST();
    void insert(Type x);
    void traverse();
    int height() const;
  private:
    NodeType < Type > *insert(Type x, NodeType < Type > *rot);
    void traverse(NodeType < Type > *root);
    int height(NodeType < Type > *root) const;
    int max(int x, int y) const;
    NodeType < Type > *root;
};

template < class Type > BST < Type >::BST()
{
    root = NULL;
}

template < class Type > void BST < Type >::insert(Type x)
{
    root = insert(x, root);
}

template < class Type > NodeType < Type > *BST < Type >::insert(Type x, NodeType < Type > *root)	// binary tree insert routine
// -- inserts key x into tree pointed to by root
{
// create new node
    NodeType < Type > *n = new NodeType < Type >;
    n->key = x;
    n->lptr = n->rptr = NULL;

    if (root == NULL)
	root = n;
    else {
	NodeType < Type > *curr = root;
	NodeType < Type > *prev;	// behind curr
	while (curr != NULL) {	// loop for search process
	    prev = curr;
	    if (x < curr->key)
		curr = curr->lptr;	// go left
	    else
		curr = curr->rptr;	// go right
	}
// insert (connect) new node
	if (x < prev->key)

	    else
	    prev->rptr = n;
    }
    return root;
}

template < class Type > void BST < Type >::traverse()
{
    traverse(root);
}

template < class Type > int BST < Type >::height() const const
{
    return height(root);
}

template < class Type > int BST < Type >::height(NodeType < Type > *root) const const
{
    if (root == NULL)
	return 0;
    else
	return 1 + max(height(root->lptr), height(root->rptr));
}

template < class Type > int BST < Type >::max(int x, int y) const const
{
    if (x >= y)
	return x;
    else
	return y;
}

template < class Type > void BST < Type >::traverse(NodeType < Type > *root)	// inorder traversal routine
{
    if (root != NULL) {
	cout << root->key << endl;	//visit node (print key)
	traverse(root->lptr);	// traverse left subtree
	traverse(root->rptr);	// traverse right subtree
    }
}

When posting a message under format choose the symbol <> which will add code tags in the middle of which you add your code.

[lams]

thank you