从零开始学数据结构系列之第三章《二叉树的存储结构》

---

二叉树的创建

注意，以下我们表示的是特殊的树：满二叉树

我们这里就简单的了解其中最常用的孩子兄弟表示法。

/*
*data：当前节点存储的信息
*lchild:存储左孩子节点的地址--左子树
*rchild:存储右孩子节点的地址--右子树
*/
typedef struct TreeNode 
{
    char data;
    struct TreeNode* lchild;
    struct TreeNode* rchild;
}TreeNode;
1
2
3
4
5
6
7
8
9
10
11

二叉树的存储结构

二叉树一般可以使用两种存储结构，一种顺序结构，一种链式结构。

顺序存储

​   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

链式存储

​   二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》