C and C++

Welcome to Dream.In.Code
	Getting C++ Help is Easy! Join 135,948 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,712 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a C++ Expert

Nearly All Tree functions in c(recursive and iterative!)

Nearly All Tree functions in c(recursive and iterative!)

Options

nnnn

18 May, 2008 - 07:41 AM

Post #1

New D.I.C Head

Joined: 10 May, 2008
Posts: 1

cpp


#include<stdio.h>
#include<stdlib.h>

typedef struct tnode{
	int info;
	struct tnode *lchild;
	struct tnode *rchild;
}TNODE;

TNODE * createNode(int);
int countNode(TNODE *root);
int sumNode(TNODE *root);
int countLeaf(TNODE *root);
int countLeaf2(TNODE *root);
int countParent1(TNODE *root);
int countParent2(TNODE *root);
int countParent3(TNODE *root);
int countOdd1(TNODE *root);
int countOdd2(TNODE *root);
void inOrder(TNODE *root);
void preOrder(TNODE *root);
void postOrder(TNODE *root);
TNODE * rinsertBST(TNODE *root,int item);
TNODE * insertBST(TNODE *root,int item);
TNODE * rsearchBST(TNODE *root,int item);
TNODE * searchBST(TNODE *root,int item);
int rsearchBST2(TNODE *root,int item);
int searchBST2(TNODE *root,int item);
int height(TNODE *root);
int findMin(TNODE *root);
int findMax(TNODE *root);
int findLevel(TNODE *root,int item);

