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);

}