Функция для определения, является ли дерево моно (все элементы уникальны) или нет?

Я пытаюсь добавить функцию Total и функции isMono в этот код. Сделал уже

Нужна помощь с функцией ismono, которая возвращает, является ли дерево моно (все элементы уникальны или нет, элемент не появляется более одного раза) или нет. пожалуйста

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

0

Решение

//Gets the value of the node at the leftmost node
int left_most_value(tnode * t) {
if (t == NULL) return (0); //Something went wrong
if (t->left == NULL) return(t->info);
else return(left_most_value(t));
}

//Gets the value of the node at the rightmost node
int right_most_value(tnode * t) {
if (t == NULL) return (0); //Something went wrong
if (t->right == NULL) return(t->info);
else return(right_most_value(t));
}

//Returns true (1) if node does NOT have duplicate
int node_is_mono(tnode * t) {
//Ignore leaf nodes
if (t->left == NULL && t->right == NULL) return 1;

//Check the left side
if (t->left != NULL && right_most_value(t->left) == t->info) return(0);

//Check the right side
if (t->right != NULL && left_most_value(t->right) == t->info) return(0);

//This node is mono
return(1);
}

int tree_is_mono(tnode * t) {
if (t == NULL) return(1);

//If one node has a duplicate, then the entire tree is NOT mono
if (node_is_mono(t) == 0) return 0;
else return(tree_is_mono(t->left) && tree_is_mono(t->right));
}

На каждом узле дерева вам необходимо выполнить следующие шаги.

  1. Найдите самый левый узел узла из дочерних узлов справа. Если они равны по стоимости, то дерево НЕ моно (прекратить поиск и return false)
  2. Найдите самый правый узел узла из его дочерних узлов слева. Если они равны по стоимости, то дерево НЕ моно (прекратить поиск и return false)
  3. Мы не нашли равных по значению узлов, поэтому дерево моно! return true
1

Другие решения

Если вы используете C ++, вы можете просто использовать std::set или же std::unordered_set сохранить список объектов в вашем дереве. Затем вы используете обход дерева (inorder, preorder, postorder и т. Д.), И для каждого объекта в обходе вы делаете следующее:

  1. Вы проверяете, находится ли он уже в set, Если это так, то return false;,
  2. Вы добавляете элемент к set,

Затем, когда вы закончите с обходом, вы знаете, что нет никаких дубликатов, так просто return true;,

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector