2 Replies - 588 Views - Last Post: 05 April 2013 - 02:52 PM Rate Topic: -----

#1 KaijuX25  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 26
  • Joined: 22-February 13

Binary Tree program

Posted 05 April 2013 - 07:39 AM

I'm writing a binary tree program to do the following actions:
a. Print out the tree in inorder
b. Print out the tree in preorder.
c. Print out the tree in postorder.
d. Print out the number of nodes in the tree. (Traverse the tree and count the nodes)
e. Sum up all the values in the tree and computer the average.
f. Count the number of leafs in the tree.
g. Print the value that is the deepest in the tree.

Here's the input file data I must use in the program:
75 97 82 47 90 59 23 51 36 110 66 102 69 79 13 130 49 41 19 67 85 64 115 30 94

The program runs perfectly but only reads in the 1st number. This is the output I get(I added the bold to stand out in this post):
In-Order:
75

Pre-Order:
75

Post-Order:
75

There are 1 nodes in this program.

The average of your input is 75.

The binary tree contains 1 leaves.

The deepest value in this program is 1

Process returned 0 (0x0) execution time : 0.030 s
Press any key to continue.


Also, the DeepVal function in my program can find the depth of the tree but I can't find how to make it say what value is the deepest. Can you help me?

Here's my source code:
#include <iostream>
#include <fstream>
using namespace std;

struct Tree
{
    int N;
    Tree *Rchild;
    Tree *Lchild;
};
Tree *RT;
Tree *NewNode();
void Insert(Tree *c, int N);
void InOrder(Tree *ptr);
void PreOrder(Tree *R);
void PostOrder(Tree *Pr);
int NodeNum(Tree *Node);
int TreeAvg(Tree *ND);
int LeafCount(Tree *root);
int DeepVal(Tree *ro);
ifstream inputFile;

int main()
{

    inputFile.open("TreeData.txt");
    while (!inputFile.eof())
    {
        int H;
        inputFile >> H;
        Insert(RT, H);
    }

    cout << "In-Order:" << endl;
    InOrder(RT);
    cout << endl;
    cout << "Pre-Order:" << endl;
    PreOrder(RT);
    cout <<  endl;
    cout << "Post-Order:" << endl;
    PostOrder(RT);
    cout << endl;
    cout << "There are " << NodeNum(RT) << " nodes in this program." << endl << endl;
    cout << "The average of your input is " << TreeAvg(RT) << "." << endl << endl;
    cout << "The binary tree contains " << LeafCount(RT) << " leaves." << endl << endl;
    cout << "The deepest value in this program is " << DeepVal(RT) << endl << endl;


    inputFile.close();
    return 0;
}

Tree *NewNode()
{
    Tree *temp;
    temp = new Tree();
    temp->N = 0;
    temp->Lchild = NULL;
    temp->Rchild = NULL;
    return temp;
}

void Insert(Tree *c, int Num)
{

    if(c == NULL)
    {
        RT = NewNode();
        RT->N = Num;
        return;
    }
    Tree *p;
    Tree *T;
    p = NULL;
    T = NULL;
    while(c != NULL)
    {
        p = c;
        if (Num < c->N)
        {
            c = c->Lchild;
        }
        else
        {
            c = c->Rchild;
        }
    }
    if(Num < p-> N)
    {
        p->Lchild = T;
    }
    else
    {
        p->Rchild = T;
    }
    return;
}

void InOrder(Tree *ptr)
{

    if (ptr == NULL)
    {
        return;
    }
    InOrder(ptr->Lchild);
    cout << ptr->N << endl;
    InOrder(ptr->Rchild);
    return;

}

void PreOrder(Tree *R)
{
    if (R == NULL)
    {
        return;
    }
    cout << R->N << endl;
    PreOrder(R->Lchild);
    PreOrder(R->Rchild);
    return;
}

void PostOrder(Tree *Pr)
{
    if (Pr == NULL)
    {
        return;
    }
    PostOrder(Pr->Lchild);
    PostOrder(Pr->Rchild);
    cout << Pr->N << endl;
    return;
}

int NodeNum(Tree *Node)
{
    if(Node != NULL)
    {
        return 1 + NodeNum(Node->Lchild) + NodeNum(Node->Rchild);
    }
    else
    {
        return 0;
    }
}

int TreeAvg(Tree *ND)
{
    if (ND == NULL)
    {
        return 0;
    }
    else
    {
        return (ND->N + TreeAvg(ND->Lchild) + TreeAvg(ND->Rchild)) / NodeNum(ND);
    }
}

int LeafCount(Tree *root)
{
    if(root == NULL)
    {
		return 0;
    }
	else if(root->Lchild == NULL && root->Rchild == NULL)
	{
	    return 1;
	}
	else
	{
	    return LeafCount(root->Lchild) + LeafCount(root->Rchild) + 1;
	}
}

int DeepVal(Tree *ro)
{
    if (ro == NULL)
    {
        return 0;
    }
	else
	{
		int lDepth = DeepVal(ro->Lchild);
		int rDepth = DeepVal(ro->Rchild);

		if(lDepth > rDepth)
		{
		    return (lDepth + 1);
		}
		else
		{
		    return (rDepth + 1);
		}
	}
}



Is This A Good Question/Topic? 0
  • +

Replies To: Binary Tree program

#2 KaijuX25  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 26
  • Joined: 22-February 13

Re: Binary Tree program

Posted 05 April 2013 - 02:16 PM

I forgot to mention that I need to insert all the numbers I showed above.
Was This Post Helpful? 0
  • +
  • -

#3 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,495
  • Joined: 23-August 08

Re: Binary Tree program

Posted 05 April 2013 - 02:52 PM

void Insert(Tree *c, int Num)
{

    if(c == NULL)
    {
        RT = NewNode();
        RT->N = Num;
        return;
    }
    Tree *p;
    Tree *T;
    p = NULL;
    T = NULL;
    while(c != NULL)
    {
        p = c;
        if (Num < c->N)
        {
            
            c = c->Lchild;
        }
        else
        {
            c = c->Rchild;
        }
    }
    if(Num < p-> N)
    {
        p->Lchild = T;
    }
    else
    {
        p->Rchild = T;
    }
    return;
}


When do you ever set T to anything but NULL?

Learn to use your debugger so you can step through the code and see what it is doing.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1