12.3 Представление дерева в виде древовидного списка

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

Рассмотрим реализацию функций для работы с древовидным списком, представленным как контейнер.

Описание элемента древовидного списка. Имеется три указателя: первый указатель на список сыновей, второй указатель на брата справа. Третий указатель - это указатель на любые данные, которые программист устанавливает по своему усмотрению.

typedef struct TagNodeTreeList
{
      struct TagNodeTreeList *down; //указатель на список сыновей
      struct TagNodeTreeList *right; //указатель на соседа справа
      void* data; //данные узла
} NodeTreeList;

Структура, описывающая весь древовидный список.

typedef struct
{
      NodeTreeList *root; //корень дерева
      void *discrip; //описание (используют клиенты)
} KruTreeList;

Описание функций для работы с древовидным списком

1. Функция создания древовидного списка. Выделяется память под структуру KruTreeList и устанавливаются начальные значения элементов структуры. Если памяти не было выделено, то возвращается нулевое значение указателя.

   KruTreeList *CreateTreeList() //создание древовидного списка
   {
         KruTreeList *tl=(KruTreeList *)malloc(sizeof(KruTreeList));
         if(tl==NULL) return NULL;
         tl->root=NULL;
         tl->discrip=NULL;
         return tl;
   }

2. Функция создания узла древовидного списка. На входе подается указатель на данные, который надо записать в элемент древовидного списка. Выделяется память под структуру NodeTreeList, устанавливаются указатели down и right в нулевое значение, указатель на данные записывается в node->data. Возвращается указатель на структуру NodeTreeList.

   NodeTreeList* CreateTreeListNodeData(void* data)
   {
         NodeTreeList *node=(NodeTreeList*)malloc(sizeof(NodeTreeList));
         if(node==NULL) return NULL;
         node->down=NULL;
         node->right=NULL;
         node->data=data;
         return node;
   }

3. Функция копирования узла древовидного списка. На входе подается элемент древовидного списка и указатель на функцию, которая выделяет память под новую копию данных и копирует данные в новый буфер. Первоначально выделяется память под узел, устанавливаются нулевые значения указателей down и right, если указатель на функцию нулевой, то копируется указатель на данные. В противном случае производится копирование путем вызова функции копирования данных и запись адреса копии в поле cnode->data. Функция возвращает адрес копии узла древовидного списка.

NodeTreeList* CopyTreeListNode(NodeTreeList* node, void*(*CopyData)(void *))
{
      NodeTreeList *cnode=(NodeTreeList*)malloc(sizeof(NodeTreeList));
      if(cnode==NULL) return NULL;
      cnode->down=NULL;
      cnode->right=NULL;
      if(CopyData==NULL) cnode->data=node->data;
      else
            cnode->data=CopyData(node->data);
      return cnode;
}

4. Функция копирования поддерева. Функция производит рекурсивный обход древовидного списка и копирует узлы, и устанавливаются соответствующие связи.

NodeTreeList* CopyTreeListSubTree(NodeTreeList* node, void*(*CopyData)(void *))
{
      if(node==NULL) return NULL;
      NodeTreeList* cnode=CopyTreeListNode(node,CopyData);
      //копируем узел
      if(cnode==NULL) return NULL;
      cnode->down=CopyTreeListSubTree(node->down,CopyData);
      //копируем поддерево
      cnode->right=CopyTreeListSubTree(node->right,CopyData);
      //копируем правого узла
      return cnode;
}

5. Функция вставки узла как самого левого сына. На входе задан адрес узла, к которому вставляется новый узел с данными, адрес которых помещен в указатель data.

void AddTreeListNodeLeftSonData(NodeTreeList *node, void *data)
{
      NodeTreeList *son;
      if(node==NULL) return;
      son=CreateTreeListNode(data);
      if(son==NULL) return;
      if(node->down==NULL) //у узла нет сыновей
      node->down=son;
      else //у узла имеются сыновья
      {
            son->right=node->down;
            node->down=son;
      }
}

6. Функция вставки поддерева, корень которого записывается как самый левый сын указанного узла. На входе заданы: узел node и корень поддерева son.

void AddTreeListNodeLeftSon(NodeTreeList *node, NodeTreeList *son)
{
      if(node==NULL||son==NULL) return;
      if(node->down==NULL) //у узла нет сыновей
            node->down=son;
      else //у узла имеются сыновья
      {
            son->right=node->down;
            node->down=son;
      }
}

7. Функция вставки узла как самого правого сына. На входе задан адрес узла, к которому вставляется новый узел с данными, адрес которых помещен в указатель data.

void AddTreeListNodeRightSonData(NodeTreeList *node, void *data)
{
      NodeTreeList *son;
      if(node==NULL) return;
      son=CreateTreeListNode(data); //создаем новый узел
      if(son==NULL) return;
      if(node->down==NULL) //у узла нет сыновей
            node->down=son;
      else //у узла имеются сыновья
      {
            NodeTreeList *s=node->down;
            while(s->right!=NULL) s=s->right; //находим правого сына
            s->right=son;
      }
}

