Задача с бинарным деревом (написать функцию, которая свяжет все узлы на одном уровне:) - C++

@dimkaok · Регистрация: 06.03.2013

Есть бинарное дерево:

C++

struct node 
{
int n; // value of node
struct node *left; // left subtree
struct node *right; // right subtree
struct node *level; // level pointer (node “to the right”)
}

Поля инициализированы нулями. Нужно написать функцию, которая свяжет все узлы на одном уровне:

C++

1	void linkSameLevel(struct node *t);

@xtorne21st · 13.05.2013, 14:49

Не самая лучшая реализация, но всё же лучше чем ничего:
Дерево. Поуровневая связь

@salam · 13.05.2013, 15:39

не понятно, как это делать, имея только right, left? так вы просто зациклите дерево и превратите его в бесполезный расход памяти...

@xtorne21st · 13.05.2013, 15:54

salam, есть ещё и указатель *level на слудующу структуру текущего уровня.

@salam · 13.05.2013, 15:57

поясните тогда механизм связи... что значит в вашем понимании "связать все узлы на одном уровне"

@Ternsip · 13.05.2013, 15:59

Сообщение от dimkaok

которая свяжет все узлы на одном уровне:

Господа, дерево - ациклический связанный граф.
Если вы добавите дугу в дереве на 1 уровне между вершинами, вы гарантированно получите цикл и эта структура перестанет быть деревом!!!

@xtorne21st · 13.05.2013, 16:10

Ternsip, никакого цикла не будет. Обход, добавление узла и т.д. - всё будет работать по прежнему (ни кто не заставляет использовать этот дополнительный указатель для типичных для дерева функций).

@Ternsip · 13.05.2013, 16:26

xtorne21st, странно звучит, ну я придерживаюсь максимальной абстракции, так что связать узлы = добавить ребро в граф, в моём понимании.

Добавлено через 3 минуты
xtorne21st, само собой, всё будет работать, на произвольном графе dfs тоже работает, например. Я говорил, что это не дерево буде, в таком случае.

@xtorne21st интересующийся 304 / 275 / 19 Регистрация: 25.09.2010 Сообщений: 1,056
	13.05.2013, 14:49	#2
	Не самая лучшая реализация, но всё же лучше чем ничего: Дерево. Поуровневая связь 1

@salam 173 / 154 / 17 Регистрация: 10.07.2012 Сообщений: 760
	13.05.2013, 15:39	#3
	не понятно, как это делать, имея только right, left? так вы просто зациклите дерево и превратите его в бесполезный расход памяти... 0

@xtorne21st интересующийся 304 / 275 / 19 Регистрация: 25.09.2010 Сообщений: 1,056
	13.05.2013, 15:54	#4
	salam, есть ещё и указатель *level на слудующу структуру текущего уровня. 0

@salam 173 / 154 / 17 Регистрация: 10.07.2012 Сообщений: 760
	13.05.2013, 15:57	#5
	поясните тогда механизм связи... что значит в вашем понимании "связать все узлы на одном уровне" 0

@Ternsip 661 / 189 / 6 Регистрация: 10.05.2012 Сообщений: 595
	13.05.2013, 15:59	#6
	Сообщение от dimkaok которая свяжет все узлы на одном уровне: Господа, дерево - ациклический связанный граф. Если вы добавите дугу в дереве на 1 уровне между вершинами, вы гарантированно получите цикл и эта структура перестанет быть деревом!!! 0

@xtorne21st интересующийся 304 / 275 / 19 Регистрация: 25.09.2010 Сообщений: 1,056
	13.05.2013, 16:10	#7
	Ternsip, никакого цикла не будет. Обход, добавление узла и т.д. - всё будет работать по прежнему (ни кто не заставляет использовать этот дополнительный указатель для типичных для дерева функций). 0

@Ternsip 661 / 189 / 6 Регистрация: 10.05.2012 Сообщений: 595
	13.05.2013, 16:26	#8
	xtorne21st, странно звучит, ну я придерживаюсь максимальной абстракции, так что связать узлы = добавить ребро в граф, в моём понимании. Добавлено через 3 минуты xtorne21st, само собой, всё будет работать, на произвольном графе dfs тоже работает, например. Я говорил, что это не дерево буде, в таком случае. 1

Опции темы

С++ для начинающих

Задача с бинарным деревом (написать функцию, которая свяжет все узлы на одном уровне:) - C++