int main()
{
	int numberOfOdds;
	int numberOfParents;
	int numberOfLeafs;
	int sum;
	int nOfNodes;
	TNODE *root2=createNode(30);
	TNODE *root=createNode(43);
	root2->lchild=createNode(20);
	root2->lchild->rchild=createNode(25);
	root2->lchild->lchild=createNode(10);
	root2->lchild->lchild->rchild=createNode(11);
	root2->lchild->lchild->lchild=createNode(5);
	root2->lchild->lchild->lchild->lchild=createNode(1);
	root2->rchild=createNode(40);
	root2->rchild->rchild=createNode(50);
	root2->rchild->rchild->lchild=createNode(45);
	root->lchild=createNode(32);
	root->lchild->lchild=createNode(20);
	root->lchild->rchild=createNode(40);
	root->lchild->rchild->lchild=createNode(33);
	root->lchild->lchild->rchild=createNode(28);
	root->rchild=createNode(64);
	root->rchild->rchild=createNode(89);
	root->rchild->lchild=createNode(56);
	root->rchild->lchild->lchild=createNode(47);
	root->rchild->lchild->rchild=createNode(59);
	nOfNodes=countNode(root);
	printf("Number of nodes on tree is:%d\n",nOfNodes);
	sum=sumNode(root);
	printf("Sum of nodes on tree is:%d\n",sum);
	numberOfLeafs=countLeaf(root);
	printf("Number of leaves in our tree is:%d\n",numberOfLeafs);
	numberOfLeafs=countLeaf2(root);
	printf("Number of leaves in our tree is:%d\n",numberOfLeafs);
	numberOfParents=countParent1(root);
	printf("Number of parents in our tree is:%d\n",numberOfParents);
	numberOfParents=countParent2(root);
	printf("Number of parents in our tree is:%d\n",numberOfParents);
	numberOfParents=countParent3(root);
	printf("Number of parents in our tree is:%d\n",numberOfParents);
	numberOfOdds=countOdd1(root);
	printf("Number of odds in our tree is:%d\n",numberOfOdds);
	numberOfOdds=countOdd2(root);
	printf("Number of odds in our tree is:%d\n",numberOfOdds);
	printf("Traverse the tree inOrder:");
	inOrder(root);
	printf("\n");
	printf("Traverse the tree in preOrder:");
	preOrder(root);
	printf("\n");
	printf("Traverse the tree in postOrder:");
	postOrder(root);
	printf("\n");
	root=rinsertBST(root,34);
	printf("Traverse the tree inOrder:");
	inOrder(root);
	printf("\n");
	root=insertBST(root,55);
	root=insertBST(root,60);
	root=insertBST(root,99);
	printf("Traverse the tree inOrder:");
	inOrder(root);
	printf("\n");
	if(rsearchBST(root,43)==NULL)
		printf("Item can not be found!\n");
	else
		printf("Item found!\n");

	if(searchBST(root,105)==NULL)
		printf("Item can not be found!\n");
	else
		printf("Item found!\n");

	printf("Traverse the tree inOrder:");
	inOrder(root);
	printf("\n");

	if(rsearchBST2(root,43)==0)
		printf("Item can not be found!\n");
	else
		printf("Item found!\n");
	
	if(searchBST2(root,105)==0)
		printf("Item can not be found!\n");
	else
		printf("Item found!\n");
	
	printf("Traverse the tree(root) inOrder:");
	inOrder(root);
	printf("\n");

	printf("Traverse the tree(root2) inOrder:");
	inOrder(root2);
	printf("\n");

	printf("height of tree(root2) is:%d\n",height(root2));

	printf("min in tree(root2) is:%d\n",findMin(root2));
	printf("max in tree(root2) is:%d\n",findMax(root2));
	printf("min in tree(root) is:%d\n",findMin(root));
	printf("max in tree(root) is:%d\n",findMax(root));
	printf("level of 21 in root2 is:%d\n",findLevel(root2,21));
	return 0;
}
void postOrder(TNODE *root)
{
	if(root==NULL)
		return;
	printf("%d ",root->info);
	postOrder(root->lchild);
	postOrder(root->rchild);
}
void preOrder(TNODE *root)
{
	if(root==NULL)
		return;
	preOrder(root->lchild);
	preOrder(root->rchild);
	printf("%d ",root->info);
}
void inOrder(TNODE *root)
{
	if(root==NULL)
		return;
	inOrder(root->lchild);
	printf("%d ",root->info);
	inOrder(root->rchild);
}
TNODE *createNode(int info)
{
	TNODE *newNode=(TNODE *)malloc(sizeof(TNODE));
	if(newNode==NULL)
	{
		printf("\nOut of Memory!!\n");
		exit(0);
	}
	newNode->info=info;
	newNode->lchild=NULL;
	newNode->rchild=NULL;
	return newNode;
}
int countOdd1(TNODE *root)
{
	if(root==NULL)
		return 0;
	if(root->info%2==1)
		return 1+countOdd1(root->lchild)+countOdd1(root->rchild);
	return 0+countOdd1(root->lchild)+countOdd1(root->rchild);
}
int countOdd2(TNODE *root)
{
	int lc;
	int rc;
	if(root==NULL)
		return 0;
	lc=countOdd2(root->lchild);
	rc=countOdd2(root->rchild);
	if(root->info%2==1)
		return 1+lc+rc;
	return lc+rc;
}
int countParent2(TNODE *root)
{
	int lc;
	int rc;
	if(root==NULL)
		return 0;
	if(root->lchild==NULL && root->rchild==NULL)
		return 0;
	lc=countParent2(root->lchild);
	rc=countParent2(root->rchild);
	return 1+lc+rc;
}
int countParent3(TNODE *root)
{
	int lc;
	int rc;
	if(root==NULL)
		return 0;
	lc=countParent3(root->lchild);
	rc=countParent3(root->rchild);
	if(root->lchild!=NULL || root->rchild!=NULL)
		return 1+lc+rc;
	return 0;
}
int countParent1(TNODE *root)
{
	if(root==NULL)
		return 0;
	if(root->lchild!=NULL || root->rchild!=NULL)
		return 1+countParent1(root->lchild)+countParent1(root->rchild);
	return 0;
}
int countNode(TNODE *root)
{
	if(root==NULL)
		return 0;
	return 1+countNode(root->lchild)+countNode(root->rchild);
}
int sumNode(TNODE *root)
{
	if(root==NULL)
		return 0;
	return root->info+sumNode(root->lchild)+sumNode(root->rchild);
}
int countLeaf(TNODE *root)
{
	int lc;
	int rc;
	if(root==NULL)
		return 0;
	if(root->lchild==NULL && root->rchild==NULL)
		return 1;
	lc=countLeaf(root->lchild);
	rc=countLeaf(root->rchild);
	return lc+rc;
}
int countLeaf2(TNODE *root)
{
	if(root==NULL)
		return 0;
	if(root->lchild==NULL && root->rchild==NULL)
		return 1;
	else 
		return countLeaf2(root->lchild)+countLeaf2(root->rchild);
}
TNODE * rinsertBST(TNODE *root,int item)
{
	if(root==NULL)
		return createNode(item);
	if(item<root->info)
		root->lchild=rinsertBST(root->lchild,item);
	if(item>root->info)
		root->rchild=rinsertBST(root->rchild,item);
	return root;
}

