以孩子兄弟链表表示法为存储结构，求树的深度和度。

向右看齐 2022-05-28 07:59 192阅读 0赞

## 问题描述 ##

> 1、树以孩子兄弟链表为数据结构，请设计算法，求树的深度。  
> 2、以孩子-兄弟表示法作为树的存储结构，编程求树的度。

## 算法实现 ##

1.  首先是树的数据结构表示，具体就不详细说，很简单。
    
    > 但我做的时候还是有一些问题，那就是不知道怎么具体写构造函数  
    > 解决方法，把树以双亲表示法的形式输入，eg: `data` `parent`
2.  然后是问题的求解  
    【1】、求深度（递归）  
    求根节点的各个子节点的的深度，然后比较子节点深度的最大值，最后还要记得最大值还要加1，因为根节点的高度还没有算。  
    【2】、求高度  
    和上题类似，对根节点的每个子节点计数，求出最大值，最后更根节点的度再比较下，求出最大值
3.  算法实现(一些析构函数，拷贝构造函数之类，以及无关的函数就都没写)

#include<iostream>
    using namespace std;
    template<class ElemType>
    struct childSibling                      // 节点类
    {
        ElemType data;
        childSibling<ElemType> *firstChild;   // 第一个孩子节点
        childSibling<ElemType> *nextSibling;  // 下一个兄弟节点
        childSibling();                       // 构造函数
        childSibling(ElemType val, childSibling<ElemType> *fChild = NULL, childSibling<ElemType> *nSibling = NULL);  // 构造函数
    };
    // 孩子节点的具体实现
    template<class ElemType>
    childSibling<ElemType>::childSibling()
    {
        firstChild = nextSibling = NULL;
    }
    
    template<class ElemType>
    childSibling<ElemType>::childSibling(ElemType val, childSibling<ElemType> *fChild, childSibling<ElemType> *nSibling)
    {
        data = val;
        firstChild = fChild;
        nextSibling = nSibling;
    }
    
    template<class ElemType>
    class childSiblingTree    // 节点树类
    {
        protected:
            childSibling<ElemType> *root;
        public:
            childSiblingTree();
            childSiblingTree(ElemType items[],int parents[], int n);    // 通过双亲表示法的树转化为孩子兄弟链表表示法
            childSibling<ElemType>* childSiblingTreeHelp(ElemType items[],int parents[],int r, int n);     // 有助于构造函数的实现（便于递归）
            childSibling<ElemType>* FirstChild(childSibling<ElemType> *cur);  // 返回cur节点的第一个孩子节点
            childSibling<ElemType>* NextSibling(childSibling<ElemType> *cur);  // 返回下一个兄弟节点
            int getHeigth(childSibling<ElemType> *r);
            int getHeigth();    // 求高度
            int Degree(childSibling<ElemType> *r);
            int Degree();       // 求深度
    };
    
    template<class ElemType>
    childSiblingTree<ElemType>::childSiblingTree()
    {
        root = NULL;    
    }
    
    template<class ElemType>
    childSibling<ElemType>* childSiblingTree<ElemType>::childSiblingTreeHelp(ElemType items[],int parents[], int r,int n)
    {
        if(r >= 0 && r <n){
            childSibling<ElemType> *rt = new childSibling<ElemType>(items[r]);
            childSibling<ElemType> *subRoot, *cur;
            for(int i = 0;i<n;i++){
                if(parents[i] == r){
                    subRoot = childSiblingTreeHelp(items,parents,i,n);
                    if(rt->firstChild == NULL){
                        rt->firstChild = subRoot;
                        cur = subRoot;
                    } else {
                        cur->nextSibling = subRoot;
                        cur = subRoot; 
                    }
                }
            }
            return rt;
        } else{
            return NULL;
        }
    }
    
    template<class ElemType>
    childSiblingTree<ElemType>::childSiblingTree(ElemType items[],int parents[], int n)
    {
        root = childSiblingTreeHelp(items,parents,0,n);
    }
    
    template<class ElemType>
    childSibling<ElemType>* childSiblingTree<ElemType>::FirstChild(childSibling<ElemType> *cur)
    {
        if(cur == NULL){
            return NULL;
        } else {
            return cur->firstChild;
        }
    }
    
    template<class ElemType>
    childSibling<ElemType>* childSiblingTree<ElemType>::NextSibling(childSibling<ElemType> *cur)
    {
        if(cur == NULL){
            return NULL;
        } else {
            return cur->nextSibling;
        }
    }
    
    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;
        }
    }
    
    template<class ElemType>
    int childSiblingTree<ElemType>::getHeigth()
    {
        return getHeigth(root);
    }
    
    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;
        }
    }
    
    template<class ElemType>
    int childSiblingTree<ElemType>::Degree()
    {
        return Degree(root);
    }
    // 测试
    int main()
    {
        char items[] = {
       'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
        int parents[] = {-1, 0, 0, 0, 1, 1, 3, 3};
        int n = 8;
        childSiblingTree<char> t(items, parents, n);
        cout<<"height:"<<t.getHeigth()<<endl;
        cout<<"degree:"<<t.Degree()<<endl;
        return 0;
    }

最后推荐一个好用的网上[IDE][]，我的代码[运行结果][Link 1]

[IDE]: https://ide.geeksforgeeks.org/
[Link 1]: https://ide.geeksforgeeks.org/9RAp3mu1aE