8. Функция вставки поддерева, корень которого записывается как самый правый сын указанного узла. На входе заданы: узел node и корень поддерева son.

void AddTreeListNodeRightSon(NodeTreeList *node, NodeTreeList *son)
{
      if(node==NULL||son==NULL) return;
      if(node->down==NULL) //у узла нет сыновей
            node->down=son;
      else //у узла имеются сыновья
      {
            NodeTreeList *s=node->down;
            while(s->right!=NULL) s=s->right; //находим самого правого сына
            s->right=son;
      }
}

9. Функция удаления поддерева узла. На входе указывается указатель на корень поддерева и указатель на функцию удаления данных DeleteData. Производится рекурсивный обход поддерева и удаление узлов вместе с данными.

void DeleteSubTreeList(NodeTreeList *node, void(*DeleteData)(void*))
{
      if(node==NULL) return;
      DeleteSubTreeList(node->down,DeleteData); //удалить левого сына
      DeleteSubTreeList(node->right,DeleteData); //удалить правого брата
      DeleteData(node->data); //удалить данные узла
      free(node); //удалить узел
}

10. Функция удаления сына вместе c поддеревом. Первоначально удаляется поддерево, затем корректируются связи, в зависимости от расположения узла и удаляется сам узел.

void DeleteSonTreeList(NodeTreeList *node, NodeTreeList *son,void(*DeleteData)(void*))
{
      if(node==NULL) DeleteSubTreeList(son, DeleteData);
      //удаление всего дерева
      else //найти соседей
      {
            if(node->down==son) //самый левый сын
                  node->down=son->right; //у родителя изменяем связь на левого сына
            else //найти брата слева
            {
                  NodeTreeList *s=node->down;
                  while(s!=NULL)
                        if(s->right==son) break; //нашли левого брата
                        else s=s->right;
                  if(s==NULL) return; //Ошибка: son не является сыном node
                  else s->right=son->right;
            }
            DeleteSubTreeList(son->down,DeleteData);
            //удаление поддрева
            DeleteData(son->data);
            free(son);
      }
}

11. Функция левостороннего обхода для всех узлов поддерева node. При этом для каждого узла вызывается функция, адрес которой записан в указателе func.

void ForEachTreeListLeftNode(NodeTreeList *node, void(*func)(void*))
{
      if(node==NULL) return;
      func(node->data);
      ForEachTreeListLeftNode(node->down,func);
      ForEachTreeListLeftNode(node->right,func);
}

12. Функция левостороннего обхода для всех узлов поддерева node. При этом для каждого листа вызывается функция, адрес которой записан в указателе func.

void ForEachTreeListLeftLeaf(NodeTreeList *node, void(*func)(void*))
{
      if(node==NULL) return;
      if(node->down!=NULL)
            ForEachTreeListLeftLeaf(node->down,func);
      else
            func(node->data); //это лист
      if(node->right!=NULL)
            ForEachTreeListLeftLeaf(node->right,func);
}

13. Функция поиска на всех узлах дерева. На входе подается адрес поддерева, указатель на функцию сравнения. Параметр param. Функция Compare(node- >data,param) на входе принимает адрес узла и указатель param, производит сравнение и если возвращает 1, то поиск прекращается. Функция Compare пишется в зависимости от целей поиска и структуры данных.

void* FindTreeListLeftNode(NodeTreeList *node, int (*Compare)(void*,void*),void* param)
{
      if(node==NULL) return NULL; 
      if(Compare(node->data,param)) return node->data;
      if(!FindTreeListLeftNode(node->down,Compare,param))
            return node->data;
      return FindTreeListLeftNode(node->right,Compare,param);
}

14. Функция аналогична FindTreeListLeftNode, только поиск осуществляется для листьев.

