Дерево. Связанное представление.

Представление дерева в памяти машины похоже на представление связанного списка.

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

На первый взгляд может показаться странным то, что каждый узел обладает лишь одним указателем на дочерний узел, в то время как от одного узла может отходить произвольное число дочерних узлов. Однако, наличие указателя на соседний узел, имеющий того же самого родителя («брата» данного узла), позволяет организовать связанный список «детей» этого родительского узла. Благодаря этому родительский узел может содержать указатель только на первый свой подузел.

typedef struct _TREE_ITEM

{

int nItem;

struct _TREE_ITEM *pParent;

struct _TREE_ITEM *pSibling;

struct _TREE_ITEM *pChild;

} TREE_ITEM;

void EmptyTree(TREE_ITEM *pRootItem)

{

LINK_STACK_STRUCT Stack = {NULL};

LINK_STACK_ITEM *pStackItem;

TREE_ITEM *pItem = pRootItem;

while (pItem != NULL)

{

PushLink(&Stack, (int)pItem);

pItem = GetNextItem(pItem);

}

pStackItem = Stack.pHead;

while (pStackItem != NULL)

{

free((void *)pStackItem->nItem);

pStackItem = pStackItem->pNext;

}

EmptyLinkStack(&Stack);

}

Заметим, что для освобождения памяти, занятой деревом, используется стек (его функции описаны в разделе "Стек. Связанное представление"). Это связано с тем, что совершать обход дерева и при этом освобождать память, занятую его узлами, нельзя, поскольку для обхода узлов дерева требуется информация и об их родительских узлах в том числе. Поэтому сначала совершается обход дерева и указатели на все его узлы помещаются в стек, а затем осуществляется их освобождение.

TREE_ITEM *AddItem(TREE_ITEM *pParentItem, int nNewItem)

{

TREE_ITEM *pItem;

TREE_ITEM *pNewItem = malloc(sizeof(TREE_ITEM));

if (pNewItem == NULL)

return NULL;

pNewItem->nItem = nNewItem;

pNewItem->pParent = pParentItem;

pNewItem->pSibling = NULL;

pNewItem->pChild = NULL;

if (pParentItem != NULL)

{

pItem = pParentItem->pChild;

if (pItem == NULL)

pParentItem->pChild = pNewItem;

else

{

while (pItem->pSibling != NULL)

pItem = pItem->pSibling;

pItem->pSibling = pNewItem;

}

}

return pNewItem;

}

TREE_ITEM *GetNextItem(TREE_ITEM *pItem)

{

if (pItem->pChild != NULL)

return pItem->pChild;

else

if (pItem->pSibling != NULL)

return pItem->pSibling;

else

{

while (1)

{

pItem = pItem->pParent;

if (pItem == NULL)

return NULL;

if (pItem->pSibling != NULL)

return pItem->pSibling;

}

}

}

Функция GetNextItem() возвращает следующий узел дерева, идущий после данного. При этом обход осуществляется по следующему алгоритму: если у данного узла есть дочерний узел, переходим к этому дочернему узлу; иначе, если у данного узла есть брат, переходим к этому брату; иначе переходим к родителю узла до тех пор, пока у этого родителя не будет брата, после чего переходим к брату найденного родителя. Если алгоритм доходит до узла, у которого нет ни брата, ни родителя, - это корневой узел. В таком случае обход дерева завершен.

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

TREE_ITEM *pRoot = AddItem(NULL, 1);

TREE_ITEM *pItem11 = AddItem(pRoot, 11);

TREE_ITEM *pItem12 = AddItem(pRoot, 12);

TREE_ITEM *pItem13 = AddItem(pRoot, 13);

TREE_ITEM *pItem121 = AddItem(pItem12, 121);

TREE_ITEM *pItem122 = AddItem(pItem12, 122);

Для того, чтобы осуществить обход всего дерева, выводя при этом на печать значения, хранящиеся в его узлах, можно воспользоваться следующим фрагментом кода:

TREE_ITEM *pItem = pRoot;

while (pItem != NULL)

{

printf("Item %d\n", pItem->nItem);

pItem = GetNextItem(pItem);

}

Использование дерева завершается освобождением памяти, занимаемой им:

EmptyTree(pRoot);

Двоичное дерево, как уже упоминалось, – это дерево, у каждой вершины которого могут быть только два поддерева: левое и правое.

Двоичное дерево можно хранить в памяти точно таким же образом, как и дерево в общем виде. Однако, условие о том, что у каждой вершины может быть не более двух поддеревьев, позволяет упростить его структуру: вместо указателя на дочерний и на соседний узлы можно хранить два указателя на дочерние узлы данного узла. Каждый узел при этом по-прежнему хранит три указателя, однако связи в дереве становятся более простыми.

15. Реализация связанного списка: добавление и удаление элементов, поиск элемента по индексу.

16. Рекурсивный вызов функций. Пример применения.