6 Replies - 522 Views - Last Post: 25 September 2009 - 09:27 PM Rate Topic: -----

#1 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

My First Tree

Posted 24 September 2009 - 10:27 PM

This is my first binary tree i wanted you guyz to check if i did something wrong or if i can improve it some way, so far is just getting numbers in it and showing them.
Got help from Martyr2's Programming Underground > Plant a Node, make a Binary Tree Forest in C++!

Well here is the code
#include <iostream>
#include <ctime>

using namespace std;


class Btree{
	int num;
	Btree *right;
	Btree *left;
public:
	void addItem(Btree *&tree, int val);
	void printTree(Btree *aTree);
};
void Btree::addItem(Btree *&tree, int val){
	Btree *temp=new Btree;
	Btree *ttemp=tree;
	temp->num=val;
	temp->left=NULL;
	temp->right=NULL;
	bool flag = false;
	if(tree==NULL)
		tree=temp;
	else{
		while(!flag){
			if(val<ttemp->num){
				if(ttemp->left==NULL){
					ttemp->left=temp;
					flag=true;
				}else{
					ttemp=ttemp->left;
				}
			}else
				if(val>ttemp->num){
					if(ttemp->right==NULL){
						ttemp->right=temp;
						flag=true;
					}else
						ttemp=ttemp->right;
				}else
					flag=true;
		}
	}
}
void Btree::printTree(Btree *aTree){
	if(aTree->left!=NULL)
		printTree(aTree->left);
	cout<<aTree->num<<endl;
	if(aTree->right!=NULL)
		printTree(aTree->right);
}
int main(){
	int num=0;
	Btree *root=NULL;
	srand((unsigned int)time(NULL));
	for(int i=0;i<20;i++){
		num=rand()%100+1;
		root->addItem(root,num);
	}
	root->printTree(root);
	cin.get();
	return 0;
}


All comments are welcome :)

Is This A Good Question/Topic? 0
  • +

Replies To: My First Tree

#2 Lillefix  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 37
  • View blog
  • Posts: 204
  • Joined: 19-September 08

Re: My First Tree

Posted 25 September 2009 - 05:01 AM

Well, as a start I see that you pass pointer to a Btree to the functions addItem() and printTree(). There is no point in doing that as those functions already is a member of the class Btree.

So I would first remake those to addItem(int val) and printTree(). For tips on doing this, remember that (this) returns a pointer to the current class. See this link for more info: Codersource.net

A second, minor, adjustment, would be to make a default constructor for Btree that initialises the left and right pointers to null.

This post has been edited by Lillefix: 25 September 2009 - 05:03 AM

Was This Post Helpful? 0
  • +
  • -

#3 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: My First Tree

Posted 25 September 2009 - 05:43 AM

Ok here is with the constructor, but i still dont understand the addItem thing can you explain?
/* Codded by poncho4all using Visual Studio 2008 */

#include <iostream>
#include <ctime>

using namespace std;


class Btree{
	int num;
	Btree *right;
	Btree *left;
public:
	Btree();
	~Btree();
	void addItem(Btree *&tree, int val);
	void printTree(Btree *&root);
};
Btree::Btree(){
	right=NULL;
	left=NULL;
}
void Btree::addItem(Btree *&tree, int val){
	Btree *temp=new Btree;
	Btree *ttemp=tree;
	temp->num=val;
	bool flag = false;
	if(tree==NULL)
		tree=temp;
	else{
		while(!flag){
			if(val<ttemp->num){
				if(ttemp->left==NULL){
					ttemp->left=temp;
					flag=true;
				}else{
					ttemp=ttemp->left;
				}
			}else
				if(val>ttemp->num){
					if(ttemp->right==NULL){
						ttemp->right=temp;
						flag=true;
					}else
						ttemp=ttemp->right;
				}else
					flag=true;
		}
	}
}
void Btree::printTree(Btree *&root){
	if(root->left!=NULL)
		printTree(root->left);
	cout<<root->num<<endl;
	if(root->right!=NULL)
		printTree(root->right);
}
int main(){
	int num=0;
	Btree *root=NULL;
	srand((unsigned int)time(NULL));
	for(int i=0;i<20;i++){
		num=rand()%100+1;
		root->addItem(root, num);
	}
	root->printTree(root);
	cin.get();
	return 0;
}


