데이터 구조의 유 니 버 설 트 리 (아이 형제 표현법)

#ifndef __TREE_H__
#define __TREE_H__

#include "error.h"
#define CHILD 1
#define BROTHER 0 

typedef int TreeData;

//     
typedef struct _treenode
{
	TreeData data;              //   
	struct _treenode *child;      //        
	struct _treenode *brother;      //        
}TreeNode;

//   
typedef struct _tree
{
	int len;                 //      （     ）
	TreeNode *head;             //        
}Tree;

//              

//   
Tree *Create_tree ();

// pos                 ，    1，   0， 01     ，   
//count    ，    （         ）   。
//   ：
//                       
//flag                   
int Insert_Tree(Tree *tree, TreeData data, int pos, int count, int flag);

//   
void Display(Tree *tree);

//    
// pos           ，    1，   0， 01     ，   
//count    ，    （         ）   。
int Delete(Tree *tree, int pos, int count, TreeData *x);

//          
// pos           ，    1，   0， 01     ，   
//count    ，    （         ）   。
int Tree_Get(Tree *tree, int pos, int count, TreeData *x);

//          
int Tree_Clear(Tree* tree);

//      
void Tree_Destroy(Tree* tree);

//         
TreeNode* Tree_Root(Tree* tree);

//      
int Tree_Count(Tree* tree);

//     
int Tree_Height(Tree* tree);

//    
int Tree_Degree(Tree* tree);



#endif   //__TREE_H__ 

#include "tree.h"
#include 
#include 


//   
Tree *Create_tree ()
{
	//     
	Tree *tree = (Tree*)malloc(sizeof(Tree)/sizeof(char));
	if (tree == NULL)
	{
		errno = MALLOC_ERROR;
		return NULL;
	}
	//     
	tree->head = (TreeNode *)malloc(sizeof(TreeNode)/sizeof(char));
	if (tree->head == NULL)
	{
		errno = MALLOC_ERROR;
		free(tree);
		return NULL;
	}
	tree->head->child = NULL;   //          ，     
	tree->head->brother = NULL;   //       
	tree->len = 0;     //      0（     ）
	return tree;
}

// pos                 ，    1，   0， 01     ，   
//count    ，    （         ）   。
//   ：
//                       
//flag                   
int Insert_Tree(Tree *tree, TreeData data, int pos, int count, int flag)
{
	if(tree == NULL || count < 0 || pos < 0 || flag != CHILD && flag != BROTHER)
	{
		errno = ERROR;
		return FALSE;
	}
	//     
	TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)/sizeof(char));
	if (node == NULL)
	{
		errno = MALLOC_ERROR;
		return FALSE;
	}
	//      ，             
	node->data = data;
	node->child = NULL;
	node->brother = NULL;
	if (count == 0)    //     0，        
	{
		tree->head->child = node;
		tree->len++;  //    ，   +1
		return TRUE;
	}
	else
	{
		//       ，       
		TreeNode *tmp = tree->head;
		int way;
		while (count > 0 && tmp != NULL)
		{
			//        ，        
			way = pos & 1;
			pos = pos >> 1;
			if (way == CHILD)
			{
				tmp = tmp->child;
			}
			else
			{
				tmp = tmp->brother;
			}
			count--;
		}
		//tmp               ，tmp   ，   
		if (tmp == NULL)
		{
			errno = OVER_ERROR;
			printf ("    
");
			return FALSE;
		}
		//  flag                    
		if (flag == CHILD)
		{
			tmp->child = node;
		}
		else
		{
			tmp->brother = node;
		}
		tree->len++;  //    ，   +1
	}
	return TRUE;	
}

