0

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

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?

3
Contributors
5
Replies
6
Views
7 Years
Discussion Span
Last Post by csurfer
0

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

0

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.

0

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

#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;
}
0

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.

0

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.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.