Im trying to add Total function and isMono functions to this code. Did total already

Need help with function ismono which returns whether a tree is mono (all the elements are unique aka no element appears more than one time) or not. Please

this is the original program

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

Recommended Answers

All 2 Replies

Not having a compiler handy, so treat the following as kind-of pseudo code, but if performance is no requirement you could define it as

bool isMono(const tNode* t)
{
    if (t == NULL) 
        return true;
    else
        return tsearch(t->info, t->left) == NULL && tsearch(t->info, r->right) == NULL && isMono(t->left) && isMono(r->right);
}

(assuming tsearch on an empty tree results in a NULL pointer)

The tree being "mono" is already an invariant as far as nodes go, you'll never have two nodes with the same key. However, you can check for the tree being "mono" with a simple traversal and a test to see if any of the counts are greater than 1 (which may be what you mean by "mono"):

bool isMono(tnode *root)
{
    if (!root) {
        return true;
    }

    if (root->count > 1) {
        return false;
    }

    return isMono(root->left) && isMono(root->right);
}
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.