Ad:

C++ Discussion Thread
Marked Solved
Views: 545

Jun 5th, 2009

Tree help

Expand Post »

So in a binary tree the insertion looks something like this:

C++ Syntax (Toggle Plain Text)
void btree::insert(int num)
{
	if(root!=NULL)
	{
		insert(num, root);
	}
	else
	{
		root=new Node;
		root->data=num;
		root->left=NULL;
		root->right=NULL;
	}
}
 
void btree::insert(int num, Node *leaf)
{
	if(num< leaf->data)
	{
		if(leaf->left!=NULL)
		{
			insert(num, leaf->left);
		}
		else
		{
			leaf->left=new Node;
			leaf->left->data=num;
			leaf->left->left=NULL;
			leaf->left->right=NULL;
		}
	}
	else if(num>=leaf->data)
	{
		if(leaf->right!=NULL)
			insert(num, leaf->right);
		else
		{
			leaf->right=new Node;
			leaf->right->data=num;
			leaf->right->left=NULL;
			leaf->right->right=NULL;
		}
	}
}
void btree::insert(int num)
{
	if(root!=NULL)
	{
		insert(num, root);
	}
	else
	{
		root=new Node;
		root->data=num;
		root->left=NULL;
		root->right=NULL;
	}
}
	
void btree::insert(int num, Node *leaf)
{
	if(num< leaf->data)
	{
		if(leaf->left!=NULL)
		{
			insert(num, leaf->left);
		}
		else
		{
			leaf->left=new Node;
			leaf->left->data=num;
			leaf->left->left=NULL;
			leaf->left->right=NULL;
		}
	}
	else if(num>=leaf->data)
	{
		if(leaf->right!=NULL)
			insert(num, leaf->right);
		else
		{
			leaf->right=new Node;
			leaf->right->data=num;
			leaf->right->left=NULL;
			leaf->right->right=NULL;
		}
	}
}

But how would you insert for an n-ary tree?

Similar Threads

Left Column Menu Tree in JavaScript / DHTML / AJAX
Binary search tree removal in C++
outputing a basic tree ? in C
Insertion in a binary search tree in C++
Help with strings and file directory tree in C

JackDurden

Reputation Points: 10

Solved Threads: 0

Junior Poster in Training

Offline

92 posts
since Jun 2008

Permalink

Jun 5th, 2009

Re: Tree help

The same way, except instead of dealing with only two links, you have more than two (usually in an array).

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Jun 5th, 2009

Re: Tree help

It would be better if you divide that nary tree nodes in some hierarchical levels so that it would be helpful in deciding their positions in future.

csurfer

Reputation Points: 485

Solved Threads: 88

Posting Pro

Offline

564 posts
since Jan 2009

Permalink

Jun 5th, 2009

Re: Tree help

So If i had this how would I keep track of the root children?

C++ Syntax (Toggle Plain Text)
#include<iostream>
#include<vector>
 
using namespace std;
 
class Tree
{
public:
	Tree() { root = NULL; }
 
	bool isEmpty() const { return root==NULL; }
	void insert(int);
	void remove(int);
 
private:
	struct node
	{
		node *parent;
		vector <node*> children;
		int item;
	};
 
node* root;
};
 
void Tree::insert(int num)
{
	if(isEmpty())
	{
		root=new node;
		root->item = num;
	}
	else
	{
		//?
	}
 
}
 
int main()
{
return 0;
}
#include<iostream>
#include<vector>

using namespace std;

class Tree
{
public:
	Tree() { root = NULL; }

	bool isEmpty() const { return root==NULL; }
	void insert(int);
	void remove(int);
	
private:
	struct node
	{
		node *parent;
		vector <node*> children;
		int item;
	};

node* root;
};

void Tree::insert(int num)
{
	if(isEmpty())
	{
		root=new node;
		root->item = num;
	}
	else
	{
		//?
	}

}

int main()
{
return 0;
}

JackDurden

Reputation Points: 10

Solved Threads: 0

Junior Poster in Training

Offline

92 posts
since Jun 2008

Permalink

Jun 5th, 2009

Re: Tree help

Well, do the children need to be in any specific order? If so, you know what to do: keep the vector sorted to maintain that order. That's how you keep track of the nodes.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Jun 5th, 2009

Re: Tree help

Or may be a priority array which stores the data in the node for referencing the node and its level or priority in the tree.

csurfer

Reputation Points: 485

Solved Threads: 88

Posting Pro

Offline

564 posts
since Jan 2009

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: URGENT! It is for my assignment. I am so stuck. Please check my c++ work.

Next Thread in C++ Forum Timeline: Flie Handling

DaniWeb Message

Cancel Changes

User Name
Password