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