@gasonger0

Как найти бинарное дерево с заданной структурой в изначальном дереве?

Суть задания в следующем: дано 2 бинарных дерева. Нужно найти все поддеревья в первом такие, то по структуре они совпадают со вторым, т.е. заполненность листьями справа и слева одинакова.

Как найти эти самые совпадающие деревья, используя код, не понимаю...

Сами деревья реализованы следующим образом: есть класс дерева, который имеет указатель на корень дерева. Каждый отдельный лист представляет собой структуру, в котором хранится значение вершины, указатель на потомка справа и указатель на потомка слева. В кода ЗАПРЕЩЕНО использовать какие-либо библиотеки С++, даже стандартные типа vector, string и т.д., максимум fstream для манипуляций файлами.

Код программы прикладываю:

#include <iostream>

struct Tree {
	int value{};																					// Номер листа
	Tree* left{};																					// Потомок слева
	Tree* right{};																					// Потомок справа

	Tree(int _) : value(_), left(nullptr), right(nullptr) {};										// Конструктор с передачей в него значения листа
	Tree() : value{}, left(nullptr), right(nullptr) {};												// Конструктор по умолчанию
};

int compareByStruct(Tree* a, Tree* b, int lvl_a, int lvl_b, int cur_lvl_a, int cur_lvl_b) {			// Сравнение по структуре: принимает на вход
																									// Сравниваемые поддеревья, их уровни и текущий уровень
	int out{};																						// Переменная для вывода числа совпавших деревьев
	if ((lvl_a <= cur_lvl_a) && (lvl_b <= cur_lvl_b)) {												// Если находимся на допустимых уровнях
		if ((a->left != NULL) == (b->left != NULL)) {												// Если "пустота" листьев совпадает слева
			if ((a->right != NULL) == (b->right != NULL)) {											// Если "пустота" листьев совпадает справа
				out += compareByStruct(a->left, b->left, lvl_a, lvl_b, cur_lvl_a + 1, cur_lvl_b + 1);	// Сравниваем с увеличением уровня
				out += compareByStruct(a->right, b->right, lvl_a, lvl_b, cur_lvl_a + 1, cur_lvl_b + 1);
			}
		}
	}
	return out;
}

int compareByVal(Tree* a, Tree* b) {																// Сравнение по значению
	int match{};
	if ((a->left != nullptr) && (b->left != nullptr)) {
		if ((a->left->value) == (b->left->value)) {
			match++;
			match += compareByVal(a->left, b->left);
		}
	}

	if ((a->right != nullptr) && (b->right != nullptr)){
		if ((a->right->value) == (b->right->value)) {
			match++;
			match += compareByVal(a->right, b->right);
		}
	}

	return match;
}

class Treehouse {

	friend int compare(Treehouse a, Treehouse b) {													// Функция сравнения
		int match{};
		match += compareByVal(a.bin->left, b.bin->left);
		match += compareByVal(a.bin->right, b.bin->right);
		return match;
	}												
private:
	Tree* bin = new Tree(0);																		// Наше дерево			
public:

	int level{};																					// Уровень дерева

	Treehouse() {																					// Конструктор														
		std::cout << "Enter level of Tree: ";														// Ввод ранга дерева
		try {
			std::cin >> level;
			std::cin.clear();
		}
		catch (std::exception e) {
			std::cout << "Enter integers!!!";
		}
		for (int i{}; i < level; i++) {																// Проходим к нижнему уровню дерева
			add(bin->left);																			// Добавляем потомков слева 
			add(bin->right);																		// Добавляем потомков справа
		}
	}

	void add(Tree*& T) {																			// Втсавка потомков, на вход принимает лист, в который нужно вставить потомков
		int value{};																				// Значение для вставки
		if (!T) {																					// Если переданный лист пуст
			std::cout << "Enter value of cell: ";													// Вводим значение
			try {
				std::cin >> value;
				std::cin.clear();
			}
			catch (std::exception e) {
				std::cout << "Enter correct value! (int)\n";
			}
			if (value != 0) {
				T = new Tree(value);																// Записываем новое значение
			}
		}
		else {																						// Если лист не пустой
			add(T->left);																			// Вставляем потомков
			add(T->right);
		}
	}

