一颗树是怎么储存是一个值得思考的问题，不仅仅是储存数据，而且要使得数据之间的关系(比如父子关系)清晰明了，我们一般从顺序表和链表两个方面来开始考虑，不过这里很显然的是顺序表是行不通的，而这里需要用的也不是真正的链表因为它需要有多个后驱指针，我们并不能确定一个结点的子结点的个数，所以不能给确切后驱指针个数，可以考虑使用一个结构体指针数组来储存，不过这样就太麻烦了而且效率低，可能造成空间浪费。这里有一个非常妙的方法，就是把一个结点的所有兄弟结点用一个链表来储存，所以在设计结构体的时候就只需要创建三个成员，一个用来储存数据，一个用来储存它的子结点，另一个用来储存它的兄弟结点。如下：


typedef int DataType;
struct Node
{
    struct Node* firstChild1; // 第一个孩子结点
    struct Node* pNextBrother; // 指向其下一个兄弟结点
    DataType data; // 结点中的数据域
};

四.二叉树

1.二叉树的概念

二叉树指的是度不超过2的树形结构，也就是说一个节点的子节点最多只能有2个。

它是由根结点和一个左子树和右子树组成

所有的二叉树都是由以下这些情况复合而成：

2.现实中的二叉树

3.特殊二叉树

3.1.完全二叉树

完全二叉树：比如一个深度为h的二叉树，那么第h-1层是满的，并且第h层从左到右叶子结点依次存在。

3.2.满二叉树

满二叉树是一种特殊的完全二叉树它指的是最后一层叶子结点是满的一个深度为h的满二叉树结点个数为2^h-1

3.3.堆

堆就是完全二叉树，而且是一种特殊的完全二叉树，它需要满足每一个父节点都大于子节点，称为大堆，或每一个父节点都小于子节点，称为小堆。而对兄弟节点之间的大小关系并没有要求(为此它并不是有序的)。如下：

4.二叉树的存储结构

二叉树的储存一般是用类似链表来储存的，因为能确定一个结点的度是小于等于2的，所以在设计结构体的时候我们用两个后驱指针成员一个指向左孩子，另一个指向右孩子，如下：


typedef int DataType;
struct Node
{
    struct Node* LeftChild; // 左孩子的节点
    struct Node* RightChild; // 右孩子的节点
    DataType data; // 结点中的数据域
};

对于特殊的二叉树完全二叉树有一个更好的储存方法，就是用顺序表来储存，它的一个很大的好处在于知道一个结点可以很容易的算出它父结点和子结点的下标，还有可以随机访问。

父子结点下标计算公式：

左子结点下标 = 父结点下标*2+1

右子结点下标 = 父结点下标*2+2

父结点下标 = (子结点下标-1) / 2

这些公式对堆的学习非常重要，下一章我们开始堆的学习。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/662527