Мне нужно принять данные от пользователя, чтобы заполнить дерево, а затем найти максимальную высоту и указания, как его получить. (L - слева и R - справа) Например, пользовательские вводы: 50 25 75 15 40 60 30 55 56 57 Выход должен быть HRLLRR, но у меня есть HRRRR
Или другой пример, когда ввода: 50 25 75 15 40 60 100 Выход должен быть HRR, но у меня есть HRRR
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
template <typename T>
class Tree {
private :
T info;
Tree* left;
Tree* right;
public :
Tree() {
info = NULL;
left = right = NULL;
}
Tree* insert(Tree<T>* head,T value);
void InOrder(Tree* head);
void findMaxPath(Tree<T>*);
int findMax(Tree<T>*);
};
string path="H";
int main() {
Tree<int>* head = NULL;
char ch;
int info;
do {
cin >> ch;
switch (ch) {
case 'i':
cin >> info;
head = head->insert(head, info);
break;
case 'p':
head->InOrder(head);
cout << endl;
break;
case 'm':
head->findMaxPath(head);
cout << path << endl;
break;
}
}while (ch != 'e');
}
template <typename T>
Tree<T>* Tree<T>::insert(Tree<T>* head,T value) {
if (head == NULL) {
head = new Tree<T>();
head->info = value;
return head;
}
if (head->info > value) {
head->left = insert(head->left, value);
}
else
head->right = insert(head->right, value);
return head;
}
template <typename T>
void Tree<T>::InOrder(Tree<T>* head) {
if (head != NULL) {
InOrder(head->left);
cout << head->info << " ";
InOrder(head->right);
}
}
template <typename T>
void Tree<T>::findMaxPath(Tree<T>* head){
if (head == NULL) {
cout << "Empty" << endl;
return;
}
else findMax(head);
}
template <typename T>
int Tree<T>::findMax(Tree<T>* head){
if (head==NULL){
cout << path << endl;
return 0;
}
else{
int leftMax, rightMax;
int max = head->info;
if(head->left != NULL){
leftMax = findMax(head->left);
if(leftMax > max){
max = leftMax;
path+="L";
}
}
if(head->right != NULL){
rightMax = findMax(head->right);
if(rightMax > max){
max = rightMax;
path+="R";
}
}
return max;
}
}