Binary Search Tree

[harde_1]

Hi, I need a function that will take a tree as argument and
return the number of ints that were typed and
a correct call.

would it just be preorder? like below. Please. Thanks

#include "t.h"

void preorder(tnode * t){
    if (t == NULL) return;
    cout << t->info <<endl;
    preorder(t->left);
    preorder(t->right);
    }

call would be preorder(t).

[rubberman]

Assuming this is a tree structure with one data point per node, then you need a node structure/class that contains an int value and left/right nodes that point to items less than value (left) and those with more (right). So, what you are doing is counting the number of nodes (leafs) in the tree. So, your function should return the count of leaves it traverses. Something like this:

#include "t.h"
struct tnode {
    int value;
    tnode* left;
    tnode* right;
    tnode(int v = 0) : left(0), right(0), value(v) {}
    int countChildren() const;
};
int tnode::countChildren() const
{
    int retval = 1;  // Count self;
    if (left)
    {
        retval += left->countChildren();
    }
    cout << dec << value << endl;
    if (right)
    {
        retval += right->countChildren();
    }
    return retval;
}

By placing the current node's print statement beetween left and right branches, we will end up printing the values in numeric order.

[harde_1]

This is the original program I have. Need that function in here.

#ifndef T_H
#define T_H

#include <iostream>
#include <iomanip>
using namespace std;

struct tnode {
    int info ;
    int count;
    tnode * right, *left;
};

tnode * insert(int target,tnode * t);
tnode * makenode(int x);
tnode * tsearch(int x,tnode * t);
void inorder(tnode * t);
int height(tnode * t);
int count(tnode * t) ;
int total(tnode * t) ;

#endif

int main() {
int n,c;
tnode * t = NULL, *x;
    while (cin >> n) {t=insert(n,t);cout << n <<' ';}
    cout << endl;
    inorder(t);
    cout << endl;
    c = count(t);
    cout << "count: "<< c  <<endl;
    cout << endl;
    c = height(t);
    cout << "height: "<< c  <<endl;
    cout << endl;
    c=200;
    while (c-->0) if (x = tsearch(c,t)) cout << c << " is on the tree."<<endl;
return 0;
}

#include "t.h"

int count(tnode * t) {
    if (t == NULL) return 0;
    return 1 +  count(t->left) + count (t->right);
}

#include "t.h"

int height(tnode * t) {
    if (t == NULL) return -1;
    return 1 + max(height(t->left) , height (t->right));
}

#include "t.h"

//write out t in order
void inorder(tnode * t) {
    if (t == NULL) return;
    inorder (t->left);//write out lst in order
    cout <<setw(5) << t->info <<setw(5) << t->count<< endl;
    inorder (t->right);//write out rst in order
}

#include "t.h"

tnode * insert(int x, tnode * t) {
tnode * tmp = tsearch(x,t);
if (tmp != NULL) {
    tmp->count++;
    return t;
}
if (t == NULL) return makenode(x);
if ( x < t->info ) {
    t->left = insert(x,t->left);
    return t;
}
t->right = insert(x,t->right);
return t;
}

#include "t.h"

tnode * makenode(int x) {
tnode * t = new tnode;
    t->info =x;
    t->count =1;
    t->right = t->left = NULL;
return t;
}