Чтение, сохранение и печать деревьев

1. Сохранение в файле

void SaveTree(FILE *f, tree *t)

{

if (t!=NULL)

{

             fputc(t->ch,f);

             if (t->left)

                        fputc('+',f);    

             else

                        fputc('-',f);     

 

             if (t->right)

                        fputc('+',f);    

             else

                        fputc('-',f);     

 

             SaveTree(f,t->left);

             SaveTree(f,t->right);

}

}

1. Чтение из файла

tree *ReadTree(FILE *f)

{

char ch, ch_l, ch_r;

tree *t;

 

ch=fgetc(f);

ch_l=fgetc(f);

ch_r=fgetc(f);

if (!feof(f))

{

             t = (tree *)malloc(sizeof(tree));

             t->ch=ch;

             t->left=NULL;

             t->right=NULL;

             if (ch_l!= '-')

                        t->left=ReadTree(f);

             if (ch_r!= '-')

                        t->right=ReadTree(f);

}

return t;

}

1. Печать

1

2

3

4

5

 

void PrintTree(tree *t, int n)

{

int i;

if (t!=NULL)

{

             PrintTree(t->right, n+1);

             for (i=0; i<n; i++) putchar(' ');

             printf("%c\n",t->ch);

             PrintTree(t->left, n+1);

}

}

 

x=1

void PrintTree(tree *t, int y)

{

if (t!=NULL)

{

             PrintTree(t->left, y+1);

             gotoxy(x,y); // A[x][y]=t;

             printf("%c",t->ch);

             x++;

             PrintTree(t->right, y+1);

}

}

 

1. Быстрое чтение

 

Самоорганизующаяся экспертная система

Кто это? Кот

Чем характеризуется? Маленькое

Счетчики

a) Число узлов

int n=0;

void Count(tree *t)

{

if (t!=NULL)

{

       n++;

             Count(t->left);

             Count(t->right);

}

}

int Count(tree *t)

{

int r1, r2;

if (t==NULL) return 0;

else

{

             r1=Count(t->left); // t->nl = r1

             r2=Count(t->right); // t->nr = r1

             return (r1+r2+1);

}

}

 

b) Высота

int h=0;

int CountH(tree *t, int n)

{

if (t!=NULL)

{

             if (t->left==NULL && t->right==NULL)

             {

                        if (n>h) h=n;

             }

             CountH(t->left, n+1);

             CountH(t->right, n+1);

}

}

CountH(t, 0);

 

int CountH(tree *t)

{

int r1, r2, r;

if (t==NULL) return 0;

else

{

             if (t->left==NULL && t->right==NULL) return 0;

             else

             {

                        r1=CountH(t->left); // t->nl = r1

                        r2=CountH(t->right); // t->nr = r2

                        if (r1>r2) r=r1+1;

                        else r=r2+1;

                        return r;

             }

}

}

 

Сильноветвящиеся деревья и графы

Представление в памяти

Tree:

Int key;

Tree* brother;

Tree* child;

 

Обходы

a) Дерево

Q – stack или очередь

 

Q<-t;

While (Q!=пусто)

{

t<-Q; обработать(t);

t=t->child;

while (t!=NULL)

{

Q<-t; t=t->brother;

}

}

 

b) Граф

Q – stack или очередь

for(всех u)

u->flag=0;

u->flag=1;

Q<-u;

While (Q!=пусто)

{

u<-Q;

обработать(u);

for (v связанных с u)

{

if (v->flag==0)

{

Q<-v;

v->flag=1;

                   }

}

}

 

 

Деревья двоичного поиска

struct tree{

       int key;

       tree * left;

tree * right;

};

 

tree* Add(tree *t, int x)

{

       if (t==NULL)

       {

                   t=(tree *)malloc(sizeof(tree));

                   t->key=x;

                   t->left=t->right=NULL;

       }

       else

       {

                   if (x<t->key)

                              t->left=Add(t->left,x); 

                   else

                   {

                              if (x>t->key)

                                          t->right=Add(t->right,x); 

                   }

       }

       return t;

}

 

 

tree* del1(tree* &q, tree *p)

{

       tree *r;

 

       if (q->right!=NULL)

       r=del1(q->right,p);

       else

       {

                   p->key=q->key;

                   r=q;

                   q=q->left;

       }

       return r;

}

 

tree* del(tree *t, int x)

{

tree *p;

 

if (t!=NULL)

{

       if (x<t->key)

        t->left=del(t->left,x);

       else

       {

       if (x>t->key)

                    t->right=del(t->right,x);

       else

       {

                    p=t;

                    if (p->right==NULL)

                   t=p->left;

                    else

                    {

                   if (p->left==NULL)

                               t=p->right;

                   else

                               p=del1(p->left,p);

                    }

 

                    free(p);

       }

       }

}

return t;

}

 

Пример: таблица перекрестных ссылок.

 

Деревья с дополнительной информацией

Добавление с поддержкой числа узлов

struct tree{

       int key;

       int number; //число узлов в поддереве

       tree* left;

tree* right;

};

 

int add(tree* &t, int k)

{

       int flag;

 

       if(t == NULL)

       {

                   t=(tree1*)malloc(sizeof(tree1));

                   t->key = k;

                   t->left = t->right = NULL;

                   t-> number = 1; 

                   flag=1;

       }

       else

       {

                   if(k < t->key)

                   {

                              flag = add(t->left, k);

                              if (flag)

                                          t->number += 1;

                   }

                   else

                   {

                              if(k > t->key)

                              {

                                          flag = add(t->right, k);

                                          if (flag)

                                                      t->number += 1;

                              }

                              else

                                          flag=0;

                   }

       }

       return flag;

}

 

К-й наименьший

tree* k_min (tree* t, int k)

{

       int r;

           

       if (t->left)

       {

                   r=t->left->number + 1;

       }

       else

                   r=1;

       if (r!=k)

       {

                   if (k<r)

                              t=k_min(t->left,k);

                   else

                              t=k_min(t->right,k-r);

       }

       return t;

}

Порядковый номер

struct tree{

       int key;

       int number; //число узлов в поддереве

       tree* left;

tree* right;

tree* father;

};

 

int Number(tree *t)

{

       tree *f;

       int r = Size(t); //t->left->number + 1;

           

       while (t!=root)

       {

                   f=t->father;    

                   if (t==f->right)

                              r+=Size(f->left)+1;

                   t=t->father;

       }

       return r;

}         

Рис. 3.1

Пересекающиеся отрезки

struct tree{

       int l;

       int r;

int r_max;

       tree* left;

tree* right;

};

tree* Intersect(tree *t, int l, int r)

{

       tree *p;

       while (t!=NULL && (t->l > r || t->r < l))

       {

                   p=t->left;

                   if (p!=NULL && (p->r_max > l))

                              t=t->left;

                   else

                              t=t->right;

       }

       return t;

}         

 

BSP-tree

 

 

Oct-tree, quad-tree