本文向给大家分享求子树深度相关知识，同时小编也会对()的树进行解释，如果能解决您在求子树深度方面面临的问题，请收藏关注本站，现在开始吧！
试编写算法,对一棵以孩子兄弟链表
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;
}
}
树使用孩子链表的存储结构的优点之一是()比较方便
//计算孩子链表表示树的深度
int getDepth(CTree T){
int front=rear=tail=-1;//tail为层最后一个结点
ChildPtr queue[maxSize];
ChildPtr p,q;
ChildPtr root=T->nodes[T->r];
queue[++rear]=root;tail++;
if(root){
int depth=0;
while(front<rear){
while(front<tail){
p=queue[++front];
q=p->next;
while(q){//将p结点所有孩子加入队列
queue[++rear]=q;
q=q->next;
}
}
tail=rear;//此时tail为当前p孩子结点层的最后一个结点
depth++;
}
return depth;
}else
return 0;
}
用孩子链表表示法表示下图中的树
int Depth(CTree &T, int i)
{
if (!T.n)//空树
{
return 0;
}
else if (!T.nodes[i].firstchild)//只有根结点且为叶子结点
{
return 1;
}
else//否则树的深度为其各个子树中深度的最大者+1
{
int depth = 0;
for (CNode *p = T.nodes[i].firstchild; p; p = p->next)
{
int temp = Depth(T, p->child);
if (temp > depth)
{
depth = temp;
}
}//求子树的最大深度
return depth + 1;//返回这棵树的深度
}
}
这是第一个
int Max(int a, int b)
{
return a > b ? a : b;
}
int DepthT(CTree &T, int i)//求树的深度
{
if (!T.n)
{
return 0;
}
else if (!T.nodes[i].firstchild)//如果树中只有一个结点
{
return 1;//则深度为1
}
else//否则
{
return DepthF(T,T.nodes[i].firstchild) + 1;
//树的深度为其子树森林的深度+1
}
}
int DepthF(CTree &T,CNode* &FS)//求森林的深度
{
if (!FS)//森林为空
{
return 0;//则深度为0
}
else//否则
{
return Max(DepthT(T, FS->child), DepthF(T, FS->next));
//森林的深度为Max(森林中第一棵树的深度,森林中由其他树所构成的森林
//的深度)
}
}
这是第二个。
选择哪个算法就看你怎么理解了，是把树理解成由一个根结点和其各个子树组成的，还是理解成由一个根结点和其子树森林组成的，如果是理解成第二种，那么你就认为树和森林是相互递归的，树中有森林，森林中有树，那么可以编写相互递归调用的算法，这个算法的思想是：
树的深度：为其子树森林的深度+1，这里要调用求子树森林深度的算法
森林的深度：为森林中第一棵树的深度和森林中由其他树所构成的森林的深度，两个深度的最大者，这里求第一棵树的深度要调用求树深度的算法，而求森林的深度就递归调用自身。
所以这两个算法是相互递归调用的。
也可以不用递归，那么就需要用到栈，但是栈需要记录结点的深度，这样的话只不过是模拟了递归而已。
以上就是与求子树深度以及()的树的相关内容，也是关于试编写算法,对一棵以孩子兄弟链表的分享。看完求子树深度一文后，希望这对大家有所帮助！