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);
        }
    }
}

Recommended Answers

All 4 Replies

I forgot to mention that I need to insert all the numbers I showed above.

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):

The program does NOT run perfectly. If it did, the output would be right and you would not be posting. As far as whether it only reads in the first number, are you sure of that? Several things need to go right for the output to be what it is supposed to be. Put another way, you could get the output you are getting if any of the following are true.

  • The program is indeed only reading in the first number.
  • The program does not insert correctly.
  • The program does not traverse correctly.

You need to figure out which one it is. If you have not proven it is the first one, don't assume it is the first one.

I won't comment on whether the reading in part or the traversal part is correct. The insertion part seems quite problematic though. In particular, I see no calls to NewNode other than the one on line 68. I see no call to "new" outside of the NewNode function. I see no recursion in Insert and I see NewNode called only when RT is NULL. More memory needs to be allocated every time something is inserted into the tree, right? So check your Insert function logic to make sure that is happening.

if that's the case then where does the newnode calls go in the Insert function b/c all the examples I find online don't match.

I don't know which examples you are finding online. If they do not allocate memory every time a new node is inserted, I don't know how they can work. Somehow all this info has to get stored, which means memory must be allocated. Here's some code where "new" is called every time the "insert" function is called.

http://www.cprogramming.com/tutorial/lesson18.html

As to your code, you need to rewrite the Insert function completely. There's more than one way of doing it. I think you want to make it a non-void function. Have it return the node that was inserted. Since you are inserting a new node every time you call this (note that this allows for duplicate values in the tree), might as well stick it at the very top of the code. Return a pointer to the node created. For the top of the tree, when you are passed a NULL tree, just return the node created and assign RT to equal that pointer. You need to traverse right or left till you get to a child that is NULL in the correct direction. Assign that child to be the node created at the top of the function.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.