Ch4Tree/

directory
v0.0.0-...-9b8d98b Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 4, 2021 License: MIT

README

Table of Contents

4 树

树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用, 直观来看, 树是以分支关系自定义的层次结构.把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

4.1 树与基本术语的定义

  1. 树的定义: 树（tree）是包含n（n>=0）个结点的有穷集，其中
  • 每个元素称为结点（node）

  • 有一个特定的结点被称为根结点或树根（root）

    • 除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合T_i（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）

  1. 树的基本术语

    • 空树: 没有结点的树
    • 度: 结点含有的子树的个数称之为该节点的度
    • 叶节点(终端结点): 度为零的结点
    • 分支结点(非终端结点): 度不为零的结点
    • 子节点: 结点的子树的根为子节点
    • 父节点: 子节点的根为该子节点的父节点
    • 兄弟结点:同一个根节点下的同一级结点.
    • 结点的层次: 根节点开始定义, 根为第一层, 根的子节点为第二层,以此类推
    • 子孙：以某结点为根的子树中任一结点都称为该结点的子孙
    • 树的高度(深度): 树中结点的最大层次称为树的深度
    • 森林：由m（m>=0）棵互不相交的树的集合称为森林
    • 有(无)序树: 将树中结点的各子数看成从左至右是有次序的(不能互换顺序),则称该树为有序树, 否则称为无序树

4.2 二叉树

1.定义和性质

  1. 定义: 二叉树(Binary Tree)是最多含有两个子树的二叉树, 两个子树由左右之分, 次序不能颠倒是有序树.

  2. 性质:

    • 根据二叉树定义, 表明二叉树可以为空, 或有一个根节点加上两个左右子树互不相交的二叉树组成.
    • 深度为k的树最多有2^k-1个结点
    • 在二叉树的第i层上最多有2^(i-1)个结点

  3. 完全与满二叉树

    • 满二叉树: 深度为k且有2^k-1个结点的二叉树称为满二叉树,特点为每层的结点数都满了.

    image-20200530201120156

    • 完全二叉树: 深度为k的含有n个结点的二叉树, 当且精当每一个结点都与深度k的满而擦函数中编号从1至n一一对应时,为完全二叉树. 特点为不会超过一层中结点不满, 不满的分支里, 结点从左至右排布

      image-20200530201527663

2. 二叉树的存储结构与表达方法

树结构虽然是非线性的逻辑结构, 但是仍然有两种物理存储方式

  1. 线性存储结构

    用一组地址连续的存储单元依次自上而下, 从左至右存储完全二叉树上的结点元素, 即将完全二叉树上编号为i的结点由如上定义下的一维数组中下标为i-1的分量中. 如将上面的完全二叉树顺序存储结构如图

    image-20200530210512163

    这种其中为零的单元表示没有该节点 , 故仅适用于完全二叉树. 在最坏的情况下一个深度为k且只有k个结点的单只树需要2^k-1个单元, 不灵活

  2. 链式存储结构

    构造的结点结构不同可构成不同形式的链式存储结构.

    例如:image-20200530211723288

    结点里可以包含左右指针, 保存的元素, 以及头节点的指针.

  3. 左子右兄弟法:

    物理存储形式为链式存储, 每个结点中的左指针指向其最左边的子节点, 其右节点指向其右边相邻的兄弟结点

3. 二叉树的基本操作

  1. 求度

  2. 求深度和高度

  3. 判断结点类型

  4. 查找兄弟结点

    等

4.3 遍历二叉, 线索二叉树与重建二叉树

1.遍历二叉树

遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列:

  • 先序遍历(Preorder Tree Walk) :按照根节点, 左子树, 右子树的顺序访问节点.

    //递归版
preTraverse(u)
	if u == nill
		return 
	print u
	preTraverse(T[u].left)
	preTraverse(T[u].right)

//迭代版
preTraverse(u)
	if u == nil
		return
	stack.Push(u)
	for !stack.Empty()
		top = stack.Pop()
		print(top.val)
		if top.right != nil
			stack.Push(top.right)
		if top.left != nil
			stack.Push(top.left)

  • 中序遍历(Inorder Tree Walk): 按照左子树, 根节点, 右子树的顺序访问节点.

    //递归
inTraverse(u)
	if u == nill
		return 
	inTraverse(T[u].left) 
	print u
	inTraverse(T[u].right)

//迭代
inTraverse(u)
	p = u
	for p != nil || !stack.Empty()
		if p != nil
			stack.Push(p)
			p = p.left
		else
			q = stack.Pop()
			print(q.val)
			p = q.right

  • 后序遍历(postorder Tree Walk): 按照左子树, 右子树, 根节点的顺序访问树.

    postTraverse(u)
	if u == nill
		return 
	postTraverse(T[u].left)
	postTraverse(T[u].right)
	print u

