Tree Insert

This is a discussion on Tree Insert within the C++ Programming forums, part of the General Programming Boards category; I have made a class of tree with 12 children. I insert the data in the tree systematically, Like first ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    112

    Tree Insert

    I have made a class of tree with 12 children. I insert the data in the tree systematically, Like first root, then first children , second children, and so on.
    I am having problems in coding this function.
    I am sharing with you, whatever i have managed so far.
    here is the code, Kindly help with the insert function.

    Code:
    class Node
    {
    	public:
    	char data[25];
    	Node *next[12];
    	
    };
    
    class Tree
    {
    	Node* root;
    	
    public:
    	Tree()
    	{
    		root=NULL;
    		
    	}
    		
    	void insert(char a[25])
    	{
    		Node* temp = new Node();
    			
    		strcpy(temp->data,a );
    		//temp = root;
    		for (int i = 1; i < 13; i ++)
    			temp->next[i] = NULL;
    		
    		
    		
    		for (int i = 1; i <13; i ++)
    		{
    			if (temp->next[i] == NULL)
    				strcpy(temp->data,a);
    			//break;
    			return;
    		}
    
    		for (int i= 1; i < 13; i++)
    		{
    			temp = temp->next[i];
    			for (int i = 1; i <13; i ++)
    			{
    				if (temp->next[i] == NULL)
    				strcpy(temp->data,a);
    				//break;
    				return;
    			}
    			temp = root;
    		}
    
    		for (int i= 1; i < 13; i++)
    		{
    			temp = temp->next[i]->next[i];
    			for (int i = 1; i <13; i ++)
    			{
    				if (temp->next[i] == NULL)
    				strcpy(temp->data,a);
    				return;
    			}
    			temp = root;
    		}
    		
    	}
    
    	void treeSearch(char a[25])
    	{
    		Node* temp;
    		temp = root;
    		bool flag = false;
    
    		for ( int i = 1; i < 13; i++ )
    		{
    			if (strcmp(temp->next[i]->data,a)== 0)
    			{
    				flag = true;
    				cout<<"Found";
    				break;
    			}
    			
    		}
    
    		if ( flag == false)
    		{
    			for ( int i = 1; i < 13; i++ )
    			{
    				temp = temp->next[i];
    				for (int i = 1; i < 13; i++ )
    				{
    					if (strcmp(temp->next[i]->data,a)== 0)
    					{
    						flag = true;
    						cout<<"Found";
    						break;
    					}
    				}
    				temp = root;
    			}
    		
    			for ( int i = 1; i < 13; i++ )
    			{
    				temp = temp->next[i]->next[i];
    				for (int i = 1; i < 13; i++ )
    				{
    					if (strcmp(temp->next[i]->data,a)== 0)
    					{
    						flag = true;
    						cout<<"Found";
    						break;
    					}
    				}
    				temp = root;
    			}
    		
    		}
    
    		
    	}

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you have 12 items in an array, they are numbered 0 through 11, not 1 through 12.

    If you intend to always insert in order, it may not be a bad idea to just store a pair of numbers for the "next" place to insert so you don't have to try and find it each time. If you're not necessarily inserting in order, then you need to know (whether by passing in a parameter, or by setting a criteria) where the new object is supposed to go.

    You'll also need to have root involved somehow.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Quote Originally Posted by tabstop View Post

    You'll also need to have root involved somehow.
    Didn't get you , How to involve the root. Plus I m making the tree of height 2.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Fatima Rizwan View Post
    Didn't get you , How to involve the root. Plus I m making the tree of height 2.
    You're trying to insert temp into temp. You need to make your new object temp, and then hook it onto the root of the tree (by saying root->next[5] = temp or whatever).

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Maybe I am looking at your code wrong, but are you just inserting "randomly" and then searching brute force wise thru every node?

    I had thought the purpose of a tree was to place lower values to the left and higher values to the right, so you can get something like O(log(n)) lookups.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by MK27 View Post
    I had thought the purpose of a tree was to place lower values to the left and higher values to the right, so you can get something like O(log(n)) lookups.
    That's the purpose of a binary search tree, yes. Not all trees are BST, though, and when you see the phrase "every node has 12 children" that may be a hint. (What the purpose of this particular tree is, I have no idea.)

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    You should be able to do this with just one lot of nested loops. The outer loop allocates each immediate child of the root, and as you enter a loop inside that, it builds the children of that particular node etc.

    MK27: A typical case of a tree that is not a BST is a disk directory. They're used when the emphasis is on the heirarchial structure, not the lookup time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  3. 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
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21