二叉树的基础知识（定义和性质、存储结构、遍历）

目录

一、二叉树的定义和性质

1.1 二叉树的定义

1.2 二叉树的性质

二、二叉树的存储结构 

2.1 顺序存储结构 

​2.2 链式存储结构

三、二叉树的遍历 

3.1 DLR先序遍历

3.2 LDR中序遍历

3.3 LRD后序遍历

1.1 二叉树的定义

满足以下两个条件的树结构称为二叉树：

1、每个结点的度都不大于2；

2、每个结点的孩子结点次序不能任意颠倒。

由此定义可看出，一个二叉树中的每个结点只能含有0、1或2个孩子，而且每个孩子有左右之分，位于左边的孩子称为左孩子，位于右边的孩子称为右孩子。

1.2 二叉树的性质

二、二叉树的存储结构 

2.1 顺序存储结构 

用一维数组作存储结构，将二叉树中的结点逐层存放在数组的分量中。 

显然，这种存储方式对于完全二叉树来说是非常方便的。因为对完全二叉树采用顺序存储结构既不浪费空间，又可以根据公式计算出每一个结点的左、右孩子的位置。

但是，对于一般的二叉树，必须用虚结点将其补成一棵完全二叉树来存储，这就会造成空间浪费。这是顺序存储结构的一大缺点。

极端情况：

2.2 链式存储结构

对于任意二叉树来说，每个结点（根除外）只有一个双亲结点，最多有两个孩子。可以设计每个结点至少包含三个域：数据域（Data）、左孩子域（LChild）和右孩子域（RChild）。

如图所示： 

其中，LChild域指向该结点的左孩子，Data域记录该结点的元素值，RChild域指向该结点的右孩子。该结点结构形成的二叉树称为二叉链表。

如图所示：

typedef struct TreeNode {
    DataType data;
    
    struct TreeNode *LChild;
    struct TreeNode *RChild;
} BiTNode, *BiTree;

---

三、二叉树的遍历 

二叉树的基本结构是由根结点、左子树和右子树三个基本单元组成，因此只要依次遍历这三部分，就遍历了整个二叉树。 

二叉树的基本结构： 

用L、D、R分别表示遍历左子树、访问根结点、遍历右子树。

根据对根的访问先后顺序不同，称DLR为先序遍历，LDR为中序遍历，LRD为后序遍历。

3.1 DLR先序遍历

访问根结点，遍历左子树，遍历右子树。

3.2 LDR中序遍历

遍历左子树， 访问根结点，遍历右子树。

3.3 LRD后序遍历

遍历左子树，遍历右子树，访问根结点。