Справочник Томас Ниман Thomas Niemann



Скачать 467.32 Kb.
страница10/12
Дата14.06.2013
Размер467.32 Kb.
ТипДокументы
1   ...   4   5   6   7   8   9   10   11   12

4.6 Коды для бинарных деревьев



typedef int T; /* type of item to be sorted */

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)
typedef struct Node_ {

struct Node_ *left; /* left child */

struct Node_ *right; /* right child */

struct Node_ *parent; /* parent */

T data; /* data stored in node */

} Node;
Node *root = NULL; /* root of binary tree */
Node *insertNode(T data) {

Node *x, *current, *parent;
/***********************************************

* allocate node for data and insert in tree *

***********************************************/
/* find x's parent */

current = root;

parent = 0;

while (current) {

if (compEQ(data, current->data)) return (current);

parent = current;

current = compLT(data, current->data) ?

current->left : current->right;

}
/* setup new node */

if ((x = malloc (sizeof(*x))) == 0) {

fprintf (stderr, "insufficient memory (insertNode)\n");

exit(1);

}

x->data = data;

x->parent = parent;

x->left = NULL;

x->right = NULL;
/* insert x in tree */

if(parent)

if(compLT(x->data, parent->data))

parent->left = x;

else

parent->right = x;

else

root = x;
return(x);

}
void deleteNode(Node *z) {

Node *x, *y;
/*****************************

* delete node z from tree *

*****************************/
/* y will be removed from the parent chain */

if (!z || z == NULL) return;
/* find tree successor */

if (z->left == NULL || z->right == NULL)

y = z;

else {

y = z->right;

while (y->left != NULL) y = y->left;

}
/* x is y's only child */

if (y->left != NULL)

x = y->left;

else

x = y->right;
/* remove y from the parent chain */

if (x) x->parent = y->parent;

if (y->parent)

if (y == y->parent->left)

y->parent->left = x;

else

y->parent->right = x;

else

root = x;
/* y is the node we're removing */

/* z is the data we're removing */

/* if z and y are not the same, replace z with y. */

if (y != z) {

y->left = z->left;

if (y->left) y->left->parent = y;

y->right = z->right;

if (y->right) y->right->parent = y;

y->parent = z->parent;

if (z->parent)

if (z == z->parent->left)

z->parent->left = y;

else

z->parent->right = y;

else

root = y;

free (z);

} else {

free (y);

}

}
Node *findNode(T data) {
/*******************************

* find node containing data *

*******************************/
Node *current = root;

while(current != NULL)

if(compEQ(data, current->data))

return (current);

else

current = compLT(data, current->data) ?

current->left : current->right;

return(0);

}
1   ...   4   5   6   7   8   9   10   11   12

Похожие:

Справочник Томас Ниман Thomas Niemann iconБердникова Дарья Владимировна Лингвистические особенности текстов произведений англо-шотландского фольклора Художественный текст, примером которого является баллада “Thomas the Rhymer” «Томас Рифмоплет»
Художественный текст, примером которого является баллада “Thomas the Rhymer” («Томас Рифмоплет»), несет в себе не только смысловое...
Справочник Томас Ниман Thomas Niemann iconДжефферсон томас
Джефферсон, томас (Jefferson, Thomas) (1743–1826), 3-й президент сша, автор Декларации независимости, архитектор, ученый, просветитель....
Справочник Томас Ниман Thomas Niemann iconТомас Роберт Мальтус Thomas Robert Malthus
Опыт о законе народонаселения и его воздействии на будущее улучшение общества с замечаниями о построениях гг. Годвина, Кондорсе и...
Справочник Томас Ниман Thomas Niemann iconТомас нагель что все это значит? Очень краткое введение в философию Thomas Nagel «What Does It All Mean? A very Short Introduction to Philosophy»
Нагель провел в стенах Корпус Кристи Колледжа в Оксфордском университете (Англия), где имел честь слушать лекции Джона Остина и получить...
Справочник Томас Ниман Thomas Niemann iconСправочник сталкера. Азбука выживания «Справочник сталкера. Азбука выживания»
Этот справочник, вы без труда обнаружите на схеме несколько принципиальных ошибок в действиях группы, приведших в конечном счете...
Справочник Томас Ниман Thomas Niemann iconСправочник Москва, 2004 год Организации социальной направленности района «Академический». Справочник
«Академический» юзао г. Москвы. Справочник, в первую очередь, адресован жителям района и округа, которые могут воспользоваться услугами,...
Справочник Томас Ниман Thomas Niemann iconПроект летней полевой игры по мотивам книги Thomas Malory "Le Morte Darthure"
Проект летней полевой игры по мотивам книги Thomas Malory “Le Morte Darthure” и других источников
Справочник Томас Ниман Thomas Niemann iconТомас гоббс гоббс, томас
Якова I, изучал философию в правление Карла I, был знаменит и находился под подозрением при Кромвеле и, наконец, вошел в моду как...
Справочник Томас Ниман Thomas Niemann iconСправочник по языку c я пишу на c с 1989 года. Этот краткий справочник был составлен мною очень давно

Справочник Томас Ниман Thomas Niemann iconСправочник "Тип мед персоналу" Добавлен новый справочник. Так как в справочник "Тип персоналу"
Тип мед персоналу” (это значение влияет на формирование отчетов). Всем должностям не медицинских специальностей присваивается значение...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org