Binary tree help

Question

13 Years Ago

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

c++

Edited 13 Years Ago by connor.wells.7946

2 Contributors
4 Replies
315 Views
5 Hours Discussion Span
Latest Post 13 Years Ago Latest Post by VernonDozier

Dani AI

Generated 9 Months Ago

The real culprit is the Insert logic. In the posted code the first node gets allocated, but subsequent inserts never create a new node (local T is left NULL and gets assigned to the parent), so the tree stays a single-node tree. Other issues worth fixing: RT should be initialized to NULL, the input loop should use while (inputFile >> H) instead of while (!inputFile.eof()), TreeAvg must compute a sum then divide (not divide at every recursion), LeafCount should not add an extra +1, and DeepVal currently returns the depth (height) rather than the node value. was right to recommend allocating a new node on each insert and returning the subtree pointer.

Replace Insert with a recursive insert that returns the (possibly new) subtree root and call it with RT = Insert(RT, H) while reading:

Tree* Insert(Tree* root, int num)
{
    if (root == NULL) {
        Tree* node = new Tree();
        node->N = num;
        node->Lchild = node->Rchild = NULL;
        return node;
    }
    if (num < root->N)
        root->Lchild = Insert(root->Lchild, num);
    else
        root->Rchild = Insert(root->Rchild, num);
    return root;
}

// initialization and input:
RT = NULL;
int H;
while (inputFile >> H)
    RT = Insert(RT, H);

Compute average and leaf count with separate helper functions (avoid integer truncation for average):

int Sum(Tree* r) {
    if (!r) return 0;
    return r->N + Sum(r->Lchild) + Sum(r->Rchild);
}
double Average(Tree* r) {
    int cnt = NodeNum(r);
    return cnt ? static_cast<double>(Sum(r)) / cnt : 0.0;
}
int LeafCount(Tree* r) {
    if (!r) return 0;
    if (!r->Lchild && !r->Rchild) return 1;
    return LeafCount(r->Lchild) + LeafCount(r->Rchild);
}

To return the value stored at the deepest node, a level-order traversal (BFS) finds the last node visited at the deepest level:

#include <queue>

int DeepestValue(Tree* root) {
    if (!root) return 0; // or another sentinel
    std::queue<Tree*> q;
    q.push(root);
    Tree* last = nullptr;
    while (!q.empty()) {
        last = q.front(); q.pop();
        if (last->Lchild) q.push(last->Lchild);
        if (last->Rchild) q.push(last->Rchild);
    }
    return last->N;
}

Notes: BFS above returns the rightmost node at the deepest level (push left then right). For leftmost instead, enqueue right before left or capture first node at a new level. Also consider freeing nodes at program end for completeness and use std::fixed/setprecision to format the average if needed.

All 4 Replies

VernonDozier 2,218 Posting Expert

13 Years Ago

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.

Reply to this topic

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.

connor.wells.7946 0 Newbie Poster · Answer 1 · 2013-04-05T21:15:11+00:00

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

connor.wells.7946 0 Newbie Poster · Answer 2 · 2013-04-05T23:10:15+00:00

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.

VernonDozier 2,218 Posting Expert Featured Poster · Answer 3 · 2013-04-06T00:01:01+00:00

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.

Binary tree help

Dani AI

Recommended Answers Collapse Answers

All 4 Replies

Recommended Answers