void* FindTreeListLeftLeaf(NodeTreeList *node, int(*Compare)(void*,void*),void* param)
{
      if(node==NULL) return NULL;
      if(node->down!=NULL)
            FindTreeListLeftLeaf(node->down,Compare,param);
      else
            if(Compare(node->data,param) return node->data; //это лист
      if(node->right!=NULL)
            FindTreeListLeftLeaf(node->right,Compare,param);
}

15. Механизм конструирования деревьев на основе строки формата. Пусть имеется следующая грамматика, описывающая строку формата, задающую описание дерева в скобочной записи.
    1. format=>node(node ,node,...node)
    2. node => node(node, node,...node)
    3. node=>%n
    4. node=>%v
    5. node=>string

    node может быть описан строкой (string), параметр типа переменная string (%v), типа узел (%n).

    Примеры записи формата

    1. A(B,C(D,E)) – описание дерева без параметров
    2. D(X(%v,C)) – описывается дерево с одним параметром типа string.
    3. V(X,%n,D(F,%v) - описывается дерево с двумя параметрами

    Функция преобразования строки формата в древовидный список

void TranslateAscizToTreeList(TranslateStateTreeList *ts, char *format,...);
1.TranslateAscizToTreeList(ts,"A(B,C(D,E))");
2.TranslateAscizToTreeList(ts, "D(X(%v,C))", "Hello");
3.TranslateAscizToTreeList(ts, "V(X,%n,D(F,%v)",node_ptr, "Hi");

#define SIZEPARAMS 10
Объединение указателей
typedef union
{
      void *pdata; // v - указатель на любые данные
      NodeTreeList *pnode; // n - указатель на узел
} KruVariantTreeList;

Описание структуры состояния трансляции

typedef struct
{
      void* (*CreateData)(char*); //функция работающая с именем
      KruVariantTreeList params[SIZEPARAMS]; //вектор параметры
      int size_params; //количество параметров в стеке
      char *string; //описание дерева
      int size_name; //длина имени
      char *name; //имя
      int top_param; //текущий параметр
      int top; //текущий символ в имени
      char open_parenthes; //скобка (
      char close_parenthes; //скобка )
      char comma; //запятая
      char procent; //заменитель процента
} TranslateStateTreeList;

Функция создание структуры TranslateStateTreeList

void InitTranslateStateTreeList(TranslateStateTreeList *ts, int size_name,void*(CreateData(char*)))
{
      ts->CreateData=CreateData;
      ts->name=new char[size_name+1];
      ts->size_name=size_name;
      ts->open_parenthes=’(’;
      ts->close_parenthes=’)’;
      ts->comma=’,’;
      ts->procent=’%’;
}

Функция удаления структуры TranslateStateTreeList

void DeleteTranslateStateTreeList(TranslateStateTreeList *ts)
{
      delete []ts->name;
}

Функция переопределения разделителей

void SetPunctuators(TranslateStateTreeList *ts, char openp,char closep,char comma,char procent)
{
      ts->open_parenthes=openp; //переопределение скобки открывающей
      ts->close_parenthes=closep;//переопределение скобки закрывающей
      ts->comma=comma;
      ts->procent=procent;
}

Функция сообщения об ошибке

void TranslateError(char *err)
{
      printf("%s\n",err);
}

Функция конструирования древовидного списка

NodeTreeList *TranslateAscizToTreeList(TranslateStateTreeList *ts,char *format,...)
{
      ts->string=format; //начальные установки
      char *ch=ts->string;
      ts->size_params=0;
      ts->top_param=0;
      va_list ap;
      va_start(ap,format);
      while(*ch)
      { //взять все параметры из стека и занести в вектор параметров
            if(*ch==ts->procent) {//это процент (взять параметр)
                  if(ts->size_params<SIZEPARAMS)
                  {
                        ch++;
                        switch(*ch) { //взять параметры из стека
                             case ’n’:{ //указатель на узел
                                   ts->params[ts->size_params++].pnode = va_arg(ap,NodeTreeList*);
                                   break;
                              }
                             case ’v’:{ //указатель на любые данные
                                   ts->params[ts->size_params++].pdata =
                                   va_arg(ap,void*);
                                   break;
                             }
                        } //endswitch
                  }
            } //endifch
            else ch++;
      }//end while
      NodeTreeList *node=AscizToTreeList(ts);//рекурсивный разбор строки
      return node;
}

Функция рекурсивного разбора строки и конструирования древовидного списка

NodeTreeList *AscizToTreeList(TranslateStateTreeList *ts)
{
      NodeTreeList *node=NULL;
      ts->top=0;
      while(*ts->string){ //выделить имя узла
            if(*ts->string==ts->open_parenthes) break; //это скобка (
            else
                  if(*ts->string==ts->comma) break;//это запятая
                  else
                        if(*ts->string==ts->close_parenthes) break;
                        else
                             if(ts->top<ts->size_name-1) ts->name[ts->top++]=*ts->string+
                             else ts->string++;//если имя длинное просто пропускаем
      }
      ///////////
      if(ts->top>0) { //имя узла выделено
            ts->name[ts->top]=0;
            if(ts->name[0]==ts->procent) { //это параметр
                  switch(ts->name[1]) { //определить тип параметра
                        case ’v’: //создать новый узел
                             if(ts->top_param<ts->size_params)
                                   node=CreateTreeListNode((void*)(ts->params[ts->top_param++].pdata));
                        break;
                        case ’n’: //узел должен быть корнем (вставить поддерево)
                             if(ts->top_param<ts->size_params)
                                   node=ts->params[ts->top_param++].pnode;
                        break;
                  }
            }
            else{//это имя
                  if(ts->CreateData!=NULL) //если функция есть
                        node=CreateTreeListNode(ts->CreateData(ts->name));
            }
      }
      else {
            TranslateError("No name of node");
            return NULL;
      }
      //узел создан
      if(*ts->string==’\0’) return node;
      else
            if(*ts->string==ts->open_parenthes) {//скобка открывающая
                  ts->string++;
                  node->down=AscizToTreeList(ts);
                  if(*ts->string==ts->close_parenthes) ts->string++;
            }
      if(*ts->string==ts->comma) {//это запятая
            ts->string++;
            node->right=AscizToTreeList(ts);
      }
      if(*ts->string==ts->close_parenthes)return node;
      return node;
}