常见树的存储结构，及如何求以孩子兄弟法存储的森林的叶子结点数

树的存储方式有很多种，既可以采用顺序存储结构，也可以采用链式存储结构，只要能唯一地反映树中的各结点之间的逻辑关系就可以

首先介绍第一种，双亲表示法

双亲表示法：用一片连续空间（数组）来存储每个结点，同时在每个结点中增设一个伪指针（指明其双亲结点在数组中的位置）。因为根结点没有双亲，所以他的伪指针域规定为－1。

#define MAX_TREE_SIZE 100			//树中结点数
typedef struct
{
	ElemType data;
	int parent;						//双亲在数组中的位置域
}PTNode;	//结点

typedef struct
{
	PTNode nodes[MAX_TREE_SIZE];	//双亲
	int n;							//结点数
}PTree;		//树

该存储结构利用了除根结点外每个结点只有唯一双亲的性质，可以利用数组的随机访存性质快速找到双亲，但是如果要求结点的孩子就很麻烦了，需要遍历整张表。

孩子表示法：将每个结点的孩子结点都用单链表横向链接起来，纵向可以用一个线性结构存储每个结点的头指针，n个结点就需要n个孩子链表

特点：寻找孩子结点比较方便，只需要纵向找到待求结点，横向遍历链表找到目标结点即可，但是寻找双亲则需要O(nE)的时间复杂度，几乎把整张庞大的表都遍历了。

孩子兄弟表示法：这种方法不错，又称为二叉树表示法

typedef struct CSNode
{
	EmemType data;
	struct CSNode *first_child, *next_bro;
}CSNode, *CSTree;

这种存储方法比较的灵活，最大的优点是可以很方便地将树转换成二叉树，易于查找结点的孩子，缺点是从当前结点查找双亲结点比较麻烦。解决方法：刚刚ADT里加一个指针，指向parent。

关键点：如何从树转换到二叉树

规则：左孩子右兄弟，每个结点左指针指向第一个孩子，右指针指向它在树中相邻的右兄弟。

Tips：假设n0个叶子结点，则有n0 + 1个右指针为空的二叉树结点（因为包含一个根结点没有右兄弟，或者包含最右边的树的根结点没有右兄弟）

如何求以孩子兄弟表示法存储的森林的叶子结点数？

算法思想：叶子结点等价于左指针为空（即没有孩子了），此算法相当于求二叉树中无左孩子的结点数

算法实现：

typedef struct node
{
	ElemType data;
	struct node *firstChild, *nextBro;
}*Tree;

int getLeavesNum(Tree T)
{
	if(T == NULL)
	{
		return 0;
	}
	if(T->firstChild == NULL)
	{
		//没有左孩子了，则该结点一定是叶子结点
		return 1+getLeavesNum(T->nextBro);	//递归调用，数量累加，看看兄弟还有没有叶子结点
	}
	else
	{
		return getLeavesNum(T->firshChild) + getLeavesNum(T->nextBro);	//孩子子树和兄弟子树叶子树之和
	}
}