树的概念

• 树是一种非线性的数据结构，他是一种以树形结构进行组织的数据结构，它由一组节点和

连接这些节点的边构成。树最顶部的节点称为根节点，每个非根节点都有且仅有一个父节点，但可以有多个子节点。每个节点的子节点可以有任意个数，

树的相关概念

概念:树+人类亲缘关系描述 (这些相关概念是比较重要的因此我们需要记性理解记忆，我们借租人类亲缘关系来记忆更加得心应手)

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上

图：A是B的父节点

• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A

的孩子节点

• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的

子孙

• 森林：由m（m>0）棵互不相交的树的集合称为森林

• 注意：树形结构中，子树之间不能有交集，否则就不是树形结构

树在实际中的运用

• 作为一种基本的数据结构，树结构在计算机科学中扮演着非常重要的角色，被广泛应用于

各种领域。下面，让我们来看一些关于数据结构树如何在实际中使用的例子.

1.🌳📊🔍搜索引擎中的应用🌳📊🔍

大家在使用搜索引擎的时候，肯定会注意到在输入关键词之后，搜索引擎会迅速返回数以百万计的结果。搜索引擎看似简单的背后，搜集整理海量数据并进行高效检索的能力，建立在树结构的基础上。通过构建一棵巨大的树结构，每个节点代表一个网页，搜索引擎就能够快速地将用户的关键词与树中的每个节点匹配，找到最符合要求的结果并迅速返回给用户。

当然，搜索引擎的树并不是普通的树，而是以倒排索引为基础建立的B树或B+树。但是，不管是什么类型的树，都非常强大且高效！

2.🌳📊🔍文件系统🌳📊🔍

文件系统是我们计算机中使用的组织和存储文件的一种方式。它通常被表示成一个层次结构，也就是一个树。在树形结构中，每个目录都是一个节点，而文件则是这个节点的子节点。通过树形结构，我们可以快速方便地找到需要的文件，提高了文件系统的效率。此外，许多操作系统也使用树来管理进程和内存。

3.🌳📊🔍计算机网络中的应用🌳📊🔍

计算机网络中的路由器是非常重要的设备，它的主要任务是将数据报文从源地址转发到目的地址。而为了快速准确地定位目的地址，路由器就需要使用到一种名为“路由表”的数据结构，而路由表的底层数据结构正是二叉树。

• 所以本章我们主要讲解二叉树.

二叉树

二叉树的概念

• 二叉树是一种由节点和连接构成的数据结构。它由一个根节点开始，它没有父节点，但可

能有左子节点和右子节点。每个节点最多可以有两个子节点，分别称为左子节点和右子节点。如果一个节点没有子节点，则称之为叶子节点。

• 一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

• 二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

特殊的二叉树

• 满二叉树

-满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。如图所示：

• 这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

• 完全二叉树

完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。 对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

大家要自己看完全二叉树的定义，很多人对完全二叉树其实不是真正的懂了。

• 一个典型的例子

相信不少人以为最后一个二叉树是不是完全二叉树都中招了。

二叉树的性质

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

推导过程： (如有看不懂可以跳过推导过程)

假设一颗满二又树高度是h

总节点的个数:

2~0 + 2’1 + 2_2…+2(h-1) = N

2^(h-1) = N

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

推导过程： (如有看不懂可以跳过推导过程)

首先，深度为1的二叉树只有一个根节点，即只有一个结点。

进一步考虑，深度为2的满二叉树则有一个根节点以及两个子节点，共三个结点。深度为3的满二叉树则在深度为2的树的每个节点下面添加两个子节点，使得节点的数量翻倍，即共有7个节点（1+2+4）。

我们可以发现，每个深度为h的满二叉树的结点数，等于前面所有深度的结点数之和，再加上1（根节点）。即：

结点数 = 1 + 2 + 4 + … + 2^h - 1 等于 2^ 0 + 2^1 + 2^2 + … 2^h - 1

因为2^ 0 + 2^1 + 2^2 + … 2^h - 1是一个等比数列，公比为2，所以可以使用等比数列的求和公式：

结点数 = (1 - 2^h)/(1-2) = 2^h - 1

因此，深度为h的满二叉树的结点数是2^h - 1

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

4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2^n + 1

推导过程： (如有看不懂可以跳过推导过程)

假设树的高度是h

假设一颗满二又树高度是h

总节点的个数:

2’0 + 2’1 + 2 '2…+2~(h-1) = N

2~(h-1) = N

h= log2^n + 1

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

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1=n否则无左孩子
3. 若2i+2=n否则无右孩子

二叉树的存储方式

• 二叉树可以链式存储，也可以顺序存储。
  

那么链式存储方式就用指针， 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

• 链式存储

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

链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？

• 顺序存储

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

• 如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

所以大家要了解，用数组依然可以表示二叉树. 所以本章节先讲链式存储二叉树。

• 链式存储结构

// 定义二叉树中存储的数据类型为int
typedef int BTDataType;
// 定义二叉树结点类型
typedef struct BinaryTreeNode
{
    BTDataType data;                    // 节点的数据
    struct BinaryTreeNode* left;        // 指向左子树节点
    struct BinaryTreeNode* right;       // 指向右子树节点
}BTNode;                                // 将该结构体类型命名为BTNode

大家会发现二叉树的定义 和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。