Thanks for the comments
Was This Post Helpful? 0
  • +
  • -

#4 Lillefix  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 37
  • View blog
  • Posts: 204
  • Joined: 19-September 08

Re: My First Tree

Posted 25 September 2009 - 06:39 AM

Hm, I suppose it is easier to just show you how I would have done it. Notice that I don't have to pass anything to the printTree() function.


#include <iostream>
#include <ctime>

using namespace std;


class Btree
{
	private:
		int num;
		Btree *right;
		Btree *left;
	public:
		Btree();
		void addItem(int val);
		void printTree();
};
Btree::Btree()
{
	right = NULL;
	left = NULL;
}
void Btree::addItem(int val)
{
	Btree *temp = new Btree;
	Btree *ttemp = this;
	temp->num = val;
	bool flag  =  false;
	if(ttemp == NULL)
	{
		ttemp = temp;
	}
	else
	{
		while(!flag)
		{
			if(val<ttemp->num)
			{
				if(ttemp->left == NULL)
				{
					ttemp->left = temp;
					flag = true;
				}
				else
				{
					ttemp = ttemp->left;
				}
			}
			else
			{
				if(val>ttemp->num)
				{
					if(ttemp->right == NULL)
					{
						ttemp->right = temp;
						flag = true;
					}
					else
					{
						ttemp = ttemp->right;
					}
				}
				else
				{
					flag = true;
				}
			}
		}
	}
}
void Btree::printTree()
{
	if(this->left != NULL)
		this->left->printTree();
	cout<<this->num<<endl;
	if(this->right != NULL)
		this->right->printTree();
}
int main()
{
	int num = 0;
	Btree *root = new Btree;
	srand((unsigned int)time(NULL));
	for(int i = 0;i<20;i++)
	{
		num = rand()%100+1;
		root->addItem(num);
	}
	root->printTree();
	cin.get();
	return 0;
}

Was This Post Helpful? 1
  • +
  • -

#5 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: My First Tree

Posted 25 September 2009 - 12:44 PM

Ya i was reading the link you got me but when i got a little time on my hands but i think its a concept ima hold one for a while before implementing.
Right now im trying to get the logic of the trees InOrder way ;)
Here is my new code:
/* Codded by Miguel Alfonso Bustamante Sanchez AKA poncho4all using Visual Studio 2008 */

#include <iostream>
#include <ctime>

using namespace std;


class Btree{
	int num;
	Btree *right;
	Btree *left;
public:
	Btree();
	~Btree();
	void addItem(Btree *&root, int val);
	void printTree(Btree *root);
	int leaves(Btree *root);
	int size(Btree *root);
	int cont,cont2;
};
Btree::Btree(){
	num=0;
	right=NULL;
	left=NULL;
	cont=0;
	cont2=0;
}
void Btree::addItem(Btree *&root, int val){
	Btree *temp=new Btree;
	Btree *ttemp=root;
	temp->num=val;
	bool flag = false;
	if(root==NULL)
		root=temp;
	else{
		while(!flag){
			if(val<=ttemp->num){
				if(ttemp->left==NULL){
					ttemp->left=temp;
					flag=true;
				}else{
					ttemp=ttemp->left;
				}
			}else
				if(val>=ttemp->num){
					if(ttemp->right==NULL){
						ttemp->right=temp;
						flag=true;
					}else
						ttemp=ttemp->right;
				}else
					flag=true;
		}
	}
}
void Btree::printTree(Btree *root){
	if(root->left!=NULL)
		printTree(root->left);
	cout<<root->num<<endl;
	if(root->right!=NULL)
		printTree(root->right);
}
int Btree::leaves(Btree *temp){
	if(temp->left==NULL&&temp->right==NULL)
		cont++;
	//else
		if(temp->left!=NULL)
			leaves(temp->left);
		if(temp->right!=NULL)
			leaves(temp->right);
	return cont;
}
int Btree::size(Btree *temp){
	if(temp->left==NULL&&temp->right==NULL)
		cont2++;
	else
		cont2++;
		if(temp->left!=NULL)
			size(temp->left);
		if(temp->right!=NULL)
			size(temp->right);
	return cont2;
}
int main(){
	Btree *root=NULL;
	int num[9]={4,2,8,9,1,6,7,10,3};
	srand((unsigned int)time(NULL));
	for(int i=0;i<9;i++){
		root->addItem(root, num[i]);
	}
	cout<<"This Tree has "<<root->leaves(root)<<" leaf"<<endl;
	cout<<"This Tree has "<<root->size(root)<<" nodes"<<endl;
	root->printTree(root);
	cin.get();
	return 0;
}


