简介

• 概念: 为n(n>=0)个结点的有限集。n=0时为空树。
• 特点: 在任意一棵非空树中
  • 有且仅有一个特定的称为根(Root)的结点
  • 当n>1时, 其余结点可以分为m(m>0)个互不相交的有限集T1、T2、……、Tm, 其中每一个集合本身又是一棵树, 并且称为根的子树(SubTree)

结点分类

• 根结点: 无双亲, 唯一
• 叶结点: 无孩子, 可以多个
• 中间结点: 一个双亲多个孩子

相关概念

• 度:
  • 结点拥有的子树数, 度为零的结点称为叶结点或终端结点, 度不为零的结点称为非终端结点或分支结点
• 树的度:
  • 树内各节点的度的最大值
• 结点的层次:
  • 从根开始定义起, 根为第一层, 根的孩子为第二层
• 树的深度或高度:
  • 树中结点的最大层次
• 有序树和无序树:
  • 如果将树中结点的各子树看成从左至右是有次序的, 不能互换的, 则称该树为有序树, 否则称为无序树
• 森林:
  • m(m>=0)棵互不相交的树的集合, 对树中每个结点而言, 其子树的集合即为森林

抽象数据类型定义

ADT 树(tree)
Data
	由一个根节点和若干棵子树构成。树中结点具有相同数据类型及层次关系
Operation
    InitTree(*T): 构造空树
    DestroyTree(*T): 销毁树
    CreateTree(*T, definition): 按definition中给出树的定义来构造树
    ClearTree(*T): 若树T存在, 则将树T清为空树
    TreeEmpty(T): 若T为空树, 返回true, 否则返回false
    TreeDepth(T): 返回T的深度
    Root(T): 返回T的根结点
    Value(T,cur_e): cur_e是树T中一个结点, 返回此结点的值
    Assign(T,cur_e,value): 给树T的结点cur_e赋值为value
    Parent(T,cur_e): 若cur_e是树T的非根结点, 则返回它的双亲, 否则返回空
    LeftChild(T,cur_e): 若cur_e是树T的非叶结点, 则返回它的最左孩子, 否则返回空
    RightSibling(T,cur_e): 若cur_e有右兄弟, 则返回它的右兄弟, 否则返回空
    InsertChild(*T,*p,i,c): 其中p指向树T的某个结点, i为所指结点p的度加上1, 非空树c与T不相交, 操作结果为插入c为树T中p指结点的第i棵子树
    DeleteChild(*T,*p,i): 其中p指向树T的某个结点, i为所指结点p的度, 操作结果为删除T中p所指结点的第i课子树
end ADT

存储结构

双亲表示法

• 说明:
  • data为数据域, parent为指针域, 根结点的位置域设置为-1
• 双亲域表示法

  下标	data	parent
  0	A	-1
  1	B	0
  2	C	0
  3	D	1
  4	E	2
  5	F	2
  6	G	3
  7	H	3
  8	I	3
  9	J	4

• 长子域表示法
• 右兄弟域表示法

孩子表示法

• 引入:
  • 采用多重链表: 每个结点有多个指针域, 其中每个指针指向一棵树的根节点
  • 存储设计:
    • 方案一: 指针域的个数等于树的度, 对于树中各节点度相差很大时, 比较浪费空间
      • data为数据域, child1~childd为指针域
    • 方案二: 每个结点指针域的个数等于该结点的度, 专门取一个位置来存储结点指针域的个数
      • data为指针域, degree为度域, child1~childd为指针域
• 概念:
  • 把每个结点的孩子结点排列起来, 以单链表做存储结构, 则n个结点有n个孩子链表, 如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表, 采用顺序存储结构, 存放一个一维数组中

结构:

• 孩子链表的孩子结点:
  • child为数据域,存储某个结点在表头数组中的下标;
  • next为指针域, 存储指向某结点的下一个孩子结点的指针
• 表头数组的表头结点:
  • data为数据域,存储某结点的数据信息;
  • firstchild为头指针域,存储该节点的孩子链表的头指针

扩展

• 双亲孩子表示法

孩子兄弟表示法

• data为数据域, firstchild为指针域, 储存该结点的第一个孩子结点的储存地址, rightsib为指针域, 存储该节点的右兄弟结点的存储地址

二叉树(Binary Tree)

• 概念: 是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树), 或者由一个根节点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成
• 特点:
  • 每个结点最多有两课子树, 即不存在度大于2的结点, 没有子树或者有一棵子树均可
  • 左子树和右子树是有序的
  • 即使某结点只有一棵子树, 也要区分是左子树还是右子树
• 基本形态(5种):
  • 空二叉树
  • 只有一个根节点
  • 根节点只有左子树
  • 根节点只有右子树
  • 根节点既有左子树又有右子树

特殊二叉树

• 斜树: 左斜树和右斜树
  • 每层只有一个结点, 结点数与二叉树的深度相同
• 满二叉树: 所有分支节点都存在左子树和右子树, 并且所有叶子都在同一层上

完全二叉树:

• 概念:
  • 对一颗具有n个结点的二叉树按层次编号, 如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同, 则这课二叉树称为完全二叉树
• 特点:
  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数第二层,若有叶子结点,一定都在右部连续位置
  • 如果结点度为1, 则该结点只有左子树, 不存在右子树
  • 同样结点的二叉树,完全二叉树的深度最小

二叉树的性质

性质一:

• 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

性质二:

• 深度为k的二叉树至多有2^k - 1 个结点

性质三:

