孩子兄弟表示法

孩子兄弟链存储结构的类型声明

typedef struct CSNode
{
	ElemType data; //数据域
	struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
}CSNode,*CSTree;

• 孩子兄弟链存储结构是为每个结点设计3个域。即一个数据元素域、一个指向该结点的左边第一个孩子结点(长子)的指针域、一个指向该结点的下一个兄弟结点的指针域。由于树的孩子兄弟链存储结构固定有两个指针域，并且这两个指针是有序的(即兄弟域和孩子域不能混淆)，所以孩子兄弟链存储结构实际上是把该树转换为二又树的存储结构。
  
• 优点：可方便地实现树和二又树的相互转换。
• 缺点：从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。

代码实现

#include<stdio.h>
#include<malloc.h>
typedef char ElemType;
#define MaxSize 15
typedef struct CSNode
{
	ElemType data;
	struct CSNode* firstchild, * nextsibling;
}CSNode, * CSTree;
typedef struct
{
	CSNode* data[MaxSize]; //存放栈中的数据元素
	int top; //存放栈顶指针
}SqStack; //顺序栈类型

void InitStack(SqStack*& s) //初始化栈
{
	s = (SqStack*)malloc(sizeof(SqStack)); //分配一个顺序栈空间，首地址存放在s中
	if (s == NULL) printf("内存分配不成功！\n");
	s->top = -1; //栈顶指针置为-1
}

bool EmptyStack(SqStack* s) //判断栈是否为空
{
	return s->top == -1;
}

bool Push(SqStack*& st, CSNode*b) //进栈
{
	if (st->top == MaxSize - 1) return false; //栈满的情况，即栈上溢出
	st->data[++st->top] = b; //栈顶指针先增1，再将元素放在栈顶指针处
	return true;
}

bool Pop(SqStack*& st, CSNode*&b) //出栈
{
	if (st->top == -1) return false; //栈空的情况，即栈下溢出
	b = st->data[st->top--]; //先取栈顶元素，再使栈顶指针减1
	return true;
}

bool GetTop(SqStack* st, CSNode*&b) //取栈顶元素
{
	if (st->top == -1) return false; //栈空的情况，即栈下溢出
	b = st->data[st->top]; //取栈顶元素
	return true;
}

void DestroyStack(SqStack*& s) //销毁栈
{
	free(s);
}

void InitCSTree(CSTree t) //构造空树(初始化树)
{
	t = NULL;
}

void ClearCSTree(CSTree t) //清空树
{
	if (t)
	{
		if (t->firstchild) ClearCSTree(t->firstchild);
		if (t->nextsibling) ClearCSTree(t->nextsibling);
		free(t); //释放根结点
		t = NULL;
	}
}

void DestoryCSTree(CSTree t) //销毁树
{ 
	//此存储结构二叉树无法销毁 
}

bool EmptyCSTree(CSTree t) //判断树是否为空
{
	return t == NULL;
}

bool CreateCSTree(CSTree &t) //按先序序列构造树
{
	char ch;
	scanf("%c", &ch);
	if (ch == '#') t = NULL;
	else
	{
		t = (CSNode*)malloc(sizeof(CSNode));
		if (t == NULL) return false; //分配失败
		t->data = ch;
		CreateCSTree(t->firstchild);
		CreateCSTree(t->nextsibling);
	}
	return true;
}

int CSTreeDegree(CSTree t)
{
	int i = 0, j = 0, max = -1, temp;
	CSTree Q[100]; //临时存放各结点
	if (t != NULL)
	{
		max = 0;
		Q[j++] = t->firstchild;
		while (i < j) //按层序遍历
		{
			temp = 0;
			while (Q[i])
			{
				temp++;
				if (Q[i]->firstchild) Q[j++] = Q[i]->firstchild; //存储有孩子的结点
				Q[i] = Q[i]->nextsibling; //统计本层结点个数
			}
			if (temp > max) max = temp;
			i++;
		}
	}
	return max;
}

