树的储存结构

待我称王封你为后i 2023-05-22 14:25 55阅读 0赞

[数据基本结构概念][Link 1]  
树是一个非线性结构，树或者是空树，或者是由一个根结点和若干棵子树构成，树中结点具有相同数据类型及**层次关系**。  
\*\*实现树的存储结构，关键是什么？  
答：**如何表示节点的双亲与孩子；**  
[树的常用存储方式][Link 2]  
数据结构，树的常用存储方式双亲表示法，孩子表示

## 1.双亲表示法 ##

typedef struct node
    {
         datatype data;//树中结点的数据信息
      int parent;	//该节点的双亲在数组的下标
      }node;
      node treelist[Maxsize];
      int length,root; //root根节点的下标
      树的双亲表示法实质上是一个静态链表。

## 2孩子表示 ##

采用孩子表示法表示一棵树时，树中每个结点除了存储其自

身的值之外，还必须指出其所有子女的位置，即整棵树中所有结  
点的相互关系是通过指明结点子女的位置来体现的，称这种表示  
法为孩子表示法。  
根据子女位置的实现方法不同，孩子表示法分为三种：数组  
方式的孩子表示法、指针方式的孩子表示法 、链表方式的孩子表  
示法 。  
孩子表示法-> **数组方式的孩子表示法**  
数据域，存放该结点的数据信息；  
child\[0\]~child\[m-1\]：下标域，存放该结点的孩子所在的下标

typedef struct node{
        
    dataype data;
    int child[m];
    }treenode;
    treenode tree[Maxsize];
    int root,length;

孩子表示法-> **指针方式的孩子表示法**

typedef struct node{
        
    datatype data;
    struct node*child[m];//指向子女的指针数组
    }node,*tree;
    tree root;//其中root表示指向树根节点的指针

孩子表示法-> **链表方式的孩子表**  
![链表方式的孩子表示法 。][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]

[Link 1]: https://iknow-pic.cdn.bcebos.com/4610b912c8fcc3cee5a16b8a9f45d688d43f2021?x-bce-process=image/resize,m_lfit,w_600,h_800,limit_1
[Link 2]: https://zhidao.baidu.com/question/1610250572159786907.html?fr=iks&word=%CA%B5%CF%D6%CA%F7%B5%C4%B4%E6%B4%A2%BD%E1%B9%B9%2C%B9%D8%BC%FC%CA%C7%CA%B2%C3%B4&ie=gbk
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]: /images/20230521/9c901a96acdf4c3985f0687097f1c195.png