• 对任何一棵二叉树T, 如果其终端结点数为n0, 度为2的结点数为n2, 则n0 = n2 + 1

性质四:

• 具有n个结点的完全二叉树的深度为[log2n] + 1 ([x]表示不大于x的最大整数)

性质五:

• 对于一棵有n个结点的完全二叉树(其深度为[log2n] + 1)的结点按层序编号(从第1层到第[log2n] + 1层, 每层从左到右), 对任一节点i(1<=i<=n):
  • 如果i=1, 则结点i是二叉树的根, 无双亲; 如果i>1, 则其双亲是结点[i/2]
  • 如果2i>n, 则结点i无左孩子(结点i为叶子结点); 否则其孩子是结点2i
  • 如果2i+1>n, 则结点i无右孩子; 否则其右孩子是结点2i+1

二叉树的存储结构

二叉树顺序存储结构

• 用一维数组存储二叉树中的结点
• 一般只用于存储完全二叉树

二叉链表

• 二叉树每个结点最多有两个孩子, 所以为它设计一个数据域和两个指针域, 我们称这样的链表叫做二叉链表
• 如有需要可以增加一个指向其双亲的指针域, 称之为三叉链表

遍历二叉树

• 二叉树额遍历(traversing binary tree):
  • 从根节点出发, 按照某种次序依次访问二叉树所有结点, 使得每个结点被访问一次, 且仅被访问一次

        A
     /     \
    B       C
   / \     / \
  D   E   F   G
 /       /     \
H       I       J
 \
  K

• 二叉树遍历方法: 把树中的结点变成某种意义的线性序列
  1. 前序遍历: 先访问根节点, 然后前序遍历左子树, 再前序遍历右子树
  2. 中序遍历: 中序遍历根节点的左子树, 然后访问根节点, 最后中序遍历右子树
  3. 后序遍历: 从左到右, 先叶子后结点的方式遍历访问左右子树, 最后访问根节点
  4. 层序遍历: 同一层按从左到右的顺序对结点逐个访问

前序遍历递归算法

• 示例:

void PreOrderTraverse(BiTree T)
{
	if(T == NULL)
		return;
	printf("%c", T->data); //显示结点数据
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

• 遍历顺序: ABDHKECFIGJ

中序遍历递归算法(6.8.4)

• 示例:

void InOrderTraverse(BiTree T)
{
	if(T == NULL)
		return;
	InOrderTraverse(T->lchild); //中序遍历左子树
	printf("%c", T->data); //显示结点数据
	InOrderTraverse(T->rchild);	//中序遍历右子树
}

• 遍历顺序: HKDBEAIFCGJ

后序遍历递归算法

• 示例:

void PostOrderTraverse(BiTree T)
{
	if(T == NULL)
		return;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c", T->data);
}

• 遍历顺序: KHDEBIFJGCA

遍历总结

• 总结:
  • 遍历都是从根节点开始
  • 前序遍历是先打印再递归左右

遍历性质

• 已知前序遍历序列和中序遍历序列, 可以唯一确定一棵二叉树
• 已知后序遍历序列和中序遍历序列, 可以唯一确定一棵二叉树

二叉树的建立

• 利用递归原理, 在原来应该打印结点的地方, 改成生成结点, 给结点赋值操作

线索二叉树(Threaded Binary Tree)

• 引入: n个节点的二叉树存在n+1个空指针域
• 定义:
  • 指向前驱和后继的指针称为线索, 加上线索的二叉链表称为线索链表, 相应的二叉树称为线索二叉树
• 特征: 其实线索二叉树, 等于把一棵二叉树转变成了一个双向链表
• 线索化: 在遍历的过程中修改空指针的过程

使用场景

• 如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继, 那么可以采用线索二叉链表的存储结构

霍夫曼树(Huffman Tree)

• 相关概念:
  • 路径长度:
    • 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径, 路径上的分支数目称做路径长度
  • 树的路径长度:
    • 从树根到每一结点的路径长度之和
• 定义:
  • 假设有n个权值{w1,w2,…,wn}, 构造一棵有n个叶子结点的二叉树, 每个叶子结点带权wk, 每个叶子的路径长度为lk, 我们通常记作, 其中带权路径长度WPL最小的二叉树称做霍夫曼树

算法描述

1. 根据给定n个权值{w1,w2,…,wn}构成n课二叉树的集合F={T1,T2,…,Tn}, 其中每颗二叉树Ti中只有一个带权为wi根节点, 其左右子树均为空
2. 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树, 且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和
3. 在F中删除这两棵树, 同时将新得到的二叉树加入F中
4. 重复2和3步骤, 直到F只含一棵树为止。这棵树便是霍夫曼树

霍夫曼编码

• 构造霍夫曼树主要运用于编码，称为霍夫曼编码。
• 定义：
  • 一般地，设需要编码的字符集为{d1,d2,…,dn}, 各个字符在电文中出现的次数或频率的集合为{w1,w2,…,wn}, 以d1,d2,…,dn作为叶子结点, 以w1,w2,…,wn作为相应叶子结点的权值来构造一棵霍夫曼树。规定霍夫曼树的左分支代表0，右分支代表1，则从根节点到叶子结点所经过的路径分支组成0和1的序列便为该节点对应字符的编码，即为霍夫曼编码。
• 霍夫曼编码实现过程中运用到了贪心算法。霍夫曼树中权值越大的结点距离根结点越近。采用二叉树可以适当降低编码长度，尤其是在编码长度较长，且权值分布不均匀时，采用霍夫曼编码可以大大缩短编码长度。