Êîäû äëÿ áèíàðíûõ äåðåâüåâ
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);
}