I included two new function to count leaves and to count the number of nodes.
I need more tutorials on trees do you know any good ones?
Was This Post Helpful? 0
  • +
  • -

#6 Lillefix  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 37
  • View blog
  • Posts: 204
  • Joined: 19-September 08

Re: My First Tree

Posted 25 September 2009 - 05:05 PM

This seems quite nice as both an introductional and an advanced guide to binary trees.
Was This Post Helpful? 1
  • +
  • -

#7 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: My First Tree

Posted 25 September 2009 - 09:27 PM

Wow that link was really helpfull, i have now added the PreOrder,PostOrder print to the code :)
/* Codded by Miguel Alfonso Bustamante Sanchez AKA poncho4all using Visual Studio 2008 */

#include <iostream>
#include <ctime>

using namespace std;


class Btree{
	int num;
	Btree *right;
	Btree *left;
public:
	Btree();
	~Btree();
	void addItem(Btree *&root, int val);
	void InOrderPrint(Btree *root);
	void PreOrderPrint(Btree *root);
	void PostOrderPrint(Btree *root);
	int leaves(Btree *root);
	int size(Btree *root);
	int cont,cont2;
};
Btree::Btree(){
	num=0;
	right=NULL;
	left=NULL;
	cont=0;
	cont2=0;
}
void Btree::addItem(Btree *&root, int val){
	Btree *temp=new Btree;
	Btree *ttemp=root;
	temp->num=val;
	bool flag = false;
	if(root==NULL)
		root=temp;
	else{
		while(!flag){
			if(val<=ttemp->num){
				if(ttemp->left==NULL){
					ttemp->left=temp;
					flag=true;
				}else{
					ttemp=ttemp->left;
				}
			}else
				if(val>=ttemp->num){
					if(ttemp->right==NULL){
						ttemp->right=temp;
						flag=true;
					}else
						ttemp=ttemp->right;
				}else
					flag=true;
		}
	}
}
void Btree::InOrderPrint(Btree *root){
	if(root!=NULL){
		InOrderPrint(root->left);
		cout<<root->num<<" ";
		InOrderPrint(root->right);
	}
}
void Btree::PreOrderPrint(Btree *root){
	if(root!=NULL){
		cout<<root->num<<" ";
		PreOrderPrint(root->left);
		PreOrderPrint(root->right);
	}
}
void Btree::PostOrderPrint(Btree *root){
	if(root!=NULL){
		PostOrderPrint(root->left);
		PostOrderPrint(root->right);
		cout<<root->num<<" ";
	}
}
int Btree::leaves(Btree *temp){
	if(temp->left==NULL&&temp->right==NULL)
		cont++;
	else
		if(temp->left!=NULL)
			leaves(temp->left);
		if(temp->right!=NULL)
			leaves(temp->right);
	return cont;
}
int Btree::size(Btree *temp){
	if(temp->left==NULL&&temp->right==NULL)
		cont2++;
	else
		cont2++;
		if(temp->left!=NULL)
			size(temp->left);
		if(temp->right!=NULL)
			size(temp->right);
	return cont2;
}
int main(){
	Btree *root=NULL;
	int num[10]={4,2,8,9,1,6,7,10,3,8};
	srand((unsigned int)time(NULL));
	for(int i=0;i<10;i++){
		root->addItem(root, num[i]);
	}
	cout<<"This Tree has "<<root->leaves(root)<<" leaf"<<endl;
	cout<<"This Tree has "<<root->size(root)<<" nodes"<<endl;
	cout<<"Tree InOrder"<<endl;
	root->InOrderPrint(root);
	cout<<"\nTree PreOrder"<<endl;
	root->PreOrderPrint(root);
	cout<<"\nTree PreOrder"<<endl;
	root->PostOrderPrint(root);
	cin.get();
	return 0;
}


:crazy: this is getting good :)
Back to reading ;)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1