Представление деревьев общего вида

Рассмотрим два варианта представления дерева общего вида. В первом варианте для хранения указателей на сыновей используется массив фиксированной длины:

const int MAXSON=10; // максимально возможное число сыновей

struct NODE {

<поля данных>;

int nSon; // действительное число сыновей узла

NODE *Sons[MAXSON];

};

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

От этого недостатка свободно представление, когда указатели на сыновей находятся в линейном списке. Такая списочная струк­тура содержит два типа узлов – узлы дерева и узлы линейного списка сыновей.

struct SON { // узел списка сыновей

struct NODE *Son; // указатель на сына

struct SON *Next; // указатель на следующий узел

// списка сыновей

};

struct NODE { // узел дерева

<поля данных>;

SON *Sons; // указатель на начало списка сыновей

};

 
 

На рис. 27 изображен пример такого дерева.

Рис.27. Дерево с линейным списком сыновей








Дата добавления: 2014-12-02; просмотров: 1474;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.