//    
void r_display(TreeNode *node,int gap)
{
	if (node == NULL)
	{
		return;
	}
	//            
	int i;
	for (i = 0; i < gap;i++)
	{
		printf ("-");
	}
	printf ("%c
",node->data);  //      
	TreeNode * child = node->child;  //         
	//         
	r_display (child,gap+4);
	TreeNode * brother = node->brother; //       
	//         
	r_display (brother,gap);
}

//   
void Display(Tree *tree)
{
	if (tree == NULL)
	{
		errno = ERROR;
		return;
	}
	r_display(tree->head->child,0);
}

//    
void r_delete (Tree* tree,TreeNode* node)
{
	//                ，   
	if (node ==NULL || node->child == NULL && node->brother == NULL)
	{
		return;
	}
	TreeNode* p = node->child;  //       
	r_delete(tree,p);   //       
	if (p != NULL)
	{
		tree->len--;    //    ，   -1
	}
	free(p);             //    
	p = node->brother;   //     
	r_delete(tree,p);   //        
	if (p != NULL)
	{
		tree->len--;
	}
	free(p);           //     
}

//    
// pos           ，    1，   0， 01     ，   
//count    ，    （         ）   。
int Delete(Tree *tree, int pos, int count, TreeData *x)
{
	//       
	if(tree == NULL || x == NULL || count <= 0 || pos <= 0)
	{
		errno = ERROR;
		return FALSE;
	}
	//        ，   
	if(tree->head->child == NULL)
	{
		errno = TREE_EMPTY;
		printf ("    
");
		return FALSE;
	}
	//tmp     ，       。
	TreeNode *tmp = tree->head;
	int way;
	while (count > 1 && tmp != NULL) //               
	{
		way = pos & 1;
		pos = pos >> 1;
		if (way == CHILD)
		{
			tmp = tmp->child;
		}
		else
		{
			tmp = tmp->brother;
		}
		count--;
	}
	//  tmp           ，     ，    
	if (tmp == NULL)
	{
		errno = OVER_ERROR;
		printf ("    
");
		return FALSE;
	}
	way = pos & 1;   //         ，        ，    
	if (way == CHILD)
	{
		if (tmp->child == NULL)
		{
			errno = OVER_ERROR;
			printf ("    
");
			return FALSE;
		}
	}
	else
	{
		if (tmp->brother == NULL)
		{
			errno = OVER_ERROR;
			printf ("    
");
			return FALSE;
		}
	}
	//    ，    
	if (way == CHILD)
	{
		TreeNode* p = tmp->child;
		*x = p->data;
		tmp->child = p->brother;  //             
		p->brother = NULL;    //            
		
		r_delete(tree,p);   //          
		free(p);  //     
		tree->len--;  //       ，     -1
	}
	else
	{
		TreeNode* p = tmp->brother;
		*x = p->data;
		tmp->brother = p->brother;
		p->brother = NULL;
		
		r_delete(tree,p);
		free(p);
		tree->len--;
	}
}

//          
// pos           ，    1，   0， 01     ，   
//count    ，    （         ）   。
int Tree_Get(Tree *tree, int pos, int count, TreeData *x)
{
	//        
	if(tree == NULL || x == NULL || count <= 0 || pos <= 0)
	{
		errno = ERROR;
		return FALSE;
	}
	//       ，       
	TreeNode *tmp = tree->head;
	int way;
	while (count > 0 && tmp != NULL)
	{
		way = pos & 1;
		pos = pos >> 1;
		if (way == CHILD)
		{
			tmp = tmp->child;
		}
		else
		{
			tmp = tmp->brother;
		}
		count--;
	}
	//tmp    ，        ，    
	if (tmp == NULL)
	{
		errno = OVER_ERROR;
		printf ("    
");
		return FALSE;
	}
	*x = tmp->data;
	return TRUE;
	
}

//          
int Tree_Clear(Tree* tree)
{
	if (tree == NULL)
	{
		errno = ERROR;
		return FALSE;
	}
	TreeData x;
	return Delete(tree,1,1,&x);   //     
}

//      
void Tree_Destroy(Tree* tree)
{
	if (tree == NULL)
	{
		errno = ERROR;
		return;
	}
	Tree_Clear(tree);   //   
	free(tree->head);   //      
	free(tree);   //    
}

//         
TreeNode* Tree_Root(Tree* tree)
{
	if (tree == NULL)
	{
		errno = ERROR;
		return;
	}
	return tree->head->child;
}

//      
int Tree_Count(Tree* tree)
{
	if (tree == NULL)
	{
		errno = ERROR;
		return;
	}
	return tree->len;
}

//     
int r_height (TreeNode *node,int gap)
{
	if (node == NULL)
	{
		return gap;
	}
	
	TreeNode * child = node->child;  //         
	int ret = r_height (child,gap+1);   //      ，  +1，       
	TreeNode * brother = node->brother;   //       
	r_height (brother,gap);       //       
	return ret;  //       
}

//     
int Tree_Height(Tree* tree)
{
	if (tree == NULL)
	{
		return FALSE;
	}
	int ret = r_height (tree->head->child,0);
	return ret;
}

//    
int r_degree (TreeNode* node,int deg)
{
	int i = 0;
	if (node == NULL)
	{
		return deg;
	}
	TreeNode* p = node->child;
	if (p != NULL)    //           ，    1
	{
		i++;
	}
	int degtmp = r_degree(p,i);  //   
	p = node->brother;
	if (p != NULL)  //        ， +1
	{
		deg++;
	}
	int tmpdeg = r_degree(p,deg);  //   
	//                      ，         
	return (tmpdeg > degtmp ? tmpdeg : degtmp);
}

//    
int Tree_Degree(Tree* tree)
{
	if (tree == NULL || tree->head == NULL || tree->head->child == NULL)
	{
		return FALSE;
	}
	int deg = r_degree (tree->head->child,0);
	return deg;
}