DaniWeb Forum Index > Software Development > C++

C++ RSS

Tree help

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Jun 2008

Posts: 92

Reputation: JackDurden is an unknown quantity at this point

Solved Threads: 0

JackDurden JackDurden is offline

Offline

Junior Poster in Training

Tree help

Jun 5th, 2009

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

 Help with Code Tags 
 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?

•

Join Date: Sep 2004

Posts: 7,625

Reputation: Narue has a reputation beyond repute

Solved Threads: 716

Narue

Offline

Code Goddess

Re: Tree help

Jun 5th, 2009

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

I'm here to prove you wrong.

•

Join Date: Jan 2009

Posts: 476

Reputation: csurfer is just really nice

Solved Threads: 76

csurfer

Offline

Posting Pro in Training

Re: Tree help

Jun 5th, 2009

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.

I Surf in "C"....

•

Join Date: Jun 2008

Posts: 92

Reputation: JackDurden is an unknown quantity at this point

Solved Threads: 0

JackDurden JackDurden is offline

Offline

Junior Poster in Training

Re: Tree help

Jun 5th, 2009

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

 Help with Code Tags 
 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;
}

•

Join Date: Sep 2004

Posts: 7,625

Reputation: Narue has a reputation beyond repute

Solved Threads: 716

Narue

Offline

Code Goddess

Re: Tree help

Jun 5th, 2009

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.

I'm here to prove you wrong.