Problem When Printing a Binary Tree

[Gawaine]

The problem with my program is that whenever I run it, it prints out a zero even though a zero is not one of the numbers in the file. Also the count is sometimes wrong. Any suggestions?


info.txt

1
2
3
4
54
6
7
8
9
10
11
21
32

tree.h with relevant functions

struct tree{
    int info;
    tree *left;
    tree *right;
};

tree* newLeaf(int data) {
	tree* f= new tree;
	f->info = data;
	f->left = f->right = NULL;
	return f;
}

int count(tree *p){
    if( p == NULL)
        return(0);
    else
        if( p->left == NULL && p->right == NULL)
            return(0);
        else
            return(1 + (count(p->left) + count(p->right)));
}

#include <iostream>
#include <fstream>
#include <queue>
#include "tree.h"
using namespace std;
fstream fin;
int main(){
    tree *x = new tree;
    queue <int> s;
    fin.open("info.txt");
    int in = 0;

    while(!fin.eof()){
        fin >> in;
        s.push(in);
    }
    
    fin.close();
    newLeaf(s.front());
    
    while (!s.empty()){
        insert (s.front(), x);
        s.pop();
    }
    
    cout << "In Order: ";
    inTrav(x);
    cout << endl;
    
    cout << "Pre-Order: ";
    preTrav(x);
    cout << endl;
    
    cout << "Post-Order: ";
    postTrav(x);
    cout << endl;
    
    cout << "count of tree: " << count(x);
    
    return 0;
}

[cire]

tree.h with relevant functions

Speaking of relevant functions, where are insert, inTrav, preTrav and postTrav?

Your count function doesn't count leaves, even though they contain data.

int count(tree *p)
{
    if ( !p )
        return 0;

    return 1 + count(p->left) + count(p->right);
}

[coder777]

line 19 in tree.h: return 1; since there is a node

it prints out a zero even though a zero is not one of the numbers

You didn't show the print functions. There might be even a problem in the insert function

[Gawaine]

Sorry it took so long but here are the insert and trav functions...

void insert(int key, tree *p)
{
    if(key < p->info)
    {
        if(p->left != NULL)
            insert(key, p->left);
        else
        {
            p->left = new tree;
            p->left->info = key;
            p->left->left = NULL;    //Sets the left child of the child node to null
            p->left->right = NULL;   //Sets the right child of the child node to null
        }
    }
    else if(key>=p->info)
    {
        if(p->right!= NULL)
            insert(key, p->right);
        else
        {
            p->right = new tree;
            p->right->info = key;
            p->right->left = NULL;  //Sets the left child of the child node to null
            p->right->right = NULL; //Sets the right child of the child node to null
        }
    }
}

void inTrav(tree *root){
    if(root != NULL){
        inTrav(root->left);
        cout << root->info << " ";
        inTrav(root->right);
    }
}
void preTrav(tree *root){
    if(root != NULL){
        cout << root->info << " ";
        preTrav(root->left);
        preTrav(root->right);
    }
}
void postTrav(tree *root){
    if(root != NULL){
        postTrav(root->left);
        postTrav(root->right);
        cout << root->info << " ";
    }
}
 

[coder777]

A problem is on line 8: tree *x = new tree; x remains unintialized. It's undefined what happens when you add a node to this.

I suggest following change:

void insert(int key, tree *&p) // Note: &
{
if(p) // Note
{
    if(key < p->info)
    {
        if(p->left != NULL)
            insert(key, p->left);
        else
        {
            p->left = new tree;
            p->left->info = key;
            p->left->left = NULL;    //Sets the left child of the child node to null
            p->left->right = NULL;   //Sets the right child of the child node to null
        }
    }
    else if(key>=p->info)
    {
        if(p->right!= NULL)
            insert(key, p->right);
        else
        {
            p->right = new tree;
            p->right->info = key;
            p->right->left = NULL;  //Sets the left child of the child node to null
            p->right->right = NULL; //Sets the right child of the child node to null
        }
    }
}
else  // Note
{
            p = new tree;
            p->info = key;
            p->left = NULL;
            p->right = NULL;
}
}
...
int main(){
    tree *x = NULL;
...

Are you aware that you do not insert. It's only appending (it may not a problem if intended)

[Gawaine]

Thanks coder777, the change worked. Can you also go into more detail about why the insert function isn't really an insert?
I understand that it appends the tree and adds a new leaf but why wouldn't that be considered an insert?

[coder777]

Imagine a tree like this:

0
- 101
- 202

if you want to insert 2 it would look like this:

0
- 101
-- 2
-202

It's added after 101 not before like it might be expected