Binary Search Tree Operations

[robertica23]

Hi! I have a homework based on the BST. I have some of the operations from the class but some I had to implement by myself. The problem is that I implemented all of them and when I complile it crashes.
This is my BST.h header:
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
#include <istream>
using namespace std;

int rDeph=0,lDeph=0;
int rHeight=0, lHeight=0;
template<typename T> class BinarySearchTree {
public:
BinarySearchTree<T> *root, *left_son, *right_son, *parent;
T *pinfo;

BinarySearchTree() {
left_son = right_son = NULL;
root = this;
pinfo = NULL;
}

void setInfo(T info) {
pinfo = new T;
*pinfo = info;
}

void insert(T x) {
if (pinfo == NULL)
setInfo(x);
else
insert_rec(x);
}

void insert_rec(T x) {
int next_son;
if (x <= (*pinfo))
next_son = 0;
else
next_son = 1;

if (next_son == 0) { // left son
if (left_son == NULL) {
left_son = new BinarySearchTree<T>;
left_son->pinfo = new T;
*(left_son->pinfo) = x;
left_son->left_son = left_son->right_son = NULL;
left_son->parent = this;
left_son->root = root;
} else
left_son->insert_rec(x);
} else { // right son
if (right_son == NULL) {
right_son = new BinarySearchTree<T>;
right_son->pinfo = new T;
*(right_son->pinfo) = x;
right_son->left_son = right_son->right_son = NULL;
right_son->parent = this;
right_son->root = root;
} else
right_son->insert_rec(x);
}
}

void inOrderTraversal() {
if (left_son != NULL)
left_son->inOrderTraversal();
printf("%d\t", *pinfo);
if (right_son != NULL)
right_son->inOrderTraversal();
}

void preOrderTraversal() {
printf("%d\t", *pinfo);
if (left_son != NULL)
left_son->preOrderTraversal();
if (right_son != NULL)
right_son->preOrderTraversal();
}

void postOrderTraversal() {
if (left_son != NULL)
left_son->postOrderTraversal();
if (right_son != NULL)
right_son->postOrderTraversal();
printf("%d\t", *pinfo);
}
void remove() {
BinarySearchTree<T> *p;
T *paux;

if (left_son == NULL && right_son == NULL) {
if (parent == NULL) { // this == root
delete this->pinfo;
root->pinfo = NULL;
} else {//we have a leaf
if (parent->left_son == this)
parent->left_son = NULL;
else
parent->right_son = NULL;

delete this->pinfo;
delete this;
}
} else {
if (left_son != NULL) {
p = left_son;
while (p->right_son != NULL)
p = p->right_son;
} else { // right_son != NULL
p = right_son;
while (p->left_son != NULL)
p = p->left_son;
}

paux = p->pinfo;
p->pinfo = this->pinfo;
this->pinfo = paux;
p->remove();
}
}
void searchMax(){
if(right_son == NULL){
printf("%d\t", *pinfo);
printf("\n");
}

if(right_son != NULL)
right_son->searchMax();
}

void printLevelOrder() { // a kind of BFS
Queue<BinarySearchTree*> currentLevel, nextLevel;
currentLevel.enqueue(this);
printf("\n");
while (!currentLevel.isEmpty()) {
BinarySearchTree *currNode = currentLevel.peek();
currentLevel.dequeue();
if (currNode) {
printf("%d ",*currNode->pinfo);
nextLevel.enqueue(currNode->left_son);
nextLevel.enqueue(currNode->right_son);
}
if (currentLevel.isEmpty()){
printf("\n");
swap(currentLevel, nextLevel);
}
}
}
void PrintArr(int arr[],int len)
{
int pathNo=0;
int i;

printf("\nPath %d ->",++pathNo);

for(i=0;i<len;i++)
printf(" %d ",arr[i]);

return;
}
void routes(){
BinarySearchTree<T> *p;
int* pathArr[20];
int pathLen;
if(root == NULL)
return;
pathArr[pathLen] = pinfo;
pathLen++;

if(left_son==NULL && right_son==NULL)
{
PrintArr(*pathArr,pathLen);
return;
}
else
{
left_son->routes();
right_son->routes();
}
}

void mirror()
{
BinarySearchTree<T> *p;
if (left_son==NULL && right_son==NULL)
return;
else
{
BinarySearchTree<T> *t;

left_son->mirror();
right_son->mirror();

t = left_son;
left_son = right_son;
right_son = t;
}
}
void createDoubleTree() {
BinarySearchTree<T> *p;
if (p == NULL) {
return;
}
p->left_son->createDoubleTree();
BinarySearchTree<T> *t = left_son;
p->left_son->pinfo = p->pinfo;
p->left_son->left_son = t;
p->right_son->createDoubleTree();
}
BinarySearchTree<T> *commonAncestor(BinarySearchTree<T> *p, int p1,int p2){
if(p->root == NULL)
return NULL;
if(p->root->pinfo > &p1 && p->root->pinfo > &p2)
return commonAncestor(p->left_son,p1,p2);

if(p->root->pinfo < &p1 && p->root->pinfo < &p2)
return commonAncestor(p->right_son,p1,p2);
return p->root;
}

};

[dhayden]

Your insert_rec() and *Traversal() methods look good, but I'm having trouble following the rest of the code.

When implementing a binary tree, it's helpful to use two classes. One is the binary tree itself, and the other is a node within a tree. The BinaryTree has a pointer to root, but the nodes do not. The Nodes have a value member, but the tree does not:

template < typename T > class BinarySearchTree {
private:
    class Node {
    public:
        T val;
        Node *left, *right, *parent;
        Node(const T &v, Node *p) :
            val(v),
            left(NULL),
            right(NULL),
            parent(p)
        {}
    };


  public:
    Node *root;

    BinarySearchTree() {
        root = NULL;
    }

    void insert_rec(const T &x)
    {
        Node *p, **pp;
        for (pp = &root; p = *pp;) {
            if (x <= p->value) {
                pp = &p->left;
            } else {
                pp = &p->right;
            }
        }
        *pp = new Node(x, p);
    }

    void inOrder (Node *p)
    {
        if (p) {
            inOrder(p->left);
            cout << p->val << '\t';
            inOrder(p->right);
        }
    }
    void inOrderTraversal() { inOrder(root); }
    ...

printf("%d\t", *pinfo);
This takes your nice generic template class and restricts T to intger types. Better to use:
cout << *pinfo << '\t';