01. 树与二叉树的基础知识
01. 树与二叉树的基础知识
1. 树简介
1.1 树的定义
树(Tree):由
个节点与节点之间的关系组成的有限集合。当 时称为空树,当 时称为非空树。
之所以把这种数据结构称为「树」是因为这种数据结构看起来就像是一棵倒挂的树,也就是说数据结构中的「树」是根朝上,而叶朝下的。如下图所示。
「树」具有以下的特点:
- 有且仅有一个节点没有前驱节点,该节点被称为树的 「根节点(Root)」 。
- 除了根节点以之,每个节点有且仅有一个直接前驱节点。
- 包括根节点在内,每个节点可以有多个后继节点。
- 当
时,除了根节点之外的其他节点,可分为 个互不相交的有限集合 ,其中每一个集合本身又是一棵树,并且被称为根的 「子树(SubTree)」。
如下图所示,红色节点
1.2 树的相关术语
下面我们来介绍一下树结构中的一些基本术语。
1.2.1 节点分类
「树的节点」 由一个数据元素和若干个指向其子树的树的分支组成。而节点所含有的子树个数称为 「节点的度」。度为
- 树的节点:由一个数据元素和若干个指向其子树的树的分支组成。
- 节点的度:一个节点所含有的子树个数。
- 叶子节点(终端节点):度为
的节点。例如图中叶子节点为 、 、 、 、 、 。 - 分支节点(非终端节点):度不为
的节点。例如图中分支节点为 、 、 、 、 。 - 树的度:树中节点的最大度数。例如图中树的度为
。
1.2.2 节点间关系
一个节点的子树的根节点称为该节点的 「孩子节点」,相应的,该节点称为孩子的 「父亲节点」。同一个父亲节点的孩子节点之间互称为 「兄弟节点」。
- 孩子节点(子节点):一个节点含有的子树的根节点称为该节点的子节点。例如图中
是 的孩子节点。 - 父亲节点(父节点):如果一个节点含有子节点,则这个节点称为其子节点的父节点。例如图中
是 的父亲节点。 - 兄弟节点:具有相同父节点的节点互称为兄弟节点。例如图中
、 互为兄弟节点。
1.2.3 树的其他术语
「节点的层次」 是从根节点开始定义,将根节点作为第 1 层,根的孩子节点作为第 2 层,以此类推,如果某个节点在第
- 节点的层次:从根节点开始定义,根为第
层,根的子节点为第 层,以此类推。 - 树的深度(高度):所有节点中最大的层数。例如图中树的深度为
。 - 堂兄弟节点:父节点在同一层的节点互为堂兄弟。例如图中
、 互为堂兄弟节点。 - 路径:树中两个节点之间所经过的节点序列。例如图中
到 的路径为 。 - 路径长度:两个节点之间路径上经过的边数。例如图中
到 的路径长度为 。 - 节点的祖先:从该节点到根节点所经过的所有节点,被称为该节点的祖先。例如图中
的祖先为 、 、 。 - 节点的子孙:节点的子树中所有节点被称为该节点的子孙。例如图中
的子孙为 、 、 。
1.3 树的分类
根据节点的子树是否可以互换位置,我们可以将树分为两种类型:「有序树」 和 「无序树」。
如果将树中节点的各个子树看做是从左到右是依次有序的(即不能互换),则称该树为 「有序树」。反之,如果节点的各个子树可以互换位置,则成该树为 「无序树」。
- 有序树:节点的各个⼦树从左⾄右有序, 不能互换位置。
- 无序树:节点的各个⼦树可互换位置。
2. 二叉树简介
2.1 二叉树的定义
二叉树(Binary Tree):树中各个节点的度不大于
个的有序树,称为二叉树。通常树中的分支节点被称为 「左子树」 或 「右子树」。二叉树的分支具有左右次序,不能随意互换位置。
下图就是一棵二叉树。
二叉树也可以使用递归方式来定义,即二叉树满足以下两个要求之一:
- 空树:二叉树是一棵空树。
- 非空树:二叉树是由一个根节点和两棵互不相交的子树
、 ,分别称为根节点的左子树、右子树组成的非空树;并且 、 本身都是二叉树。
⼆叉树是种特殊的树,它最多有两个⼦树,分别为左⼦树和右⼦树,并且两个子树是有序的,不可以互换。也就是说,在⼆叉树中不存在度⼤于
二叉树在逻辑上可以分为
2.2 特殊的二叉树
下面我们来介绍一些特殊的二叉树。
2.2.1 满二叉树
满二叉树(Full Binary Tree):如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层上,则称该二叉树为满二叉树。
满二叉树满足以下特点:
- 叶子节点只出现在最下面一层。
- 非叶子节点的度一定为
。 - 在同等深度的二叉树中,满二叉树的节点个数最多,叶子节点个数最多。
如果我们对满二叉树的节点进行编号,根节点编号为
我们可以来看几个例子。
2.2.2 完全二叉树
完全二叉树(Complete Binary Tree):如果叶子节点只能出现在最下面两层,并且最下层的叶子节点都依次排列在该层最左边的位置上,具有这种特点的二叉树称为完全二叉树。
完全二叉树满足以下特点:
- 叶子节点只能出现在最下面两层。
- 最下层的叶子节点一定集中在该层最左边的位置上。
- 倒数第二层如果有叶子节点,则该层的叶子节点一定集中在右边的位置上。
- 如果节点的度为
,则该节点只偶遇左孩子节点,即不存在只有右子树的情况。 - 同等节点数的二叉树中,完全二叉树的深度最小。
完全二叉树也可以使用类似满二叉树的节点编号的方式来定义。即从根节点编号为
我们可以来看几个例子。
2.2.3 二叉搜索树
二叉搜索树(Binary Search Tree):也叫做二叉查找树、有序二叉树或者排序二叉树。是指一棵空树或者具有下列性质的二叉树:
- 如果任意节点的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。
- 如果任意节点的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。
- 任意节点的左子树、右子树均为二叉搜索树。
如图所示,这
2.2.4 平衡二叉搜索树
平衡二叉搜索树(Balanced Binary Tree):一种结构平衡的二叉搜索树。即叶节点高度差的绝对值不超过
,并且左右两个子树都是一棵平衡二叉搜索树。平衡二叉树可以在 内完成插入、查找和删除操作。最早被发明的平衡二叉搜索树为 「AVL 树(Adelson-Velsky and Landis Tree))」。 AVL 树满足以下性质:
- 空二叉树是一棵 AVL 树。
- 如果 T 是一棵 AVL 树,那么其左右子树也是 AVL 树,并且
, 是左子树的高度, 是右子树的高度。 - AVL 树的高度为
。
如图所示,前
2.3 二叉树的存储结构
二叉树的存储结构分为两种:「顺序存储结构」和「链式存储结构」,下面进行一一讲解。
2.3.1 二叉树的顺序存储结构
其实,堆排序、优先队列中的二叉堆结构,采用的就是二叉树的顺序存储结构。
二叉树的顺序存储结构使用一维数组来存储二叉树中的节点,节点存储位置则采用完全二叉树的节点层次编号,按照层次从上至下,每一层从左至右的顺序依次存放二叉树的数据元素。在进行顺序存储时,如果对应的二叉树节点不存在,则设置为「空节点」。
下图为二叉树的顺序存储结构。
从图中我们也可以看出节点之间的逻辑关系。
- 如果某二叉树节点(非叶子节点)的下标为
,那么其左孩子节点下标为 ,右孩子节点下标为 。 - 如果某二叉树节点(非根节点)的下标为
,那么其根节点下标为 。 表示整除。
对于完全二叉树(尤其是满二叉树)来说,采用顺序存储结构比较合适,它能充分利用存储空间;而对于一般二叉树,如果需要设置很多的「空节点」,则采用顺序存储结构就会浪费很多存储空间。并且,由于顺序存储结构固有的一些缺陷,会使得二叉树的插入、删除等操作不方便,效率也比较低。对于二叉树来说,当树的形态和大小经常发生动态变化时,更适合采用链式存储结构。
2.3.2 二叉树的链式存储结构
二叉树采用链式存储结构时,每个链节点包含一个用于数据域
二叉链节点结构的对应代码为:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
下面我们将值为
二叉树的链表存储结构具有灵活、方便的特点。节点的最大数目只受系统最大可存储空间的限制。一般情况下,二叉树的链表存储结构比顺序存储结构更省空间(用于存储指针域的空间开销只是二叉树中节点数的线性函数),而且对于二叉树实施相关操作也很方便,因此,一般我们使用链式存储结构来存储二叉树。
参考链接
- 【书籍】数据结构教程 第 3 版 - 唐发根 著
- 【书籍】大话数据结构 程杰 著
- 【书籍】算法训练营 陈小玉 著
- 【博文】二叉树理论基础 - 代码随想录
- 【博文】二叉树基础 - 袁厨的算法小屋
来源:https://github.com/itcharge/LeetCode-Py