数据结构中树的表示方法

小咪咪 2022-08-05 08:23 173阅读 0赞

树：非线性结构

在计算机中，就只有顺序存储和链式存储，但是对于树结构在计算机中的存储，当然可以天马行空能想到的方法很多，但是考虑到充分利用存储空间，这里说三种主要的表示方法

a)双亲表示法：

*  以双亲作为索引关键词的一种表示方法
 *  定义一个结构，对于每个节点，除了存储自身的信息，还存储着其双亲节点的位置

假设一组连续空间存储树的节点，同时在每个节点中，附设一个指示其双亲节点在数组中位置的元素，定义如下：

//树的双亲表示法节点结构定义
    #define MAX_TREE_SIZE 100
    
    typedef int ElemType;
    
    typedef struct
    {
        ElemType data;  //节点位置
        int parent;     //双亲位置
    }PTNode;
    
    typedef struct
    {
        PTNode nodes[MAX_TREE_SIZE];
        int r;  //根的位置
        int n;  //节点数目
    }PTree;

但是，对于该种表示方法，已知孩子节点寻找双亲非常简单，时间复杂度为O(1)，但是对于已知某双亲节点寻找某孩子节点，就需要遍历整个树结构。  
当然可以对上述结构进行改进从而克服该缺点，就是对于每个孩子节点，再附设指示其孩子节点在数组中位置的元素，但是由于各个节点的孩子数不同，就需要根据节点度的最大值来决定需要附设几个指示元素，当然会造成空间的浪费，应了那句话---------提高空间效率便会增加时间复杂度，提高时间效率便会增加空间复杂度。再多说几句，这也就是研究算法的重要原因，如何在解决某个问题的时候，实现效率和复杂度的最优化，找到最好的平衡点。

b)孩子表示法：

类比于上面的双亲表示法，该方法无非就是在每个节点附设存放孩子位置的指示

但是存在一个问题，在上面也曾经提到过，就是每个节点的孩子数目是不一定相同的，甚至差别较大，此时如果单纯按照节点度的最大值来声明足够的空间，则必然造成很大的浪费，针对以上问题，此时可以想到另一种表示方法，就是在每个节点中存储节点的度，按照节点的度来申请空间，但是还是不行阿，这种结构不好统一处理阿，初始化和维护起来难度大，终于找到一种比较NB的表示方法-----多重链表，Po图通俗易懂

![Image 1][]![Image 1][]![Center][]![Center 1][]

#define MAX_TREE_SIZE
    
    typedef char ElemType
    //孩子节点
    typedef struct CTNode
    {
        int child;            //孩子节点下标
        struct CTNode *next;  //指向下一个孩子节点的指针
    }*childPtr;
    //表头节点
    typedef struct
    {
        ElemType data;       //存放在树中的节点的数据
        int parent;          //存放双亲的下标
        childPtr firstChild; //指向第一个孩子的指针
    }CTBox;
    //树结构
    typedef struct
    {
        CTBox nodes[MAX_TREE_SIZE];  //节点数组
        int r;                       //根的位置
        int t;                       //节点数目
    }CTree;

如果想通过孩子找双亲呢，可以结合上一种方法产生双亲孩子表示法

![Image 1][]![Center 2][]

c)孩子兄弟表示法

由于多叉链表法表示不方便，因此被迫无奈采用孩子兄弟表示法（二叉表法），将多叉树转换为二叉树，然后定义数据结构

#define MAX_TREE_SIZE
    
    typedef char ElemType
    //定义节点
    typedef struct CTNode
    {
        ElemType data;       //存放在树中的节点的数据
        CTNode *firstChild;  //存放子节点
        CTNode *nextSibling; //存放其子节点的兄弟节点
    }CTNode,*CTree;

[Image 1]: 
[Center]: https://img-blog.csdn.net/20150910003634900?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220731/3bcd3a98d94949cfb2a4d63fa3b938af.png
[Center 2]: /images/20220731/09a06a5a3020493fbb27ea08afaf3827.png