int CSTreeDepth(CSTree t) //返回树的深度
{
	int row = 0, max;
	SqStack *st;
	CSTree temp;
	if (t != NULL)
	{
		InitStack(st);
		Push(st, t);
		row = max = 1;
		while (!EmptyStack(st))
		{
			GetTop(st, temp);
			while (temp->firstchild)
			{
				Push(st, temp->firstchild);
				max++;
				if (row < max) row = max;
				GetTop(st, temp);
			}
			Pop(st, temp);
			if (temp->nextsibling) Push(st, temp->nextsibling);
			else
			{
				while (!EmptyStack(st))
				{
					Pop(st, temp);
					max--;
					if (temp->nextsibling)
					{
						Push(st, temp->nextsibling);
						break;
					}
				}
			}
		}
	}
	return row;
}

ElemType CSRoot(CSTree t) //返回树的根结点值
{
	if (t != NULL) return t->data;
	else return '\0';
}

ElemType CSTreeValue(CSTree t, int i) //返回树中第i个结点值(按层序计数)
{
	int j = 0, k= 0, count = 0;
	CSTree Q[100];
	if (t != NULL && i > 0)
	{
		Q[k++] = t;
		while (j < k)
		{
			while (Q[j])
			{
				count++;
				if (count == i) return Q[j]->data;
				if (Q[j]->firstchild) Q[k++] = Q[j]->firstchild;
				Q[j] = Q[j]->nextsibling;
			}
		}
		j++;
	}
	return '\0';
}

CSTree OrderCS(CSTree t, ElemType e) //返回指向结点e的指针，NULL代表无此结点
{
	int i = 0, j = 0, count = 0;
	CSTree Q[100];
	if (t != NULL)
	{
		Q[j++] = t;
		while (i < j)
		{
			while (Q[i] && Q[i]->data != e)
			{
				if (Q[i]->firstchild) Q[j++] = Q[i]->firstchild;
				Q[i] = Q[i]->nextsibling;
			}
			if (Q[i] && Q[i]->data == e) return Q[i];
			i++;
		}
	}
	return NULL;
}

bool CSAssign(CSTree t, ElemType e, ElemType value) //替换结点e的值为value
{
	CSNode* p = OrderCS(t, e);
	if (p != NULL) //找到了e
	{
		p->data = value;
		return true;
	}
	return false;
}

ElemType CSChildValue(CSTree t, ElemType e, int order) //返回结点e的第order个孩子的值(从左至右计数)
{
	int i = 0, j = 0, count = -1;
	CSTree Q[100];
	if (t != NULL)
	{
		Q[j++] = t;
		while (i < j)
		{
			while (Q[i] && Q[i]->data != e)
			{
				if (Q[i]->firstchild) Q[j++] = Q[i]->firstchild;
				Q[i] = Q[i]->nextsibling;
			}
			if (Q[i] && Q[i]->data == e) break;
			i++;
		}
		if (i < j)
		{
			count = 0;
			if (Q[i]->firstchild)
			{
				Q[i] = Q[i]->firstchild;
				while (Q[i])
				{
					count++;
					if (count == order) return Q[i]->data;
					Q[i] = Q[i]->nextsibling;
				}
			}
		}
	}
	return '\0';
}

ElemType SiblingCS(CSTree t, ElemType e, int mark) //返回元素e的左(右)兄弟，mark标记左右
{
	int i = 0, j = 0, m = 0, n = 0;
	CSTree Q[100];
	ElemType key[100] = {};
	if (t != NULL && t->data != e)
	{
		Q[j++] = t;
		key[n++] = t->data;
		while (i < j)
		{
			while (Q[i])
			{
				if (Q[i]->firstchild)
				{
					Q[j++] = Q[i]->firstchild;
					key[n++] = Q[i]->firstchild->data;
				}
				if (mark == 0)
				{
					if (Q[i]->data == e && Q[i]->data == key[m]) return '\0';
					if (Q[i]->nextsibling && Q[i]->nextsibling->data == e) return Q[i]->data;
				}
				else
				{
					if (Q[i]->data == e && Q[i]->nextsibling) return Q[i]->nextsibling->data;
				}
				Q[i] = Q[i]->nextsibling;
			}
			i++;
			m++;
		}
	}
	return '\0';
}

CSNode* CSChildSeat(CSTree t, ElemType e, int i) //返回树中结点e的第i个孩子(层序计数)的指针
{
	ElemType temp;
	CSNode* p = NULL;
	temp = CSChildValue(t, e, i);
	if (temp) p = OrderCS(t, temp);
	return p;
}

int ChildCount(CSTree t, ElemType p) //返回结点p的孩子结点(子树)个数，返回负数代表结点p不存在
{
	int i = 0, j = 0, count = -1;
	CSTree Q[100];
	if (t)
	{
		Q[j++] = t;
		while (i < j)
		{
			while (Q[i] && Q[i]->data != p)
			{
				if (Q[i]->firstchild) Q[j++] = Q[i]->firstchild;
				Q[i] = Q[i]->nextsibling;
			}
			if (Q[i] && Q[i]->data == p) break;
			i++;
		}
		if (i < j) //找到了p	
		{
			count = 0;
			if (Q[i]->firstchild)
			{
				Q[i] = Q[i]->firstchild;
				while (Q[i])
				{
					count++;
					Q[i] = Q[i]->nextsibling;
				}
			}
		}
	}
	return count;
}

bool InsertCSTree(CSTree T, ElemType e, int i, CSTree t) //将树t插入为树t中e结点的第i棵子树(层序计数)，i=0定义为最后一棵子树
{
	int j, k0;
	CSNode* p, * q;
	k0 = ChildCount(t, e);
	if (k0 < 0 || i<0 || i>k0 + 1) return false;
	if (i == 0) j = k0 + 1;
	else j = i;
	if (j == 1)
	{
		p = OrderCS(t, e);
		t->nextsibling = p->firstchild;
		p->firstchild = t;
	}
	else {
		q = CSChildSeat(t, e, j - 1);
		t->nextsibling = q->nextsibling;
		q->nextsibling = t;
	}
	return true;
}

bool DeleteCSTree(CSTree t, ElemType e, int i) //删除树中e结点的第i棵子树
{
	ElemType tmp;
	CSNode *p, *q;
	if (i == 1)
	{
		p = OrderCS(t, e);
		if (!p) return false;
		q = p->firstchild->nextsibling;
		p->firstchild->nextsibling = NULL;
		ClearCSTree(p->firstchild);
		p->firstchild = q;
	}
	else
	{
		p = CSChildSeat(t, e, i - 1);
		if (!p) return false;
		q = p->nextsibling->nextsibling;
		p->nextsibling->nextsibling = NULL;
		ClearCSTree(p->nextsibling);
		p->nextsibling = q;
	}
	return true;
}

void LevelOrder(CSTree t) //层序遍历树
{
	int i = 0, j = 0;
	CSTree Q[100];
	if (t) Q[j++] = t;
	while (i < j)
	{
		while (Q[i])
		{
			printf("%c ", Q[i]->data);
			if (Q[i]->firstchild) Q[j++] = Q[i]->firstchild;
			Q[i] = Q[i]->nextsibling;
		}
		i++;
	}
}

void PreOrder(CSTree t) //前序遍历树
{
	if (t)
	{
		printf("%c ", t->data);
		PreOrder(t->firstchild);
		PreOrder(t->nextsibling);
	}
}

void InOrder(CSTree t) //中序遍历树
{
	if (t)
	{
		InOrder(t->firstchild);
		printf("%c ", t->data);
		InOrder(t->nextsibling);
	}
}

int main()
{
	CSNode* t = NULL;
	InitCSTree(t);
	printf("输入：");
	CreateCSTree(t);
	printf("\n前序遍历树：");
	PreOrder(t);
	printf("\n中序遍历树：");
	InOrder(t);
	printf("\n层次遍历树：");
	LevelOrder(t);
	printf("\n树的根结点为：%c", CSRoot(t));
	printf("\n树的度为：%d", CSTreeDegree(t));
	printf("\n树共有：%d层", CSTreeDepth(t));
	return 0;
}

运行结果