Деревья

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

Элементы дерева связывают между собой таким образом, чтобы каждый узел был связан с корнями своих поддеревьев. Вышестоящий узел называют предком, нижестоящие - поддеревьями или потомками, узлы одного уровня - братьями. Узел, не имеющий поддеревьев, называют концевым узлом, или листом.

Выполнение некоторой операции над всеми элементами дерева называют обходом дерева.

Наиболее распространенными способами представления деревьев в памяти компьютера являются следующие:

а) каждый узел дерева хранит указатель на родительский узел; данный способ удобен, если требуется только подниматься вверх по дереву, но такие ситуации встречаются нечасто; например, реализация данного подхода может быть такой:

struct Node

{

void* data;

int parent_id;

// если некоторые операции требуется выполнять только с //листьями, может оказаться полезным добавить ещё одно //вспомогательное поле

//bool leaf; true, если узел — это лист

};

struct Tree

{

Node nodes[1024];

};

б) если у каждого узла не более некоторого ограниченного количества потомков, то указатели на потомки можно хранить в векторе:

struct Node

{

void *data;

Node* children[10];

};

struct Tree

{ Node* root; };

в) использование списка (как правило, односвязанного) для хранения указателя на потомков; как разновидность такого решения является хранение в каждом узле двух указателей: на одного из потомков и на одного из братьев.

г) обобщение вариантов (а) и (в) как наиболее общее решение;

struct Node

{

void *data;

Node *parent;

Node *child;

Node *brother;

};

struct Tree

{

Node *root;

};

Обход такого дерева может быть осуществлен рекурсивно:

void Action(Node *root)

{

if (node == NULL) return;

/*

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

*/

if (node->brother!=NULL) Action(node->brother);

if (node->child!=NULL) Action(node->child);

}

Обход дерева с использованием очереди приведен ниже

Рис 3.4. Пример структуры «Дерево»

Продемонстрируем вышеуказанные способы представления, используя вместо указателей порядковые номера на примере дерева рис 3.1.

id	data	С хранением номера предка	С хранением номера левого потомка и правого брата
parent	leaf	child	brother
	A		false
	B		false
	C		false
	D		true
	E		true
	F		true
	G		false
	H		true
	I		true
	J		true
	K		false
	L		true