算法与数据结构【树和⼆叉树】

Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。

1 树

1.1 树的概念与结构

概念：树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。（因为它看起来像⼀棵倒挂的树，所以把它叫做树。）

树形结构： • 有⼀个特殊的结点，称为根结点， 根结点 没有前驱结点（例如下面的A节点） • 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以 有 0 个或多个后继。因此，树是递归定义的。 •子树不相交（如果存在相交就是图了） •一棵N个结点的树有N-1条边。（因为子树是不相交的，例如两个节点相连要一条边） •除了根结点外，每个结点有且仅有一个父结点。

1.2 树相关术语

• ⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如下图：A是B的⽗结点 。 • ⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如下图：B是A的孩⼦结点 • 结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，E的度为2，B的度为0。 • 树的度：⼀棵树中，最⼤的结点的度称为树的度； 如下图：树的度为 6 。 • 叶⼦结点/终端结点：度为 0 的结点称为叶结点； 如下图： B 、 C 、 H 、 I... 等结点为叶结点。 • 分⽀结点/⾮终端结点：度不为 0 的结点； 如下图： D 、 E 、 F 、 G... 等结点为分⽀结点 。 • 兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)； 如下图： B、 C 是兄弟结点。 • 结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；【注意这是一个相对于结点的概念，例如A属于第一层】 • 树的⾼度或深度：树中结点的最⼤层次； 如下图：树的⾼度为 4 。 • 结点的祖先：从根到该结点所经分⽀上的所有结点；如下图： A 是所有结点的祖先。 • 路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q 。 • ⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如下图：所有结点都是A的⼦孙。 • 森林：由 m （ m>0 ） 棵互不相交的树的集合称为森林；

1.3树的表⽰【方法很多自己私下可以去尝试】

树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦ 兄弟表⽰法等，其中最常⽤的孩⼦兄弟表⽰法

孩⼦兄弟表⽰法：

1. 4 树形结构实际运⽤场景

⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间 的关联。

2 ⼆叉树

2.1 概念与结构

概念：在树形结构中，我们最常⽤的就是⼆叉树（从名字上看就可以知道其每个结点的子结点最多只能有两个，所以结构相对简单），⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

结构：

2.2⼆叉树具备以下特点

1. ⼆叉树不存在度⼤于 2 的结点 （每个结点的子结点最多只能是两个） 2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树（从我们定义的结构体理解）

⼆叉树都是由以下⼏种情况复合⽽成的

2.3⼆叉树的分类

1 满⼆叉树 2 完全⼆叉树（这两种都是 ⼆叉树的特殊情况）

3 满⼆叉树

3.1概念：⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是 2^k-1（可以根据等比数列计算可得） ，则它就是满⼆叉树。

4 完全⼆叉树

4.1概念：除了最后一层，其他每层的结点个数都达到最大，最后一层结点个数不一定达到最大，但是最后一层的结点是按照顺序从左往右依次排列的（因为子树有左右之分）要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

4.2完全⼆叉树和满二叉树的关系

5 ⼆叉树性质

根据满⼆叉树的特点可知： 1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2 i −1 个结点 2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2 h − 1 3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 h = log 2 ( n + 1) ( log 以2为底， n+1 为对数)

好了，今天的内容就分享到这，我们下期再见！