问题描述：

1、树以孩子兄弟链表为数据结构，请设计算法，求树的深度。
2、树以孩子兄弟链表为数据结构，请设计算法，求树的度。

实现：

1、求深度（递归）：求根节点的各个子节点的的深度，然后比较得出子节点深度的最大值，最后因为根节点的高度还没有算，所以最大值加1。
2、求度：求根节点的各个子节点的度，然后与根节点的度比较，取最大值。

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class ElemType>
int childSiblingTree<ElemType>::getHeigth(childSibling<ElemType> *r)//递归求深度
{
    childSibling<ElemType> *p;
    if(r == NULL){
        return 0;
    } else {
        int max=0, h;
        for(p = FirstChild(r);p!=NULL;p = NextSibling(p)){
            h = getHeigth(p);
            max = (max < h) ? h : max;
        }
        return max+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class ElemType>
int childSiblingTree<ElemType>::Degree(childSibling<ElemType> *r)//递归求度
{
    if(r == NULL){
        return 0;
    } else {
        childSibling<ElemType> *p;
        int max = 0, d = 0;
        for(p = FirstChild(r);p!=NULL;p=NextSibling(p)){
            d++;
            int sub = Degree(p);
            max = (sub < max) ? max : sub;
        }
        return (d < max) ? max : d;
    }
}

最后更新： 2019年10月14日 20:59

原始链接： http://leiii33.github.io/2019/06/25/Tree/