数据结构（七）：二叉树

二叉树的定义

• 二叉树是 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