Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
 2021-03-17 |
 58 |
из
5.00
|
Заказать работу |
|
|
|
|
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);
}
}
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
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);
}
}
Самоорганизующаяся экспертная система
Кто это? Кот
Чем характеризуется? Маленькое
Счетчики
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
|
|
|
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!