2.3 二叉树的性质（很重要）

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h - 1.

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2，则有 n0＝ n2 ＋1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log 2(n+1)(ps：是log以2

为底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对

于序号为i的结点有：

a. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

b. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子

c. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.4 练习题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）

A 不存在这样的二叉树

B 200

C 198

D 199

此题根据二叉树的性质3：对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2，则有 n0＝ n2 ＋1。

题目中 n2 为 199，按照公式 n0＝ n2 ＋1，n0 = 200，选择 B。

2.下列数据结构中，不适合采用顺序存储结构的是（ A ）

A 非完全二叉树

B 堆

C 队列

D 栈
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ A ）

A n

B n+1

C n-1

D n/2

经此计算，只有A符合，所以选A。

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ B）

A 11

B 10

C 8

D 12

根据满二叉树的结点总数公式：2^h - 1，我们能推出来，完全二叉树的总结点数范围在 [2^(h-1), 2^h-1]。

我们把四个选项带入范围中试一遍，当h = 10的时候，范围为[512, 1023]，在次范围内，因此选 B。

5.一个具有767个节点的完全二叉树，其叶子节点个数为（ B ）

A 383

B 384

C 385

D 386

因此，选B。

在这里我们总结了一个规律：完全二叉树的结点个数为奇数的时，度为1的结点为0，结点个数为偶数的时，度为1的结点为1。

2.5 二叉树的存储结构

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

2.5.1 顺序存储

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

2.5.2 链式存储

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

二叉链：

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
};

三叉链：

// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
};

3、二叉树的顺序结构及实现

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段 。

3.2 堆的概念及结构

堆的概念及结构我们是一篇完整的文章，点击后面的文字跳转

[数据结构 -- C语言] 堆(Heap)堆(Heap)，代码 + 详解。https://blog.csdn.net/Ljy_cx_21_4_3/article/details/131844046?spm=1001.2014.3001.5502

3.3 堆的实现

堆的实现也是一片完整的文章，与概念及结构是一篇，点击后面的文字跳转

[数据结构 -- C语言] 堆(Heap)堆(Heap)，代码 + 详解。https://blog.csdn.net/Ljy_cx_21_4_3/article/details/131844046?spm=1001.2014.3001.5502

3.4 堆的应用

堆的应用包含堆排序，TopK问题，这分别是两篇文章，点击后面的文字跳转
[数据结构 -- 手撕排序算法第四篇] 堆排序，一篇带你搞懂堆排序七大排序算法之堆排序，详解 + 代码。

https://blog.csdn.net/Ljy_cx_21_4_3/article/details/131844046?spm=1001.2014.3001.5502
[数据结构 -- C语言] 堆实现Top-K问题堆实现 Top-K 问题，代码 + 详解。https://blog.csdn.net/Ljy_cx_21_4_3/article/details/131844046?spm=1001.2014.3001.5502

4、二叉树的链式结构的实现

4.1 说明

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式 。

4.1.1 二叉树的创建

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;
    return node1;
}

上述代码中，我们创建的二叉树如下图：


从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

4.2 二叉树的遍历

4.2.1 前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为

根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

下面主要分析前序递归遍历，中序与后序图解类似，同学们可自己动手绘制。

前序遍历递归图解：

由规则我们可以直到，前序遍历是先访问根节点再访问左孩子再访问右孩子。

我们如果要使用前序遍历的方法来遍历整个二叉树，递归展开图如下：

前序遍历结果：1 2 3 4 5 6

中序遍历结果：3 2 1 5 4 6

后序遍历结果：3 2 5 6 4 1

4.2.2 前序、中序以及后序遍历的实现代码

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if (NULL == root)
  {
    printf("N ");
    return;
  }
  printf("%c ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (NULL == root)
  {
    printf("N ");
    return;
  }
  BinaryTreeInOrder(root->left);
  printf("%c ", root->data);
  BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (NULL == root)
  {
    printf("N ");
    return;
  }
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%c ", root->data);
}

4.2.3 层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

对于层序遍历来说，我们不用递归来写，现在的水平也写不了，因此，我们借助队列来实现，队列的规则是先进先出，父节点先进队，父节点出队前，把左孩子与右孩子代入到队列中，此时再出左孩子，左孩子出队时再将左孩子的左右孩子代入队列，不断这样走，走完整个二叉树。 打印的时候，我们取队头元素，打印队头元素，不断取队头打印，直到整个队列为空。

思路图解：