编写算法，对一棵一孩子-兄弟链表表示的树的度

有两种算法可以参考

①递归算法，求树的深度的递归定义如下：

如果是空树，则空操作，度定义为0（空操作是指不作任何操作）

否则，如果是没有孩子的根结点，则度为0

否则，设孩子有n个，则树的度为max(n,degree(child1),degree(child2)...degree(childn))

所以由递归定义可以得如下算法：

int Degree(SCTree &T)
{//求树的度
	if (!T || !T->FChild)
	{
		return 0;
	}
	else
	{
		SCTreeNode *s = T->FChild;
		int degree;
		for (degree = 1; s->NextSibling; ++degree)
		{
			s = s->NextSibling;
		}
		for (s = T->FChild; s; s = s->NextSibling)
		{
			int temp = Degree(s);
			if (degree < temp)
				degree = temp;
		}
		return degree;
	}
}//递归算法

算法中变量的类型参考严蔚敏数据结构的教材

②也可以给出非递归算法，时间复杂度为O(n)，常数为1

具体如下：

int Degree(SCTree &T)
{//求树的度的非递归算法
	if (!T || !T->FChild)
		return 0;

	int count = 1;
	int degree = count;
	Queue *Q;

	InitQueue(Q);
	Enqueue(Q, T);
	Enqueue(Q, T->FChild);
	SCTreeNode *child = NULL;
	while (!IsQEmpty(Q))
	{
		if (!child)
		{
			if (count > degree)
			{
				degree = count;
			}
			count = 0;
			Dequeue(Q, child);
			if (!IsQEmpty(Q))
			{
				GetHead(Q, child);
			}
		}
		else
		{
			++count;
			if (child->FChild)
			{
				Enqueue(Q, child->FChild);
			}
			child = child->NextSibling;
		}
	}
	return degree;
}

同样，结构体和变量请参考严蔚敏数据结构的教材，名称可能不一样，但是结构是相同的。

typedef struct TreeNode
{
TreeNode *child;
TreeNode *sibling;
int data;
}TreeNode;
//这是用了递归的思想，需要仔细体会
int GetChildeSiblingTreeDegree(TreeNode *root)
{
//如果当前树的根节点没有孩子和兄弟，那么，该树的度就是0
if (root->child == NULL && root->sibling == NULL)
{
return 0;
}
//如果该树只有兄弟，则该树的度就等效于对他的兄弟分支的子树求度
else if( root->sibling != NULL)
{
return GetChildeSiblingTreeDegree(root->sibling);
}
//如果该树只有孩子，那么先求出该根节点的度，然后再对它孩子分支子树求度，两者取较大者，即该树的度
else if(root->child != NULL)
{
int rootDegree = 1;
TreeNode *p = root->child;

while(p->sibling != NULL)
{
p = p->sibling;
rootDegree++;
}

int childTreeDegree = GetChildeSiblingTreeDegree(root->child);

return rootDegree > childTreeDegree ? rootDegree : childTreeDegree;
}
}