Абстрактные типы данных. Реализация дерева общего вида.
Добавлено: 11 май 2009, 18:53
Нужна помощь. Задача - реализовать на языке Си дерево общего вида. Программа для работы с деревом должна уметь
а) Добавить элемент в дерево.
б) Визуализировать дерево.
в) Выполнить некое действие над деревом.
Короче говоря, само дерево я реализовал так - каждый узел struct Node содержит значение элемента в узле - число типа int, и ссылку на сыновей этого узла - линейный однонаправленный список struct List*. Главная проблема теперь - реализовать обход дерева. Вот тут господа, мне и нужна ваша помощь! На буржуйских сайтах по этому поводу ничего не нашёл, везде только бинарные деревья.
Итак, вопрос: как реализовать обход дерева общего вида?
Вот то, что уже написал - из названия функций вроде понятно, что к чему.
а) Добавить элемент в дерево.
б) Визуализировать дерево.
в) Выполнить некое действие над деревом.
Короче говоря, само дерево я реализовал так - каждый узел struct Node содержит значение элемента в узле - число типа int, и ссылку на сыновей этого узла - линейный однонаправленный список struct List*. Главная проблема теперь - реализовать обход дерева. Вот тут господа, мне и нужна ваша помощь! На буржуйских сайтах по этому поводу ничего не нашёл, везде только бинарные деревья.
Итак, вопрос: как реализовать обход дерева общего вида?
Вот то, что уже написал - из названия функций вроде понятно, что к чему.
Код: Выделить всё
#include<stdio.h>
struct Node
{
int Data;
struct List* Descendants;
};
struct List
{
struct Node* Son;
struct List* Next;
};
struct List* CreateList ()
{
struct List* NewList=(struct List*)malloc(sizeof(struct List));
(NewList->Son)=NULL;
(NewList->Next)=NULL;
return NewList;
};
struct List* Last (struct List* Q)
{
while ((Q->Next)!=NULL)
Q=(Q->Next);
return Q;
};
void AddList (struct List* Q, struct List* NewList)
{
(NewList->Next)=(Q->Next);
(Q->Next)=NewList;
};
struct Node* CreateNode(int item)
{
struct Node* NewNode=(struct Node*)malloc(sizeof(struct Node));
(NewNode->Data)=item;
(NewNode->Descendants)=CreateList();
return NewNode;
};
struct Node* Search(struct Node* L)
{
};
int Insert(struct Node* Q, int item)
{
struct Node* P=CreateNode(item);
struct List* New=CreateList();
(New->Son)=P;
if (Q->Descendants->Son==NULL)
Q->Descendants=New;
else
AddList(Last(Q->Descendants), New);
return 0;
};
int Walk (struct Node* N) // Вот этот кусок нужно переписать,
//ну не дружу я с рекуросией!
{
printf (" ");
printf ("%d\n", N->Data);
Walk (N->Descendants->Son);
Walk (N->Descendants->Next->Son);
return 0;
};