数据结构之通用树（孩子兄弟表示法）

孩子兄弟表示法模型，每个结点都有一个指向其第一个孩子的指针，每个结点都有一个指向其第一个右兄弟的指针 。

头文件：

tree.h

#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__ 

源文件：

tree.c

#include "tree.h"
#include <stdio.h>
#include <stdlib.h>


//创建树
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 ("插入越界\n");
			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\n",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 ("此树为空\n");
		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 ("删除越界\n");
		return FALSE;
	}
	way = pos & 1;   //判断最后一步怎么走，若最后一步走向空，删除越界
	if (way == CHILD)
	{
		if (tmp->child == NULL)
		{
			errno = OVER_ERROR;
			printf ("删除越界\n");
			return FALSE;
		}
	}
	else
	{
		if (tmp->brother == NULL)
		{
			errno = OVER_ERROR;
			printf ("删除越界\n");
			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 ("查看越界\n");
		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;
}

关于用孩子兄弟表示法模型实现树以及更多的操作，可以大家一起去实现。