Reference and binary tree problem

[Obsidian_496]

Hi.
I'm working on a binary tree home assignment and I have a problem. Initially my program used global variables. I decided to change that and declare variables inside functions (various reasons, you probably understand why).

I want the program to run without using global variables.

However, I can't figure a way to get rid of this one last global (it's in red) variable (it's a reference actually). When I try fixing this, I get error when running program:
Thread stopped.
Fault: Acess violation at [address].

My program actually contains more functions, such as inorder, reorder, postorder etc but I removed them, cause they are not related to my problem. Less code for you to read :)

Thanks.

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

struct Node			   											     
{      int       Data;															
       Node* Right;														
       Node* Left;														
};

void Process (Node* BinTree);                				        	
void Insert   (Node* &BinTree, int i );                  			
bool Search   (Node* BinTree,  int a );						        	
int  Input();                                               			                        							    	

Node* Root;

int main()
{

	int end=1;
	char Type;

	for(int i=0; i<13; i++)
	{
		Insert(Root,i);
	}

	 while(end!=0)
	{
		clrscr();
		cout<<"S - Search Number\n";
		cout<<"C - Close\n";
		cin>>Type;
		Type=toupper(Type);
		switch(Type)
		{
			case 'S': {int z=Input(); Search(Root,z);} break;
			case 'C': return 0;
			default: break;
		}
	 }
	getch();
}

void Process(Node* BinTree)
{ cout << BinTree->Data << " "; }

void Insert(Node* &BinTree, int i)
{
	Node* one;
	Node* two;
	int Array[13]={1,2,3,6,5,4,7,8,9,10,13,12,11};
         
	if(!Root)
	{
		Root = new(Node);
		Root->Data = Array[i];
		cout << "Root: " << Root->Data << endl;
		Root->Right = NULL;
		Root->Left = NULL;
	}
    else
    {
		int Number = Array[i];
		cout << "one " << Number;
		one = Root;           						
		while (one != NULL)
		{													
			two = one;
			if (Number > one->Data)
			{
				one = one->Right;
				cout << two->Data << " >> " ;
			}
			else 										
			{
				one = one->Left;
				cout << two->Data << " << ";
			}
		}
		cout << endl;
		if (Number > two->Data)
		{
			two->Right = new(Node); two = two->Right;
		}
		else
		{
			two->Left = new(Node);
			two = two->Left;
		}
		two->Data = Number; two->Right = NULL; two->Left = NULL;
	}
}

bool Search( Node* BinTree, int a )
{
        int down = 0;
        Node *temp;  													
        temp = BinTree;      												
        while (true)
        {
            if (temp == NULL)
            {
			    cout<<"Not found!\n";
			    down-=down;
			    getch();
				return false;					
            }
            else if ( a == temp->Data )
            {
				cout << "Level: " << down << endl;
				down-=down;
				getch();
				return true;	
            }else if ( a < temp->Data )
            {
            temp = temp->Left;
            down++;
            }
            else
            {
				temp = temp->Right;
                down++;
            }
        }

}

int Input()
{
	int Array[13]={1,2,3,6,5,4,7,8,9,10,13,12,11};
	char row[256];
	int var;
	
	do{
	cout<<"Enter a number: ";
	fgets(row, 256, stdin);
	var = atoi (row);
	}while(var<1);
	return var;
}

[daviddoria]

I think the whole thing should be wrapped in a class called Tree or something. Then Root is simply a member variable and can be accessed no problem from all of its member functions (which should be all of the function you have written).

Let us know if you have any problems converting it - this is quite a useful thing to learn and will definitely make the code much much much more reusable.

Good luck,

Dave

[Obsidian_496]

I see. Unfortunately, I have not used classes in C++ before. But I understand the idea behind what you said. I just read an introduction to classes in C++, and it really seems like something useful. I only know basics in C++ (what I'm beight taught in University), and I focus on PHP and web-design for now.

I did not even think of using a class to fix my problem. I'm intended to use references (* and &) and things I learned about linked lists recently.

When I try to fix my code, program returns an error. Firstst element of array becomes the root, then program tries to find a place for 2nd element, and error message is shown. Program fails to add second element of array to binary tree. I can't figure out what exactly is happening.

[Obsidian_496]

The condition if(!Root) is not true.
First time Insert() is used, it is supposed to create the root (1st element) of binary tree. However, it does not happen and function skips to else{} part and tries to add second entry to the tree. Error occurs, when program tries to find place for second entry, because root does not exist.

I hope you understand what I mean.

I tried changing condition if(!Root) to if(Root->Data==NULL) but that does not work as well(it should, no?).

In short, I want the Insert() function to create a binary tree and it's first element when it is called for first time. I suspect it will work when called for 2nd and 3rd time. The code below returns an error. Code in my first post works, but it contains a global variable that I want to get rid of.

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

struct Node
{      int Data;															
       Node* Right;
       Node* Left;														
};

void Process  (Node* BinTree);                				        	
void Insert   (Node* &Root, int i );
bool Search   (Node* BinTree,  int a );						        	
int  Input();                                               			                        							    	


int main()
{
        Node* Root;
	int end=1;
	char Type;

	for(int i=0; i<13; i++)
	{
		Insert(Root,i);
	}

	 while(end!=0)
	{
		clrscr();
		cout<<"S - Search Number\n";
		cout<<"C - Close\n";
		cin>>Type;
		Type=toupper(Type);
		switch(Type)
		{
			case 'S': {int z=Input(); Search(Root,z);} break;
			case 'C': return 0;
			default: break;
		}
	 }
	getch();
}

void Process(Node* BinTree)
{ cout << BinTree->Data << " "; }

void Insert(Node* &Root, int i)
{
	Node* one;
	Node* two;
	int Array[13]={1,2,3,6,5,4,7,8,9,10,13,12,11};
         
	if(!Root)
	{
		Root = new(Node);
		Root->Data = Array[i];
		cout << "Root: " << Root->Data << endl;
		Root->Right = NULL;
		Root->Left = NULL;
	}
    else
    {
		int Number = Array[i];
		cout << "one " << Number;
		one = Root;           						
		while (one != NULL)
		{													
			two = one;
			if (Number > one->Data)
			{
				one = one->Right;
				cout << two->Data << " >> " ;
			}
			else 										
			{
				one = one->Left;
				cout << two->Data << " << ";
			}
		}
		cout << endl;
		if (Number > two->Data)
		{
			two->Right = new(Node); two = two->Right;
		}
		else
		{
			two->Left = new(Node);
			two = two->Left;
		}
		two->Data = Number; two->Right = NULL; two->Left = NULL;
	}
}

bool Search( Node* BinTree, int a )
{
        int down = 0;
        Node *temp;  													
        temp = BinTree;      												
        while (true)
        {
            if (temp == NULL)
            {
			    cout<<"Not found!\n";
			    down-=down;
			    getch();
				return false;					
            }
            else if ( a == temp->Data )
            {
				cout << "Level: " << down << endl;
				down-=down;
				getch();
				return true;	
            }else if ( a < temp->Data )
            {
            temp = temp->Left;
            down++;
            }
            else
            {
				temp = temp->Right;
                down++;
            }
        }

}

int Input()
{
	int Array[13]={1,2,3,6,5,4,7,8,9,10,13,12,11};
	char row[256];
	int var;

	do{
	cout<<"Enter a number: ";
	fgets(row, 256, stdin);
	var = atoi (row);
	}while(var<1);
	return var;
}