//非递归遍历 使用两个栈
postTraverse(u)
	if u == nil
		return
	stack s,r //两个栈,r用于保存结果
	s.Push(u)
	for cur != nil || !s.Empty()
		cur = s.Pop
		r.Push(cur)
		if cur.left != nil
			s.Push(cur.left)
		if cur.right != nil
			s.Push(cur.right)
	for !r.Empty
		print(r.pop)

//use two stack
postTraverse(u)
	cur = u
	node pre
	stack s
	for cur != nil || !s.Empty()
		for cur != nil
			s.Push(cur)
			cur = cur.left
		if !s.Empty()
			cur = s.Top()
			if cur.right == nil || cur.right == pre //condition of Stack pop
				print(s.Pop())
				pre = cur
				cur = nil
			else
				cur = cur.right

    除了按照上述序列遍历， 还可以从上到下， 从左到右层次进行

  • 层次遍历法

    levelTraverse(u)
    if u != nil
       queue.Enqueue(u)
    for (!queue.Empty())
       top = queue.Dequeue()
       if top.left != nil
          queue.Enqueue(top.left)
       if top.right != nil
          queue.Enqueue(top.right)
       print(top.val)
2. 线索二叉树(Threaded Binary Tree)

  1. 定义

    在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化.

  2. 规则:

    若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。 若结点的右子树为空，则该结点的右孩子指针指向其后继结点。

  3. 线索化二叉树:

    在遍历二叉树的过程中按照线索化的规则修改两个标志域与空的左右指针指向前驱后继即可.

3 .二叉树的重建

若将树按照前序与中序输出, 根据此按后序遍历树.

  • 分析:首先按先序遍历的顺序访问各节点., 然后通过中序遍历得到树的左右子树.

  • 算法描述:

    reconstruction(left, right) 
	if left >= right 
		return
	//获取当前树的中间值
	midValue := pre[next]
	//获取中间值在中序遍历中的位置
	m := index(in, midValue)
	reconstruction(left, m)
	reconstruction(m+1, right)
	print(midValue)

  • 算法的对每层递归执行的复杂度为O(n), 最坏的情况下复杂度为O(n^2)

4.4 树和森林

1. 树的存储结构

有三种常用的树的存储结构表示树:

  1. 双亲表示法

    每个结点除了数据域, 还有一个parent域指示父节点的位置

    image-20200721122857576

    优点在求结点的父节点遍历, 易求树的根节点, 但求子节点需要遍历整个结构

  2. 孩子表示法

    树中每个结点可能有多个子节点,则可以在每个结点中设置多个指针域指向每棵树的根节点.

    每个结点同构时(结点的结构相同)结点结构如下,由于每个结点的度不相同, 会造成大量的指针域浪费.

    image-20200721123742574

    结点不同构时, 虽然节约了存储空间, 但是结点的度也就固定了,操作不便

    image-20200721123943904

    另外的办法是, 每个结点的子节点排列起来看出一个线性表使用单链表存储, 而树的n个头指针又组成一个线性表,如下图(a).

    image-20200721124449406

    而(b)则是在(a)的基础上加入了父节点的指针域

  3. 左子右兄弟法

    又称二叉树表示法或二叉链表表示法. 结点中的两个链域分别指向该节点的第一个子节点和下一个兄弟结点.

    结构如图image-20200721124820898

    image-20200721124906099

    优点在于它和二叉树的二叉链表表示完全一样, 便于将一般的树结构转换为二叉树进行处理, 利用二叉树的算法来实现对树的操作.

2. 森林与二叉树的转换

image-20200721141501209

  1. 森林转换为二叉树

    F={T1,T2,...,Tm}是森林， 可按如下规则转换为一颗二叉树B={root, LB,RB}

    (1) 若F为空， 即m=0， 则B为空树

    (2) F非空，即m！=0，B的根root即为森林中第一颗树T1的根Root(T1),B的左子树是F中T1转换成的二叉树， 右子树是从F中剩下的森林转换成的二叉树

  2. 二叉树转换为森林

    B={root, LB,RB} 为一颗二叉树， 按如下规则转换为森林F={T1,T2,...,Tm}

    (1)若B为空， 则F为空

    (2)若B非空， 则F中T1的根Root(T1)即为二叉树B的根root，T1根的子树森林是由B的左子树转换而成的森林，F中除去T1之外剩余的树组成的森林由B的右子树转换而成

3.树和森林的遍历

树的定义可以引出两种遍历树的方法：先根遍历与后根遍历。 与二叉树的顺序相同，

树和森林在转换为二叉树前后时，树的先根和后根遍历可借用二叉树的先序遍历和中序遍历算法实现

4.5 哈夫曼树及其应用

1. 哈夫曼树的基本概念

