树的存储结构（数据结构学习笔记）

小灰灰 2022-12-28 04:22 361阅读 0赞

### 文章目录 ###

*   *  双亲存储结构
     *   *  双亲存储结构的类型声明：
         *  优缺点
     *  孩子链存储结构
     *   *  孩子链存储结构的类型声明：
         *  优缺点
         *  应用
     *  孩子兄弟链存储结构
     *   *  孩子兄弟链存储结构的类型声明：
         *  优缺点
         *  应用

--------------------

存储树既要存储结点的数据元素本身，又要存储结点之间的逻辑关系。  
因此树的存储分为三种常用的存储方法：**双亲存储结构**、**孩子链存储结构**、**孩子兄弟链存储结构**。

## 双亲存储结构 ##

在每个结点中`除了存储数据元素本身以外，还存储当前结点的双亲位置`

如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

### 双亲存储结构的类型声明： ###

typedef struct
    {
        
        ElemType data;      //存放结点的值
        int parent;         //存放双亲结点的位置
    }PTree[MaxSize];        //PTree为双亲存储结构类型

### 优缺点 ###

*  该存储方式用来**求某个结点的双亲结点非常容易**，但在**求某个结点的孩子结点时需要遍历整个存储结构**。

## 孩子链存储结构 ##

在每个结点中`除了存储数据元素本身以外，还存储当前结点的孩子结点位置`

如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]

### 孩子链存储结构的类型声明： ###

typedef struct  node
    {
        
        ElemType data;                  //结点的值
        struct node *sons[MaxSons];     //指向孩子结点
    }TSonNode                           //孩子链存储结构中的结点类型

### 优缺点 ###

*  该存储方式用来**求某个结点的孩子结点时非常容易**，但在**求某个结点的双亲结点时比较费时，并且树的度较大时存在较多的空指针域**。

### 应用 ###

以孩子链作为树的存储结构，设计一个求树t高度的递归算法。  
递归算法模型分析：

*  if(t=NULL) f(t)=0
 *  其他情况 f(t)=MAX(f§)+1

算法设计：

int TreeHeight1(TSonNode *t)
    {
        
        TSonNode *p;
        int i,h,maxh=0;
        
        if(t==NULL)
            return 0;               //空树返回高度0
        
        for(i=0;i<MaxSons;i++){
             //处理非空树
            p=t->sons[i];           //p指向t的第i+1个孩子结点
            if(p!=NULL){
                    //若存在第t+1个孩子结点
                h=TreeHeight1(p);   //递归处理第t+1个孩子结点的树高度
                if(maxh<h)          //求所有子树的最大高度
                    maxh=h;
            }
        }
        return (maxh+1);            //返回maxh+1
    }

## 孩子兄弟链存储结构 ##

在每个结点中`除了存储数据元素本身以外，还存储当前结点的孩子结点位置以及兄弟结点位置`

如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

### 孩子兄弟链存储结构的类型声明： ###

typedef struct tnode
    {
           
        ElemType data;          //结点的值
        struct tnode *hp;       //指向兄弟
        struct tnode *vp;       //指向孩子结点
    }TSBNode;                   //孩子兄弟链存储结构中的结点类型

### 优缺点 ###

*  该存储方式**通常用来存储二叉树**，缺点和孩子链存储结构一样，**求某个结点的孩子结点时非常容易**，但在**求某个结点的双亲结点时比较费时**。

### 应用 ###

以孩子链作为树的存储结构，设计一个求树t高度的递归算法。  
递归算法模型分析：

*  if(t=NULL) f(t) = 0
 *  其他情况 f(t) = MAX(f§) + 1

算法设计：

int TreeHeight2(TSBNode *t)
    {
        
        TSBNode *p;
        int h,maxh=0;
        
        if(t==NULL)
            return 0;               //空树返回高度0
        
        p=t->vp;                    //p指向第一个孩子结点
        while(p!=NULL){
                     //扫描t的所有子树
            h=TreeHeight2(p);       //递归求子树的高度
            if(maxh<h)              //求出所有子树中的最大高度
                maxh=h;
            p=p->hp;                //继续处理t的其他子树
        }
        return (maxh+1);            //返回maxh+1
    }

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/6959c9763db54c3b95e3c53d82b19f72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201214165857648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201214165904498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70