本文共 5296 字，大约阅读时间需要 17 分钟。

#include 
   
    #include 
    
     #include 
     
      typedef enum turn_  turn;typedef struct Node_ *Node;typedef struct  Tree_ *Tree;typedef struct  Tree_ *Position;Tree singleLeft(Position pos1);Tree singleRight(Position pos1);Tree doubleLeft(Position pos1);Tree doubleRight(Position  pos1);void initMore(int *n ,...);Position setValue(Position pos, void *data, int value);Position findMin(Tree tree);Position findMax(Tree tree);Tree insert(Tree  tree, Position pos);Position find(Tree tree, int value);void outPut(Position tree);void show(Tree tree, turn tn);enum turn_{	first, middle, last,};struct Node_{		void *data;		int value;		char *user;};struct  Tree_{	Node node;	Tree left;	Tree right;	int hight;};int Hight(Position pos){		if(!pos)			return -1;		else			return pos->hight;}int Max(int a, int b){		return a>b?a:b;}void initTest(Position *pos){		*pos = malloc(sizeof(struct Tree_));		(*pos)->node = NULL;		(*pos)->left=(*pos)->right=NULL;}void initMore(int *n ,...){		va_list ap;		va_start (ap,  n);				int i;		Position *p;		for(i=0; i<*n; i++)		{				p = va_arg(ap, Position*);				(*p) = malloc(sizeof(struct Tree_));				(*p)->node = NULL;				(*p)->left=(*p)->right=NULL;					(*p)->hight = 0;						}		va_end(ap);}Tree init(){		Tree tree = malloc(sizeof(struct Tree_));		if(!tree)		{			printf("init error...\n");				return NULL;		}		tree->node = NULL;		tree->left=tree->right=NULL;				return tree;}Position setValue(Position pos, void *data, int value){		Node node = malloc(sizeof(struct Node_));		pos->node = node;		pos->node->data = data;		pos->node->value = value;		return pos;}Position findMin(Tree tree){		if(tree == NULL)			return NULL;		else if(tree->left == NULL)			return tree;		else				return findMin(tree->left);}Position findMax(Tree tree){		if(tree != NULL)		{				while(tree->right !=NULL)					tree = tree->right;		}		return tree;}Tree insert(Tree  tree, Position pos){		if(tree==NULL)		{			tree = pos;		}		else if(pos->node->value < tree->node->value)		{				tree->left = insert(tree->left, pos);				if((Hight(tree->left) -Hight(tree->right) )>= 2)				{						if(pos->node->value < tree->left->node->value)						{							tree = singleLeft(tree);						}						else						{							tree = doubleLeft(tree);						}				}		}		else if(pos->node->value >tree->node->value)		{				tree->right = insert(tree->right, pos);				if((Hight(tree->right) -Hight(tree->left)) >= 2)				{						if(pos->node->value  >  tree->left->node->value)							tree = singleRight(tree);						else							tree = doubleRight(tree);				}		}				tree->hight = Max(Hight(tree->left), Hight(tree->right)) + 1;		return  tree;}Tree delete(Tree tree, int value){		Position pos;				if(tree == NULL)		{				printf("not found\n");		}		else if(value < tree->node->value)		{				tree->left = delete(tree->left, value);		}		else if(value > tree->node->value)		{				tree->right = delete(tree->right, value);		}		else if( tree->left && tree->right)		{				pos = findMin(tree->right);				tree->node->value = pos->node->value;				tree->node->data = pos->node->data;				tree->right = delete(tree->right, pos->node->value);		}		else		{				pos = tree;				if(tree->left == NULL)				{					tree = tree->right;				}				else if(tree->right == NULL)				{					tree = tree->left;				}					free(pos);			}				return tree;}Tree singleLeft(Position pos1){		Position pos2;		pos2 = pos1->left;				pos1->left = pos2->right;		pos2->right = pos1;				pos1->hight = Max(Hight(pos1->left), Hight(pos1->right))+1;		pos2->hight = Max(Hight(pos2->left), Hight(pos2->right))+1;		return pos2;}Tree singleRight(Position pos1){		Position pos2 = pos1->right;				pos1->right = pos2->left;		pos2->left =  pos1;				pos1->hight = Max(Hight(pos1->left), Hight(pos1->right))+1;		pos2->hight = Max(Hight(pos2->left), Hight(pos2->right))+1;		return pos2;}Tree doubleLeft(Position pos1){		pos1->left = singleRight(pos1->left);				return singleLeft(pos1);}Tree doubleRight(Position  pos1){		pos1->right = singleLeft(pos1->right);				return singleRight(pos1);}Position find(Tree tree, int value){		if(tree == NULL)			return NULL;		else if(value < tree->node->value)			return  find(tree->left, value);		else if(value >  tree->node->value)			return  find(tree->right, value);		else			return tree;}void outPut(Position tree){		printf("%s %d [%d]\n", tree->node->data, tree->node->value, Hight(tree));}void show(Tree tree, turn tn){	switch(tn)	{		case first:		{			if(tree)			{				outPut(tree);				show(tree->left, first);				show(tree->right, first);			}			break;		}		case middle:		{			if(tree)			{				show(tree->left,middle);				outPut(tree);				show(tree->right, middle);			}			break;		}		case last:		{			if(tree)			{				show(tree->left, last);				show(tree->right, last);				outPut(tree);			}			break;		}	}}int main(){		Position   A, B, C, D, E, F, G, H, tree;		int n=8;	initMore(&n, &A, &B, &C, &D, &E, &F, &G, &H);	setValue(A, "A", 1);	setValue(B, "B", 2);	setValue(C, "C", 3);	setValue(D, "D", 4);	setValue(E, "E", 5);	setValue(F, "F", 6);	setValue(G, "G", 7);	setValue(H, "H", 8);	tree = D;	tree = insert(tree, F);	tree = insert(tree, C);	tree = insert(tree, A);	tree = insert(tree, E);	tree = insert(tree, B);	tree = insert(tree, G);	tree = insert(tree, H);		//delete(tree, 7);	//delete(tree, 5);		show(tree, first);	//	printf("%s\n", find(tree,3)->node->data);			return 0;}