TNODE * insertBST(TNODE *root,int item)
{
	TNODE *curr=root;

	while(curr!=NULL)
	{
		if(curr->info==item)
			break;
		if(item<curr->info)
		{
			if(curr->lchild==NULL)
			{
				curr->lchild=createNode(item);
				break;
			}
			curr=curr->lchild;
		}
		else
		{
			if(curr->rchild==NULL)
			{
				curr->rchild=createNode(item);
				break;
			}
			curr=curr->rchild;
		}
	}//end while
	return root;
}
TNODE * rsearchBST(TNODE *root,int item)
{
	if(root==NULL)
		return NULL;
	if(item<root->info)
		root=rsearchBST(root->lchild,item);
	else if(item>root->info)
		root=rsearchBST(root->rchild,item);

	return root;
}
TNODE * searchBST(TNODE *root,int item)
{
	TNODE *curr=root;

	while(curr!=NULL)
	{
		if(curr->info==item)
			break;
		if(item<curr->info)
		{
			curr=curr->lchild;
		}
		if(item>curr->info)
		{
			curr=curr->rchild;
		}
	}
	return curr;
}
int rsearchBST2(TNODE *root,int item)
{
	if(root==NULL)
		return 0;
	if(item<root->info)
		return rsearchBST2(root->lchild,item);
	else if(item>root->info)
		return rsearchBST2(root->lchild,item);

	return 1;
}
int searchBST2(TNODE *root,int item)
{
	TNODE *curr=root;

	while(curr!=NULL)
	{
		if(curr->info==item)
			return 1;
		if(item<curr->info)
			curr=curr->lchild;
		if(item>curr->info)
			curr=curr->rchild;
	}

	return 0;
}
int height(TNODE *root)
{
	int lh;
	int rh;
	if(root==NULL)
		return 0;
	lh=height(root->lchild);
	rh=height(root->rchild);
	if(lh>rh)
	{
		return lh+1;
	}
	return rh+1;
}
int findMin(TNODE *root)
{
	if(root->lchild==NULL)
		return root->info;
	return findMin(root->lchild);
}
int findMax(TNODE *root)
{
	if(root->rchild==NULL)
		return root->info;
	return findMax(root->rchild);
}
int findLevel(TNODE *root,int item)
{
	if(root==NULL)
	{
		printf("Item can not be found but insertion can be made to level:\n");
		return 1;
	}
	if(item<root->info)
		return 1+findLevel(root->lchild,item);
	else if(item>root->info)
		return 1+findLevel(root->rchild,item);
	return 1;
}

This Post Was Helpful!


Register for Free to Make These Ads Go Away!

gabehabe	RE: Nearly All Tree Functions In C(recursive And Iterative!) 18 May, 2008 - 08:01 AM Post #2
Donkey DIC Joined: 6 Feb, 2008 Posts: 5,514 Thanked: 96 times Dream Kudos: 2650 Expert In: ruling the world. My Contributions	You know, it might help if you tell us what problem you're having.
	This Post Was Helpful!

born2c0de	RE: Nearly All Tree Functions In C(recursive And Iterative!) 18 May, 2008 - 10:29 PM Post #3
printf("I'm a %XR",195936478); Joined: 26 Nov, 2004 Posts: 3,906 Thanked: 34 times Dream Kudos: 2800 Expert In: 80x86 Assembly, C/C++, VB6, VB.NET, C#, J2SE, Win32 API, Reversing My Contributions	If you're simply sharing the code (assuming that it works), post it in the Code Snippets section.
	This Post Was Helpful!