二叉树的定义
- 二叉树是 n （n >= 0）个节点的有限集合，该集合或者为空集（称为空二叉树）或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
图1
- 折半规律很适合作为二叉树建模
图2
1. 二叉树特点
- 每个节点最多有两棵子树
- 左子树和右子树是有顺序的，次序不能任意颠倒
- 即使树中某节点只有一棵子树也要区分它是左子树还是右子树
2. 特殊二叉树
- 斜树：所有的节点都只有左子树的二叉树叫做左斜树，反之右斜树
- 满二叉树：所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上
图3
- 完全二叉树：叶子节点只能出现在最下两层，最下层的叶子一定集中在左部连续位置，倒数二层，若有叶子节点，一定都在右部连续位置，如果节点度为 1，则该节点只有做孩子，既不存在右子树情况，同样节点数的二叉树，完全二叉树的深度最小
图4
二叉树的性质
二叉树性质1
- 在二叉树的第 i 层上至多有 2的i-1次方个节点 (i>=1)
二叉树性质2
- 深度为 k 的二叉树至多有 2的k次方-1个节点 （k>=1）
二叉树性质3
- 如果端节点数为 n0，度为 2 的节点数为 n2，则 n0=n2+1
- 终端节点其实就是叶子节点数，而一棵二叉树除了叶子节点外，剩下的就是度为 1 或 2 的节点数了，我们设 n1 为度是 1 的节点数，则树节点总数是 n=n0+n1+n2
- 图5 度为2的节点数 n2 = 4，则叶子节点数 n0 = 4+1，树节点总数 n=4+1+5
图5
二叉树性质4
- 具有 n 个节点的完全二叉树的深度为 [log2n]+1 ([x] 表示不大于 x 的最大整数)
- 如 图1 有 10 个节点，则深度 4 = log 以2为底10的对数 + 1 = 3 + 1
二叉树性质5
- 对于一棵有 n 个节点的完全二叉树（其深度为 [log2n]+1）的节点按层序编号（从第 1 层到第 [log2n]+1 层，每层从左到右），对任一节点 i 有：
- 如果 i =1，则节点 i 是二叉树的根，则无双亲，如果 i > 1，则其双亲是节点 [i/2]（下图节点7，它的双亲就是 [7/2] = 3）
- 如果 2i > n，则节点 i 无左子树（节点 i 为叶子节点），否则其左子树是节点 2i，（下图节点6，因为 2*6=12 超过了节点总数 10，所以它无左子树，而节点5 因为等于10，所以它的左子树节点为 10）
- 如果 2i + 1 > n，则节点 i 无右子树，否则其右子树是节点 2i+1，（下图节点5，因为 2*5+1=11 大于节点总数 10，所以它无右子树，因为节点2 小于 10，所以它的右子树节点为 7）
图6
二叉树的存储结构
二叉树顺序存储
- 二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系，比如双亲与子节点、兄弟节点的关系
avV7A-1.png
- 对于一般的二叉树，层序编号不能反应逻辑关系，但是可以将其按完全二叉树编号，把不存在的节点设置为 "^"
图8
- 考虑一种极端情况，一棵深度为 k 的右斜树，它只有 k 个节点，却要分配 2的k次方-1 个存储单元空间，这显然是对存储空间的浪费，所以顺序存储结构一般只用于完全二叉树
图9
二叉链表
- 二叉树每个节点最多有两个子节点，所以为它设计一个数据域与两个指针域
| lchild | data | rchild |
|---|
遍历二叉树
- 二叉树的遍历是指从根节点触发，按照某种次序依次访问二叉树中所有的节点，使得每个节点都被访问一次且仅被访问一次
二叉树遍历方法
1. 前序遍历
- 先访问根节点，然后前序遍历左子树，再前序遍历右子树，遍历顺序为：ABDGHCEIF
avtTz.png
2. 中序遍历
- 中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树，遍历顺序为：GDHBAEICF
av1Sa.png
3. 后续遍历
- 从左到右先叶子后节点的方式遍历左右子树，最后访问根节点，遍历顺序为：GHDBIEFCA
av64S.png
4. 层序遍历
- 从树的根节点开始访问，从上而下逐层遍历，在同一层中，从左到右顺序对节点逐个访问，遍历顺序为：ABCDEFGHI
avKP2.png
网友评论