	void print(Tree* root) {
		if (root == nullptr) {
			return;
		}
		std::cout << root->value << " ";
		print(root->left);
		print(root->right);

	}

	void print_start() {
		std::cout << bin->value << " ";
		print(bin->left);
		print(bin->right);
	}
};




	

int main(){
	Treehouse alpha;
	Treehouse beta;
	alpha.print_start();
	std::cout << std::endl;
	beta.print_start();
	std::cout << std::endl << std::endl;
	std::cout << compare(alpha, beta);
	return 0;
}
  • Вопрос задан
  • 316 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Судя по комментариям, вам надо найти полное совподение поддерева: Так что поддерево вершины имеет ровно столько же точно также расставленных вершин, как и второе дерево.

Умное и быстрое решение, к сожалению, будет сложно написать без std::unordered_map. Такое решение будет работать за O(n). Самостоятельно хеш таблицу писать будет сложно. Но если без хеш таблицы, то решение будет работать также медленно, как и тупое рекурсивное прикладывание, поэтому приведу тут все решение.

Основная идея - надо классифицировать все вершины по форме их поддеревьев. Назначить каждой форме номер. Потом остается только найти вершины с тем же номером, что и корень второго дерева.

Для нумерации форм надо рекурсивно получить номера для двух детей и потом проверить, а встречали ли вы раньше вершину с двумя такими детьми. Если да - то вы знаете ее номер. Если нет - то назначьте новый номер. Вот тут и нужена хеш таблица, она же unordered_map.

Пустые вершины всегда имеют какой-то номер, допустим, 0.

Это решение, кстати, легко адаптируется на изоморфизм - если вам можно менять местами детей. Тогда пары надо отсортировать перед проверкой. Также оно адаптируется на небинарные деревья. Тут у вас будут не пары чисел, а набор чисел.

void Match(Tree *stack, Tree *needle) {
  std::unordered_map<std::pair<int, int>, int> shapes;
  int needle_shape = ClassifyShape(needle, shapes, -1);
  ClassifyShape(stack, shapes, needle_shape);
}

int ClassifyShape(Tree *tree, std::unordered_map<std::pair<int, int>, int> &shape, int find_shape) {
  if(!tree) return 0;
  int l = ClassifyShape(tree->left);
  int r = ClassifyShape(tree->right);
  auto pat = make_pair(l, r);
  auto it =  shapes.find(pat);
  int this_shape = -1;
  if (it == shapes.end()) {
    this_shape = shapes.size();
    shapes[pat] = this_shape;
  } else {
    this_shape =  it->second;
  }
  if (this_shape == find_shape) {
    std::cout << "Found match at node " << tree->value << std::endl;
  }
  return this_shape;
}


В нивном решении надо заменить unordered_map shapes на массив пар чисел (или массив структур или два массива чисел). Циклом в нем проищите текущую пару l, r, если не нашли, то допишите в конец.

Тут можно даже без vector обойтись, потому что вы знаете, сколько максимум будет пар чисел в этом массиве - сколько суммарно вершин деревьях.

Но, возможно вашему преподу такое будет слишком заумно. Тогда вам нужна аккуратная рекурсивная функция сравнения:
bool Compare(Tree* a, Tree *b) {
  if (a->left && !b->left) return false;
  if (a->right && !b->right) return false;
  return (!a->left || Compare(a->left, b->left)) && (!a->right || Compare(a->right, b->right));
}


Тут все просто. Если у корней разная конфигурация детей, то деревья точно не совпали. А дальше надо чтобы рекурсивно совпали поддеревья в левых и правых детях.

А дальше вам надо рекурсивно пройтись по первому дереву и вызвать вот эту Compare для текущей вершины и корня второго дерева. Если совпало - то выводите текущую вершину.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы