#include <stdio.h>
#include <stdlib.h>
int size; //結(jié)點(diǎn)數(shù)量
#define NUM 20
typedef struct tree_node{
struct tree_node* left;
struct tree_node* right;
int item;
}tree_node;
tree_node* splay (int i, tree_node* t) {
tree_node N, *l, *r, *y;
if (t == NULL)
return t;
N.left = N.right = NULL;
l = r = &N;
for (;;)
{
if (i < t->item)
{
if (t->left == NULL)
break;
if (i < t->left->item)
{
y = t->left; /* rotate right */
t->left = y->right;
y->right = t;
t = y;
if (t->left == NULL)
break;
}
r->left = t; /* link right */
r = t;
t = t->left;
} else if (i > t->item)
{
if (t->right == NULL)
break;
if (i > t->right->item)
{
y = t->right; /* rotate left */
t->right = y->left;
y->left = t;
t = y;
if (t->right == NULL)
break;
}
l->right = t; /* link left */
l = t;
t = t->right;
} else {
break;
}
}
l->right = t->left; /* assemble */
r->left = t->right;
t->left = N.right;
t->right = N.left;
return t;
}
/*
**將i插入樹t中,返回樹的根結(jié)點(diǎn)(item值==i)
*/
tree_node* ST_insert(int i, tree_node *t) {
/* Insert i into the tree t, unless it's already there. */
/* Return a pointer to the resulting tree. */
tree_node* node;
node = (tree_node *) malloc (sizeof (tree_node));
if (node == NULL){
printf("Ran out of space\n");
exit(1);
}
node->item = i;
if (t == NULL) {
node->left = node->right = NULL;
size = 1;
return node;
}
t = splay(i,t);
if (i < t->item) { //令t為i的右子樹
node->left = t->left;
node->right = t;
t->left = NULL;
size ++;
return node;
} else if (i > t->item) { //令t為i的左子樹
node->right = t->right;
node->left = t;
t->right = NULL;
size++;
return node;
} else {
free(node); //i值已經(jīng)存在于樹t中
return t;
}
}
/*
**從樹中刪除i,返回樹的根結(jié)點(diǎn)
*/
tree_node* ST_delete(int i, tree_node* t) {
/* Deletes i from the tree if it's there. */
/* Return a pointer to the resulting tree. */
tree_node* x;
if (t==NULL)
return NULL;
t = splay(i,t);
if (i == t->item) { /* found it */
if (t->left == NULL) { //左子樹為空,則x指向右子樹即可
x = t->right;
} else {
x = splay(i, t->left); //查找左子樹中最大結(jié)點(diǎn)max,令右子樹為max的右子樹
x->right = t->right;
}
size--;
free(t);
return x;
}
return t; /* It wasn't there */
}
void ST_inoder_traverse(tree_node* node)
{
if(node != NULL)
{
ST_inoder_traverse(node->left);
printf("%d ", node->item);
ST_inoder_traverse(node->right);
}
}
void ST_pre_traverse(tree_node* node)
{
if(node != NULL)
{
printf("%d ", node->item);
ST_pre_traverse(node->left);
ST_pre_traverse(node->right);
}
}
void main() {
/* A sample use of these functions. Start with the empty tree, */
/* insert some stuff into it, and then delete it */
tree_node* root;
int i;
root = NULL; /* the empty tree */
size = 0;
for(i = 0; i < NUM; i++)
root = ST_insert(rand()%NUM, root);
ST_pre_traverse(root);
printf("\n");
ST_inoder_traverse(root);
for(i = 0; i < NUM; i++)
root = ST_delete(i, root);
printf("\nsize = %d\n", size);
}