上一章:程序猿必修课之数据结构(九)串
你还在为开发中频繁切换环境打包而烦恼吗?快来试试 Environment Switcher 吧!使用它可以在app运行时一键切换环境,而且还支持其他贴心小功能,有了它妈妈再也不用担心频繁环境切换了。https://github.com/CodeXiaoMai/EnvironmentSwitcher
树是一对多的数据结构
树的定义
树(Tree)是 n (n ≥ 0)个结点的有限集。
n = 0 时,称为空树。
在任意一棵非空树中:
- 有且仅有一个特定的根(root)结点。
- 当 n > 1 时,其余结点可分为 m (m > 0) 个互不相交的有限集,其中每一个集合本身又是一棵树,并且称之为根的子树(SubTree)。
其实树的定义用到了递归的方法。
常用名词概念
树的每一个结点包含一个数据元素和若干个指向其子树的分支。
结点的度:结点拥有的子树的个数称为结点的度(Degree)。
度为 0 的结点称为叶结点(Leaf)或终端结点。
度不为 0 的结点称为非终端结点或分支结点。
除根结点之外,分支结点也称为内部结点。
树的度:树内各结点的度的最大值。
下图中,结点度的最大值是结点 D 的度为 3,所以树的度也为 3。
image结点的层次(Level) 从根开始,根为第一层。
树中结点的最大层次称为树的深度或高度,上图中树的深度为 4。
如果把树中各子树看成从左到右是有序的,不能互换的,则称该树为有序树,否则称为无序树。
森林:m (m ≥ 0)棵互不相交的树的集合。
线性结构与树结构的对比
线性结构 | 树结构 |
---|---|
第一个数据元素:无前驱 最后一个数据元素:无后继 中间元素:一个前驱一个后继 |
根结点:无双亲,唯一 叶结点:无孩子,可以多个 中间结点:一个双亲,多个孩子 |
树的存储结构
树的存储结构的3种表示方法:双亲表示法、孩子表示法、孩子兄弟表示法。
双亲表示法
用一组连续空间存储树的结点,同时每个结点包含数据域和一个指向其双亲的指针域。
结点 :
data | parent |
---|
其中 data 是数据域,存储结点的数据信息。而 parent 是指针域,存储该结点的双亲在数组中的下标。由于根结点没有双亲,所以我们约定根结点的位置域设置为 - 1,这样所有的结点就都保存了它的双亲的位置了。
二叉树
二叉树( Binary Tree) 是 n(n ≥ 0) 个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成 。
二叉树的特点:
- 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。注意:不是只有两棵子树,而是最多。没有子树或者有一棵子树都是可以的。
- 左子树和右子树是有顺序的,次序不能任意颠倒。
- 即使树中某结点只有一棵子树,也要区分是左子树还是右子树。如下图:树 1 和 树 2 是同一棵树,但它们却是不同的二叉树。
二叉树的五种形态
- 空二叉树。
- 只有一个根结点。
- 根结点只有左子树。
- 根结点只有右子树。
- 根结点既有左子树又有右子树。
特殊二叉树
-
斜树
所有的结点都只有左子树的二叉树叫左斜树;所有结点都只有右子树的二叉树叫右斜树。左斜树和右斜树统称为斜树。斜树有很明显的特点:就是每一层都只有一个结点,结点的个数与二叉树的深度相同。 -
满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
满二叉树的特点:
1) 叶子只能出现在最下一层。
2) 非叶子结点的度一定是 2。
3) 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。 -
完全二叉树
对一棵具有 n 个结点的二叉树按层次编号,如果编号为 i (1≤ i ≤ n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。
完全二叉树的特点:
1)叶子结点只能出现在最下两层。
2)最下层的叶子一定集中在左边连续位置。
3)倒数第二层,若有叶子结点,一定都在右边连续位置。
4)如果结点度为 1,则该结点只有左孩子,不存在只有右孩子的情况。
5)同样结点数的二叉树,完全二叉树的深度最小。
二叉树的性质
- 在二叉树的第 i 层上至多有 2 i-1 个结点(i ≥ 1)。
- 深度为 k 的二叉树至多有 2 k - 1个结点(k ≥ 1)。
- 具有 n 个结点的完全二叉树的深度为 ⌊ log2n ⌋ + 1 (⌊x⌋ 表示不大于 x 的最大整数)。
二叉树的存储结构
顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系。
将一棵完全二叉树用顺序存储结构存储。
完全二叉树.png将这棵二叉树存入到数组中,相应的下标对应其同样的位置
对于一般的二叉树,可以将其按完全二叉树编号,把不存在的结点设置为“^” 就可以了。
但是当一棵深度为 K 的右斜树,它只有 k 个结点,却要分配 2k -1 个存储单元,这样对存储空间造成浪费。所以,顺序存储结构一般只用于完全二叉树。
二叉链表
二叉树每个结点最多有两个孩子,所以每个结点包含一个数据域和两个指针域,这样的链表叫做二叉链表。
其中 data 是数据域,lchild 和 rchild 都是指针域,分别存放左孩子和右孩子的指针。
网友评论