Thread: Binary tree

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    Binary tree

    I am trying to complete an insertion function for my binary tree, but i am a little confused, because it uses two classes. Here is the code:
    Code:
    class CBinTreeNode
    {
    public:
    	CBinTreeNode() :
    	left(0), right(0), parent(0) {}
    	CBinTreeNode(int k)  :
    	left(0), right(0), parent(0) {key = k;}
    
    	CBinTreeNode *left;
    	CBinTreeNode *right;
    	CBinTreeNode *parent;
    	int key;
    };
    
    class CBinTree
    {
    public:
    	CBinTree() {root = NULL;}
    
    	void Insert(CBinTreeNode *z, int &c)
    	{
    		// TO DO
    		
    
    		
    	}
    	CBinTreeNode *root;
    };
    Code:
    int main(int argc, char* argv[])
    {
    	// declare logistical variables (for testing)
    	const size_t sa = 10001;
    	int sizes[] = {1,2,3,4,5,6,7,8,9,10,20,30,40,70,100,200,300,500,1000,2000,5000,10000};
    	int s_sizes = 22;
    	int a[sa];			// This is always the input to work with
    	srand((unsigned int)time((time_t)0));
    
    // Demonstrate binary tree
    	cout << endl<< "Demonstrate binary search tree:" << endl;
    	int ts = 10;
    	InitA(a, ts, 100);		// generate small random array
    	Print(a, ts);			// display array
    	// insert each element onto stack
    	CBinTree tree;
    	c=0;
    	cout << endl<< "Insert:" << endl;
    	for (int i=0; i < ts; i++)
    	{
    		tree.Insert(new CBinTreeNode(a[i]), c);
    	}
    return 0;
    }
    All the above code was provided, so i need to do the Insert function (where it says "TO DO"). The pseudocode for this is:
    Code:
    Tree-Insert(T,z)
    y<- NIL
    x<-root[T]
    while x (does not equal) NIL
         do y<- x
              if key[z]<key[x]
                   then x<-left[x]
                   else x<-right[x]
    p[z]<-y
    if y = NIL
         then root[T]<-z
         else if key[z]<key[y]
                   then left[y]<-z
                   else right[y]<-z
    I'm trying to figure out how to make the pseudocode work for my insert function, but i'm a little confused because this program uses two classes for the tree, and i'm not that great with using classes.
    So, in the pseudocode insert function, the tree(T) is a parameter, but i don't have it as a parameter in my function. I can't figure out how to create x and assign it the root of the tree. If i can get that, i might be able to continue with the psuedocode.
    NOTE* - None of the code should be modified, except for the insert function's body. The parameter c in the function is just a counter.

    Any help would be appreciated.
    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Your Insert function is a class function; hence the "T" that you speak of is implicit. (In other words, it would have to be called like MyTree.Insert(MyNode, counter), and "T" would correspond to MyTree.) You can use the variables of the class (specifically, root) and they will refer to the variables owned by the object (in this case, you can use root and it will refer to MyTree.root).

  3. #3
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Ok, my first attempt at this function has failed.
    Code:
    class CBinTree
    {
    public:
    	CBinTree() {root = NULL;}
    
    	void Insert(CBinTreeNode *z, int &c)
    	{
    		// TO DO
    		CBinTreeNode *y = NULL;
    		CBinTreeNode *x = root;
    		CBinTreeNode *key;
    		CBinTreeNode *parent;
    
    		while(x != NULL)
    		{
    			y = x;
    			if (key[z] < key[x])
    			{
    				x = left[x];
    			}
    			else
    			{
    				x = right[x];
    			}
    		}
    		parent[z] = y;
    
    		if(y == NULL)
    		{
    			root = z;
    		}
    		else if(key[z] < key[y])
    		{
    			left[y] = z;
    		}
    		else
    		{
    			right[y] = z;
    		}
    
    		
    	}
    So, i got the errors: "illegal index, indirection not allowed" on almost every line in this function. I'm guessing i didn't declare the variables correctly?
    IDE - Visual Studio 2005
    Windows XP Pro

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    A couple things I see right away: you did remember to move this function after the declaration of root? Otherwise it won't have that variable name ready for you. Remember the class notation! The key of z is not key[z], but z.key (etc.)

  5. #5
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Now, i'm getting the error: "left of .key/.left/.parent/.right must have class/struct/union" on almost every line.
    Code:
    class CBinTree
    {
    public:
    	CBinTree() {root = NULL;}
    	
    	void Insert(CBinTreeNode *z, int &c)
    	{
    		// TO DO
    
    		CBinTreeNode *y = NULL;
    		CBinTreeNode *x = root;
    		
    		
    		while(x != NULL)
    		{
    			y = x;
    			if (z.key < x.key)
    			{
    				x = x.left;
    			}
    			else
    			{
    				x = x.right;
    			}
    		}
    		z.parent = y;
    
    		if(y == NULL)
    		{
    			root = z;
    		}
    		else if(z.key < y.key)
    		{
    			y.left = z;
    		}
    		else
    		{
    			y.right = z;
    		}
    
    		
    	}
    So, should the declarations of x and y be something like:
    Code:
    CBinTreeNode y;
    CBinTreeNode x;
    Then x and y would be like:
    Code:
    y = NULL;
    x.parent = root;
    But, it's not even recognizing z.key/left/parent/right as having a class either.
    IDE - Visual Studio 2005
    Windows XP Pro

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I didn't read carefully enough, so I inadvertently steered you wrong, I think:
    x.key is for when x is a class
    x->key is for when x is a pointer to a class.

    So you'll need x and y to be pointers (you can't assign NULL to a class object!), so put those back and use -> instead.

  7. #7
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Yep, that fixed it. Now it compiles without any errors. I'll see if it works correctly once i finish the other functions.

    Thanks tabstop
    IDE - Visual Studio 2005
    Windows XP Pro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM