数据结构:二叉树概念篇(算法基础)

目录

一.有向树的图论基础

1.有向树的相关基本概念

有向树的基本定义:

有向树的结点的度：

有向树的度:

有向树的根结点,分枝结点,叶结点: 

树的子树:

树结点的层次:

树的高度:

2.一个基本的数学结论

3.有序有向树

二.数据结构中树的顺序存储结构与链式存储结构

1.数据结构的物理结构与逻辑结构

2.物理结构为顺序表(数组)的树形数据结构

3. 物理结构为链表的树形数据结构

三.二叉树

1.二叉树基本概念 

2.两个重要的特殊二叉树

3. 关于二叉树的一些常用数学结论

(1).第一组结论 

(2).第二组结论(数组实现二叉树的算法基础)

---

一.有向树的图论基础

基本引理:如果图G(结点数大于等于2)中不存在回路，则至少有一个结点的度为1。 

本篇所讨论的树都是有向树 

1.有向树的相关基本概念

• 有向树的基本定义:

设T是由有限个结点构成的有向简单连通图,且T的无向底图中不存在任何回路,则称T为有向树:

• 有向树的结点的度：

 结点的入度：现有树结点A,以A为终点的有向边的条数称为结点A的入度:

结点的出度: 现有树结点A,以A为起点的有向边的条数称为结点A的出度:

以结点A为终点的有向边的另一端的结点称为A的父结点(parent)

以结点A为起点的有向边的另一端的结点称为A的孩子结点(child)

•  有向树的度:

有向树的度 = 该树所有结点的出度中的最大值:

• 有向树的根结点,分枝结点,叶结点: 

1. 根结点的入度为0
2. 叶结点的出度为0
3. 其余入度和出度均不为0的结点称为树的分枝结点  

•  树的子树:

将一个有向树T的根结点去掉,该树则会被分成若干个互不连通的子树,如图:

上图中T的子树t1,t2,t3都可以再以相同的方式被划分成更小的子树直到树图被划分为若干树叶.

注意：在仅有一个根结点的树形结构中，子树之间没有通路(不然图中会出现回路)

• 树结点的层次:

从根结点开始算起，沿着有向边进行遍历,从根结点到某一个特定结点所遍历的结点个数称为某特定结点的层次

1.  层次相同且父结点相同的结点互为兄弟结点(比如上图中的E和F)
2.  层次相同但父结点不同的结点互为堂兄弟结点(比如上图中的F和G)

• 树的高度:

树的所有结点的层次中的最大值称为该树的高度:比如上图中的树的高度为4

2.一个基本的数学结论

• 关于树的一个基本命题：若树有n个结点，m条有向边，则m=n-1;

该性质可以通过数学归纳法进行证明:

1. 显然n=1时，则m=0，m=n-1成立;
2. 假设n=k(k>=1)时命题成立，即任意具有k个结点的树都有k-1条边。
3. 设树G有n=k+1个结点时(k>=1)，边数为m。 由于G中没有回路，根据基本引理G中必然存在度(出度+入度)为1的结点，设这个结点为u。 从G中删去结点u(相当于同时删去了一条边和一个结点)，根据定义G仍是树，(根据n=k时的假设2)G有k个节点，故有k-1条边，从而m=(k-1)+1=k=n-1(将u结点加回来,边数相应地增加1)。(即若n=k时命题成立则n=k+1时命题也成立,那么从n=1开始构建任意结点数量的树也满足m=n-1)

该证明过程充分体现了树在逻辑上是递推构建起来的图:

分析树的构建图解可知:

• 若构建仅有一个根结点的有向树,则该有向树的每棵子树的根结点有且只有一个父节点，可以有0个或多个孩子结点.
• 同时易知:在仅有一个根结点的树形结构中，一棵树的子树之间不存在通路

3.有序有向树

满树的概念:

• 设(单个根结点)树T的高度为h(h>1),度为k(k>=1)(树的结点个数大于1)
• 树T对应的满树的概念:高度为h且根结点和每一个分枝结点的出度都为k的树。

• 有序有向树的每一个结点都有自己固定的编号

 有序有向树各结点的编号规则:

1. 设现在有一颗高度为h,度为k的(单个根结点的)树T(h>1,,k>=1)
2. 先作出树T对应的满树
3. 将树T对应的满树的各结点按照从低层到高层,从左往右的次序进行编号
4. 根据满树各结点的编号对树T相应位置的结点进行编号

比如:

二.数据结构中树的顺序存储结构与链式存储结构

如果将树的结点看成是一个个内存区块,结点间的有向线段看成是各内存区块之间的关联(这种关联可能是通过指针或者数组下标关系建立起来的),这种在内存中形成的数据结构就是树形数据结构

1.数据结构的物理结构与逻辑结构

• 数据结构的物理结构指的是该数据结构在内存中的真实分布模型
• 数据结构的逻辑结构指的是数据结构的抽象分析模型

数据结构的类型主要取决于其逻辑结构,其逻辑结构和物理结构之间是通过逻辑映射来建立联系的。

2.物理结构为顺序表(数组)的树形数据结构

• 现有一颗度数为2的非满树T
• 我们先将一个树T对应的满树的各个结点按照从低层次到高层次,从左往右的顺序进行编号:
•  由此我们可以得到树T各个结点的编号:
• 根据树T各结点的编号我们就可以将这棵树映射到一个数组上去:
• 通过结点编号与数组下标的绝对映射,我们便可以通过数组来实现树形数据结构(有序有向树) 
• 顺序表实现的树中,非常经典的例子就是堆(大小根堆)

3. 物理结构为链表的树形数据结构

我们可以定义一个结构体类型:

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

• _firstChild1用于指向该结点的第一个孩子结点(编号意义上的第一个(位于左侧))
• _pNextBrother用于指向与该结点位于相同层次且具有相同父结点的兄弟结点

现在有一颗树:

我们用链式存储结构来实现它:

通过_firstChild1指针我们可以实现树的深度遍历

通过_pNextBrother指针我们可以实现树的广度遍历

三.二叉树

1.二叉树基本概念 

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

1. 二叉树的度为2,即不存在出度大于2的结点
2. 二叉树结点的孩子结点有左右之分(左右孩子)，次序不能颠倒，二叉树是有序有向树(各结点都有自己对应的固定编号)

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

2.两个重要的特殊二叉树

• 满二叉树：一个二叉树，如果根结点和每一个分枝结点的出度都为2，则这个二叉树就是满二叉树。从结点总个数角度分析:如果一个二叉树的层数为K，且结点总数是2^k - 1(等比数列求和)，则它就是满二叉树.
• 
• 完全二叉树：完全二叉树是效率很高的数据结构;
  对于高度为K的，有n个结点的二叉树，当且仅当其所有结点编号为1到n连续排列时称之为完全二叉树。(基于完全二叉树的结点编号特点,用数组来实现完全二叉树,内存利用率较高)
• 

完全二叉树有一个特点:

若完全二叉树的高度为k(k>1),则其前k-1层所有结点构成的子结构是一颗满树

• 
• 
•  用数组实现完全二叉树和非完全二叉树的对比:可见完全二叉树的优势所在
•  数据结构堆就是用顺序表(数组)实现的完全二叉树(堆是堆排序算法的结构基础)

3. 关于二叉树的一些常用数学结论

接下来我们给出两组在后续的算法学习中会用到的关于二叉树的数学结论

(1).第一组结论 

• 对任何一棵二叉树, 如果出度为0其叶结点个数为N0, 出度为2的分支结点个数为N2(包括根) ,则有 N0＝ N2＋1

证明:

设该二叉树出度为1的分枝结点个数为N1;

则该二叉树中的总边数为: 2*N2 + N1;

该二叉树中的总结点个数为: N0 + N1 + N2

根据第一章第2小节的基本数学结论有:2*N2 + N1 = N0 + N1 + N2 -1(树的总边数 = 结点数-1)

化简可得:N0 = N2 +1；(即二叉树中,出度为0的树叶永远比出度为2的分枝结点(包括根)多一个)

(2).第二组结论(数组实现二叉树的算法基础)

• 定理一:对于具有n个结点的完全二叉树，按照第一章第3节所述的编号规则将其各结点进行编号(根结点我们规定编为0号,则完全二叉树的各结点编号为0~n-1)，则对于编号为child的结点有如下结论：若child>0，child编号结点的父结点编号parent = (child-1)/2;若child=0 ,该结点无父结点 

定理一证明图解:

• 定理二:对于具有n个结点的完全二叉树，按照第一章第3节所述的编号规则将其各结点进行编号(根结点我们规定编为0号,则完全二叉树的各结点编号为0~n-1)，则对于编号为parent的结点有如下结论:若2*parent+1<n,则可得该结点的左孩子结点编号leftchild = 2*parent+1;若2*parent+1>=n,则该结点无左孩子(该结论是定理一的逆定理)
• 定理三:对于具有n个结点的完全二叉树，按照第一章第3节所述的编号规则将其各结点进行编号(根结点我们规定编为0号,则完全二叉树的各结点编号为0~n-1)，则对于编号为parent的结点有如下结论:若2*parent+2<n,则可得该结点的右孩子结点编号rightchild = 2*parent+2;若2*parent+2>=n则该结点无右孩子(该结论是定理一的逆定理)
• 

定理二和三的证明分析图解:

有了该组定理我们就可以通过一个父结点的编号找到其左右孩子结点的编号,反过来也可以通过孩子结点的编号找到其父结点的编号(该组定理为数组实现二叉树奠定了算法基础)

• 该组定理在后续堆的实现中的堆元素插入删除接口的元素上下调整算法中会用到