Huffman树又称最优树, 时一类带权路径长度最短的树.

  • 路径: 树中一个节点到另一个结点之间的分支构成这两个结点之间的路径.

  • 路径长度: 路径上的分支数目称作路径长度

  • 树的路径长度: 从树根到每一个节点的的路径长度之和

  • 权:赋予某个实体的一个量, 是对实体的某个或某些属性的数值化描述.数据结构中, 实体有结点(元素)和边(关系)两大类, 所以对应有结点权和关系权. 结点权或边权具体代表什么有具体情况决定. 若一棵树中的结点带有权值, 则对应有带权树的概念.

  • 结点的带权路径长度:从该节点到树根之间的路径长度与结点上权的乘积.

  • 树的带权路径长度: 书中所有叶子节点的带权路径长度之和. 通常记为:image-20200722205748583

  • 哈夫曼树: 假设有m个权值{w1, w2, ..., wm,}, 可以构造一棵含有n个子节点的二叉树, 每个叶子节点的权为wi, 则其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树.

    image-20200723142306512

    其中c树的为最小, 即为哈夫曼树.具有权值越大的结点离根节点越近的特点,据此特点哈夫曼最找给出了构造哈夫曼树的哈夫曼算法

2.哈夫曼树的构造算法

  1. 构造过程

    (1) 根据给定的n个权值, 构造n棵只有根节点的二叉树,这些树构成森林F

    (2) F中选取两个权值最小的树作为左右子树构成一颗新树, 新树的权值为左右子节点的和

    (3) F中删掉选出去的两颗子树, 并加入新生成的树

    (4) 重复(2)(3) , 知道F只有一颗树, 此时这棵树便为哈夫曼树

    image-20200723150734206

    在此过程中, 先选择最小的权值结点, 这样可以保证权大的离根较近. 这种生成算法是一种典型的贪心算法.

  2. 哈夫曼算法的实现

    HT中不含度为1的结点, n个叶子节点的哈夫曼树共有2n-1个结点. 这里选择将结点存储在动态数组中实现.

    struct HTNode
	int weight
	int parent,left, right //记录位置的下标

    数组大小为2n, 为实现方便, 0单元不使用, 1~n存储叶子节点, 后面n-1个单元存储非叶子节点.

    算法步骤:

    ​ a. 初始化: 动态申请2n个单元, 初始化每个单元, 将记录位置的三个下标初始化为空, 之后 入n个叶子节点的权重

    ​ b. 创建树: 迭代n-1次, 通过选择,删除与合并来创建哈夫曼树.

    CREATHUFFMANTREE(n)
	creat array HT with lenght 2n
	for i= 1 to 2n-1
		HT[i].parent = 0
		HT[i].left = 0
		HT[i].right = 0
	for i = 1 to n
		HT[i].weight = input //iput each node's weight
	for i=n+1; i< m; i++
		s1,s2 = Select(HT,i-1) //s1 <= s2
		HT[s1].parent = i
		HT[s2].parent = i
		HT[i].left = s1
		HT[i].right = s2
		HT[i].weight = HT[s1].weight + HT[s2].weight
	return HT
3. 哈夫曼编码
基本思想

对数据进行压缩是, 为了是压缩后的数据尽可能短, 可采用不定长编码, 基本思想为: 对出现次数多的字符进行较短的编码. 此时可以利用哈夫曼树来设计二进制编码.

先给有关编码的两个概念:

  1. 前缀编码: 若在一个编码方案中, 任一个编码都不是其他任何编码的前缀(最左字串),则称编码为前缀编码. 前缀编码可以保证对压缩文件进行解码时不产生二义性, 确保解码正确性
  2. 哈夫曼编码: 对一颗具有n个叶子节点的哈夫曼树, 若对树中的每个左分支赋予0, 右分支赋予1, 则从根到每个叶子的路径上, 各分支的赋值分别构成的一个二进制串, 该二进制串称为哈夫曼编码

哈夫曼编码有如下两个性质:

  1. 哈夫曼编码为前缀编码

    若路径A是另一条路径B的最左部分, 则B经过了A, A的终点一定不是叶子. 而哈夫曼编码对应路径的终点一定是叶子, 因此编码不会重叠

  2. 哈夫曼编码是最优前缀编码

    image-20200723160942106
算法实现

image-20200723162821055

文件的编码与解码

  1. 编码

    有了字符集的哈夫曼编码表, 对数据文件的编码过程为:

    • 依次读入文件中的字符c
    • 在编码表中找到字符c
    • 在文件中将c换为编码串

  2. 解码

    解码需要借助哈夫曼树

    • 依次读入文件的的二进制码, 从哈夫曼树的根节点出发, 若0则左结点,1右节点,到达叶子之后将字符替换, 然后继续重复此过程知道文件结束

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.