数据结构：⼆叉树（带图详解）
⽬录
先序中序后序遍历二叉树树的概念和结构
树的概念
树是⼀种 ⾮线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成⼀个具有层次关系的集合。 把它叫做树是因为它看 起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的 。
它具有以下的特点：
注意：树型结构中，⼦树之间不能有交集，否则就不是树型结构
树与⾮树？
以上三种情况可以得出：
根据下图详细说明树的概念：
结点的度 ：⼀个结点含有⼦树的个数称为该结点的度； 如上图： A 的度为 6
树的度 ：⼀棵树中，所有结点度的最⼤值称为树的度； 如上图：树的度为 6
叶⼦结点或终端结点 ：度为 0 的结点称为叶结点； 如上图： B 、 C 、 H 、 I... 等节点为叶结点
双亲结点或⽗结点 ：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图： A 是 B 的⽗结点
孩⼦结点或⼦结点 ：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图： B 是 A 的孩⼦结点
根结点 ：⼀棵树中，没有双亲结点的结点；如上图： A
结点的层次 ：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推
树的⾼度或深度 ：树中结点的最⼤层次； 如上图：树的⾼度为 4
⾮终端结点或分⽀结点 ：度不为 0 的结点； 如上图： D 、 E 、 F 、 G... 等节点为分⽀结点
兄弟结点 ：具有相同⽗结点的结点互称为兄弟结点； 如上图： B 、 C 是兄弟结点
堂兄弟结点 ：双亲在同⼀层的结点互为堂兄弟；如上图： H 、 I 互为兄弟结点
结点的祖先 ：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先
⼦孙 ：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是 A 的⼦孙
森林 ：由 m （ m>=0 ）棵互不相交的树组成的集合称为森林
树的表⽰形式
树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，实际中树有很多种表⽰⽅式，如： 双亲表⽰法 ， 孩⼦表⽰法 、 孩⼦双亲表⽰法 、 孩⼦兄弟表⽰法 等等。我们这⾥就简单的了解其中最常⽤的 孩⼦兄弟表⽰法 。
class Node {
int value; // 树中存储的数据
Node firstChild; // 第⼀个孩⼦引⽤
Node nextBrother; // 下⼀个兄弟引⽤
}
⼆叉树
⼆叉树的概念
⼆叉树（binary tree）是指树中结点的度不⼤于2的有序树，它是⼀种最简单且最重要的树。⼆叉树的递归定义为：⼆叉树是⼀棵空树，或者是⼀棵由⼀个根节点和两棵互不相交的，分别称作根的左⼦树和右⼦树组成的⾮空树；左⼦树和右⼦树⼜同样都是⼆叉树
对于任意的⼆叉树都是由以下⼏种情况复合⽽成的：
两种特殊的⼆叉树
1、满⼆叉树
满⼆叉树 : ⼀棵⼆叉树，如果 每层的结点数都达到最⼤值，则这棵⼆叉树就是满⼆叉树。也就是说，如果⼀棵⼆叉树的层数为n，且结点总数是 2ⁿ - 1 ，则它就是满⼆叉树。
2、完全⼆叉树
完全⼆叉树 : 完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K
的，有 n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K 的满⼆叉树中编号从 0 ⾄ n-1 的结点⼀⼀对应时称之为完全⼆叉树。 要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
注意：满⼆叉树⼀定是完全⼆叉树，⽽完全⼆叉树不⼀定是满⼆叉树
⼆叉树的性质
1. 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有 2^(i-1) （i>0）个结点
ps：因为求的是第i层上最多的结点个数可以简单将⼆叉树理解成满⼆叉树
2. 若规定只有 根结点的⼆叉树的深度为1 ，则 深度为K的⼆叉树的最⼤结点数是 2^k -1（k≥0）
ps：⼆叉树的最⼤结点个数也可以将⼆叉树理解成满⼆叉树
3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2，则有n0＝n2＋1
ps：在任意⼆叉树中，度为0的结点⽐度为2的结点多⼀个
假设：⼆叉树中总的结点个数为N，度为0的结点有n0个，度为1的结点有n1个，度为2的结点n2有n2个 ——>  N = n0 + n1  （1）                                                                                                                  ⼆叉树中总的结点个数为N，在⼆叉树中总共有N-1条边 ——从下往上看                                        n0的结点——叶⼦结点：往下不可能产⽣边                                                                                      n1的结点——只有⼀个孩⼦的结点：往下只能产⽣⼀条边                                                                n2的结点——两个孩⼦结点均存在：往下可以产⽣两条边                                                                利⽤总边数建⽴⼀个式⼦——>N-1 = n1 + 2* n2 （2）                                                        结合两个式⼦得出n0 = n2 + 1
4.具有n个结点的完全⼆叉树的深度k为 log₂(n+1) 向上取整
满⼆叉树也是完全⼆叉树，⽽满⼆叉树总结点个数为：2^h - 1 = n    即 h = log₂(n+1)                      如果是满⼆叉树，h计算出来之后肯定是整数；如果是完全⼆叉树，h计算出来之后可能是⼩数（向上取整数）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。