1162 lines
33 KiB
Markdown
1162 lines
33 KiB
Markdown
|
||
# 07 树
|
||
|
||
**知识结构：**
|
||
|
||
|
||
|
||
|
||
---
|
||
## 1. 树的基本概念与术语
|
||
|
||
### 1.1 树的定义
|
||
|
||
树是$N(N \geq 0)$个结点组成的有穷集合 ，该集合具有如下特征：
|
||
|
||
（1）除$N=0$的树外，有且仅有一个特定的称为根的结点。
|
||
|
||
（2）其余结点分为$m (m\geq 0)$个互不相交的有穷集合$T_1,T_2,\cdots,T_m$，其中每一个集合都是一棵树，称为该根的子树。
|
||
|
||
例：
|
||
|
||
|
||
|
||
树的特点：
|
||
|
||
（1）有一个总根。
|
||
|
||
（2）没有分支相交。
|
||
|
||
（3）树有层次。
|
||
|
||
|
||
|
||
### 1.2 树的相关术语
|
||
|
||
**结点的度**：该结点具有子树的数目。
|
||
|
||
**叶子结点**：度为零的结点。（没有子树的结点）
|
||
|
||
**树的度**：树中结点度的最大值。
|
||
|
||
**子女与双亲**：子女指该结点子树的根结点，双亲即该结点。
|
||
|
||
**结点的层次（Level）**：根到该结点的路径长度。（根为第零层、若结点$X$在$L$层，则其子女在$L+1$层）。
|
||
|
||
**树的高度（深度）**：树中结点层的最大值。
|
||
|
||
**兄弟与堂兄弟**：同一双亲孩子之间称为兄弟，其双亲在同一层的结点互为堂兄弟。
|
||
|
||
**祖先与子孙**：从根到该结点所经分支上的所有结点称为该结点的祖先，以该结点为根的子树中的所有结点称为该结点的子孙。
|
||
|
||
**森林**：$m (m \geq 0)$棵互不相交的树的集合。
|
||
|
||
|
||
---
|
||
## 2. 二叉树
|
||
|
||
### 2.1 二叉树的定义及其性质
|
||
|
||
（1）二叉树的定义
|
||
|
||
二叉树是结点的有穷集合，且必须满足下面的条件之一：
|
||
|
||
- 它是空集。
|
||
- 它由一个根结点和其左右子树构成且其左右子树满足二叉树的定义。
|
||
|
||
（2）二叉树的基本形态
|
||
|
||
|
||
|
||
|
||
（3）二叉树的特征
|
||
|
||
- 二叉树的每个结点的度不大于2。
|
||
- 二叉树的子树有左右之分。
|
||
|
||
（4）二叉树的性质
|
||
|
||
性质1：二叉树中层数为$i(i\geq 0)$的结点至多有$2^i$个。
|
||
|
||
|
||
性质2：高度为$k$的二叉树至多有$2^{k+1}-1(k\geq 0)$个结点。
|
||
|
||
若一棵高度为$k$的二叉树，具有$2^{k+1}-1$个结点，这样的二叉树称为**满二叉树**。
|
||
|
||
若一棵具有$n$个结点，高度为$k$的二叉树，其中所有结点与高度为$k$的满二叉树中编号由1至$n$的那些结点对应，这样的二叉树称为**完全二叉树**。
|
||
|
||
|
||
|
||
注：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
|
||
|
||
性质3：设二叉树中叶子结点的个数为$n_0$，度为2结点的个数为$n_2$，则$n_0=n_2+1$。
|
||
|
||
性质4：将一棵具有$n$个结点的完全二叉树按层次顺序（从上到下、从左到右）从1开始编号，则对编号为$i(1\leq i\leq n)$的结点有：
|
||
|
||
- 若$i$不等于1，则编号为$i$结点的双亲结点的编号为$[\frac{i}{2}]$；
|
||
- 若$2i\leq n$，则编号为$i$结点的左孩子的编号为$2i$，否则$i$无左孩子；
|
||
- 若$2i+1 \leq n$，则编号为$i$结点的右孩子的编号为$2i+1$，否则$i$无右孩子；
|
||
|
||
性质5：具有$n$个结点的完全二叉树的高度为$[log_2^n]$。
|
||
|
||
|
||
|
||
### 2.2 二叉树的存储
|
||
|
||
（1）顺序存储
|
||
|
||
完全二叉树：
|
||
|
||
|
||
|
||
|
||
非完全二叉树：
|
||
|
||
|
||
|
||
（2）链式存储
|
||
|
||
|
||
|
||
通常：完全二叉树用顺序存储，普通二叉树用链式存储。
|
||
|
||
二叉树结点的结构：
|
||
|
||
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
namespace NonLinearStruct
|
||
{
|
||
/// <summary>
|
||
/// 二叉树结点
|
||
/// </summary>
|
||
/// <typeparam name="T">结点中数据元素的类型</typeparam>
|
||
public class BinTreeNode<T> : IComparable<BinTreeNode<T>> where T : IComparable<T>
|
||
{
|
||
private T _data;
|
||
|
||
/// <summary>
|
||
/// 获取或设置该结点的左孩子
|
||
/// </summary>
|
||
public BinTreeNode<T> LeftChild { get; set; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置该结点的右孩子
|
||
/// </summary>
|
||
public BinTreeNode<T> RightChild { get; set; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置该结点的数据元素
|
||
/// </summary>
|
||
public T Data
|
||
{
|
||
get { return _data; }
|
||
set
|
||
{
|
||
if (value == null)
|
||
throw new ArgumentNullException();
|
||
_data = value;
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// 初始化BinTreeNode类的新实例
|
||
/// </summary>
|
||
/// <param name="lChild">该结点的左孩子</param>
|
||
/// <param name="data"> 该结点的数据元素 </param>
|
||
/// <param name="rChild">该结点的右孩子</param>
|
||
public BinTreeNode(T data, BinTreeNode<T> lChild = null, BinTreeNode<T> rChild = null)
|
||
{
|
||
if (data == null)
|
||
throw new ArgumentNullException();
|
||
LeftChild = lChild;
|
||
_data = data;
|
||
RightChild = rChild;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 实现接口IComparable<BinTreeNode<T>>中的方法。
|
||
/// </summary>
|
||
/// <param name="other"></param>
|
||
/// <returns></returns>
|
||
public int CompareTo(BinTreeNode<T> other)
|
||
{
|
||
if (other == null)
|
||
throw new ArgumentNullException();
|
||
return _data.CompareTo(other.Data);
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
### 2.3 二叉树的遍历
|
||
|
||
定义：按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。
|
||
|
||
遍历的方式：
|
||
- 前序遍历（先根遍历）：访问根结点，前序遍历左子树，前序遍历右子树；
|
||
- 中序遍历（中根遍历）：中序遍历左子树，访问根结点，中序遍历右子树；
|
||
- 后序遍历（后根遍历）：后序遍历左子树，后序遍历右子树，访问根结点
|
||
- 层次遍历：遍历第0层，遍历第1层，$\cdots$，遍历第$k$层（$k$为树的深度）；
|
||
|
||
例子：
|
||
|
||
|
||
|
||
例子：中序遍历与递归
|
||
|
||
|
||
|
||
|
||
### 2.4 二叉树的实现
|
||
|
||
二叉树的操作
|
||
- 获取或设置二叉树的根结点
|
||
- 向二叉树中插入结点
|
||
- 获取前序遍历序列
|
||
- 获取中序遍历序列
|
||
- 获取后序遍历序列
|
||
- 获取层次遍历序列
|
||
- 获取给定结点的双亲结点
|
||
- 获取给定结点的左兄弟结点
|
||
- 获取给定结点的右兄弟结点
|
||
- 删除以给定结点为根的子树
|
||
- 根据给定数据查找其在二叉树中的结点
|
||
- 获取叶子结点的个数
|
||
- 交换二叉树的左右子树
|
||
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
using LinearStruct;
|
||
namespace NonLinearStruct
|
||
{
|
||
/// <summary>
|
||
/// 二叉树的抽象数据类型实现
|
||
/// </summary>
|
||
/// <typeparam name="T">二叉树中结点数据的类型</typeparam>
|
||
public class BinTree<T> where T : IComparable<T>
|
||
{
|
||
private string _orderString = string.Empty;
|
||
|
||
/// <summary>
|
||
/// 获取或设置二叉树的根结点
|
||
/// </summary>
|
||
public BinTreeNode<T> Root { get; set; }
|
||
|
||
/// <summary>
|
||
/// 初始化BinTree类的新实例
|
||
/// </summary>
|
||
/// <param name="root">二叉树的根结点</param>
|
||
public BinTree(BinTreeNode<T> root)
|
||
{
|
||
Root = root;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 向树中插入结点
|
||
/// </summary>
|
||
/// <param name="current">要插入的结点</param>
|
||
/// <param name="lChild">该结点的左孩子结点</param>
|
||
/// <param name="rChild">该结点的右孩子结点</param>
|
||
public void Insert(BinTreeNode<T> current, BinTreeNode<T> lChild, BinTreeNode<T> rChild)
|
||
{
|
||
if (Root == null)
|
||
throw new Exception("树为空.");
|
||
if (current == null)
|
||
throw new ArgumentNullException();
|
||
|
||
current.LeftChild = lChild;
|
||
current.RightChild = rChild;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 前序遍历的递归函数
|
||
/// </summary>
|
||
/// <param name="current">开始递归的根结点</param>
|
||
private void PreOrder(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
return;
|
||
_orderString += current.Data + " ";
|
||
PreOrder(current.LeftChild);
|
||
PreOrder(current.RightChild);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到前序遍历序列
|
||
/// </summary>
|
||
/// <returns>前序遍历序列</returns>
|
||
public string PreOrderTraversal()
|
||
{
|
||
_orderString = string.Empty;
|
||
PreOrder(Root);
|
||
return _orderString.Trim();
|
||
}
|
||
|
||
/// <summary>
|
||
/// 中序遍历的递归函数
|
||
/// </summary>
|
||
/// <param name="current">开始递归的根结点</param>
|
||
private void MidOrder(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
return;
|
||
MidOrder(current.LeftChild);
|
||
_orderString += current.Data + " ";
|
||
MidOrder(current.RightChild);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到中序遍历序列
|
||
/// </summary>
|
||
/// <returns>中序遍历序列</returns>
|
||
public string MidOrderTraversal()
|
||
{
|
||
_orderString = string.Empty;
|
||
MidOrder(Root);
|
||
return _orderString.Trim();
|
||
}
|
||
|
||
/// <summary>
|
||
/// 后序遍历的递归函数
|
||
/// </summary>
|
||
/// <param name="current">开始递归的根结点</param>
|
||
private void PostOrder(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
return;
|
||
PostOrder(current.LeftChild);
|
||
PostOrder(current.RightChild);
|
||
_orderString += current.Data + " ";
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到后序遍历序列
|
||
/// </summary>
|
||
/// <returns>后序遍历序列</returns>
|
||
public string PostOrderTraversal()
|
||
{
|
||
_orderString = string.Empty;
|
||
PostOrder(Root);
|
||
return _orderString.Trim();
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到层次遍历序列
|
||
/// </summary>
|
||
/// <returns>层次遍历序列</returns>
|
||
public string LevelTraversal()
|
||
{
|
||
_orderString = string.Empty;
|
||
if (Root != null)
|
||
{
|
||
LinkQueue<BinTreeNode<T>> lq = new LinkQueue<BinTreeNode<T>>();
|
||
lq.EnQueue(Root);
|
||
while (lq.IsEmpty() == false)
|
||
{
|
||
BinTreeNode<T> temp = lq.QueueFront;
|
||
lq.DeQueue();
|
||
|
||
_orderString += temp.Data + " ";
|
||
if (temp.LeftChild != null)
|
||
lq.EnQueue(temp.LeftChild);
|
||
if (temp.RightChild != null)
|
||
lq.EnQueue(temp.RightChild);
|
||
}
|
||
|
||
}
|
||
return _orderString.Trim();
|
||
}
|
||
|
||
/// <summary>
|
||
/// 从current结点开始寻找find结点的父亲结点的递归函数
|
||
/// </summary>
|
||
/// <param name="current">开始递归的根结点</param>
|
||
/// <param name="find">要寻找的结点</param>
|
||
/// <returns>find结点的父亲结点</returns>
|
||
private BinTreeNode<T> FindParent(BinTreeNode<T> current, BinTreeNode<T> find)
|
||
{
|
||
if (find == null)
|
||
throw new ArgumentNullException();
|
||
if (current == null)
|
||
return null;
|
||
|
||
if (current.LeftChild != null && current.LeftChild.Equals(find))
|
||
return current;
|
||
|
||
if (current.RightChild != null && current.RightChild.Equals(find))
|
||
return current;
|
||
|
||
BinTreeNode<T> temp = FindParent(current.LeftChild, find);
|
||
|
||
if (temp != null)
|
||
return temp;
|
||
return FindParent(current.RightChild, find);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到find结点的父亲结点,若不存在返回null.
|
||
/// </summary>
|
||
/// <param name="find">要寻找的结点</param>
|
||
/// <returns>该结点的父亲结点</returns>
|
||
public BinTreeNode<T> GetParent(BinTreeNode<T> find)
|
||
{
|
||
if (find == null)
|
||
throw new ArgumentNullException();
|
||
return FindParent(Root, find);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到当前结点的左兄弟结点,若不存在返回null.
|
||
/// </summary>
|
||
/// <param name="current">当前结点</param>
|
||
/// <returns>当前结点的左兄弟结点</returns>
|
||
public BinTreeNode<T> GetLeftSibling(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
throw new ArgumentNullException();
|
||
BinTreeNode<T> parent = GetParent(current);
|
||
if (parent != null && parent.LeftChild != null && parent.LeftChild.Equals(current) == false)
|
||
return parent.LeftChild;
|
||
return null;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到当前结点的右兄弟结点,若不存在返回null.
|
||
/// </summary>
|
||
/// <param name="current">当前结点</param>
|
||
/// <returns>当前结点的右兄弟结点</returns>
|
||
public BinTreeNode<T> GetRightSibling(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
throw new ArgumentNullException();
|
||
BinTreeNode<T> parent = GetParent(current);
|
||
if (parent != null && parent.RightChild != null && parent.RightChild.Equals(current) == false)
|
||
return parent.RightChild;
|
||
return null;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 删除以current为根的子树
|
||
/// </summary>
|
||
/// <param name="current">要删除子树的根</param>
|
||
public void DeleteSubTree(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
throw new ArgumentNullException();
|
||
if (Root == null)
|
||
throw new Exception("二叉树为null.");
|
||
|
||
if (Root.Equals(current))
|
||
{
|
||
Root = null;
|
||
}
|
||
else
|
||
{
|
||
BinTreeNode<T> parent = GetParent(current);
|
||
if (parent != null && parent.LeftChild != null && parent.LeftChild.Equals(current))
|
||
parent.LeftChild = null;
|
||
if (parent != null && parent.RightChild != null && parent.RightChild.Equals(current))
|
||
parent.RightChild = null;
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// 寻找结点的递归函数
|
||
/// </summary>
|
||
/// <param name="current">开始结点</param>
|
||
/// <param name="data">数据</param>
|
||
/// <returns>数据所在的结点</returns>
|
||
private BinTreeNode<T> FindData(BinTreeNode<T> current, T data)
|
||
{
|
||
if (data == null)
|
||
throw new ArgumentNullException();
|
||
|
||
if (current == null)
|
||
return null;
|
||
|
||
if (current.Data.CompareTo(data) == 0)
|
||
return current;
|
||
|
||
BinTreeNode<T> temp = FindData(current.LeftChild, data);
|
||
if (temp != null)
|
||
return temp;
|
||
return FindData(current.RightChild, data);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 根据数据的值找到二叉树中对应的结点,若不存在返回null.
|
||
/// </summary>
|
||
/// <param name="data">数据的值</param>
|
||
/// <returns>二叉树中对应的结点</returns>
|
||
public BinTreeNode<T> Search(T data)
|
||
{
|
||
if (data == null)
|
||
throw new ArgumentNullException();
|
||
|
||
return FindData(Root, data);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 统计叶子结点个数的递归函数
|
||
/// </summary>
|
||
/// <param name="current">统计叶子结点子树的根</param>
|
||
/// <param name="count">叶子结点的个数</param>
|
||
private void FindLeafCount(BinTreeNode<T> current, ref int count)
|
||
{
|
||
if (current == null)
|
||
return;
|
||
if (current.LeftChild == null && current.RightChild == null)
|
||
{
|
||
count++;
|
||
return;
|
||
}
|
||
FindLeafCount(current.LeftChild, ref count);
|
||
FindLeafCount(current.RightChild, ref count);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到该树叶子结点的个数
|
||
/// </summary>
|
||
/// <returns>叶子结点的个数</returns>
|
||
public int GetLeafCount()
|
||
{
|
||
int count = 0;
|
||
FindLeafCount(Root, ref count);
|
||
return count;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 交换左右子树的递归函数
|
||
/// </summary>
|
||
/// <param name="current">子树的根结点</param>
|
||
private void Exchange(BinTreeNode<T> current)
|
||
{
|
||
if (current == null)
|
||
return;
|
||
if (current.LeftChild != null || current.RightChild != null)
|
||
{
|
||
BinTreeNode<T> temp = current.LeftChild;
|
||
current.LeftChild = current.RightChild;
|
||
current.RightChild = temp;
|
||
}
|
||
|
||
if (current.LeftChild != null)
|
||
Exchange(current.LeftChild);
|
||
|
||
if (current.RightChild != null)
|
||
Exchange(current.RightChild);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 交换二叉树的左右子树
|
||
/// </summary>
|
||
public void Exchange()
|
||
{
|
||
Exchange(Root);
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
例子：
|
||
|
||
```c
|
||
class Program
|
||
{
|
||
static void Main(string[] args)
|
||
{
|
||
BinTreeNode<string> a = new BinTreeNode<string>("A");
|
||
BinTreeNode<string> b = new BinTreeNode<string>("B");
|
||
BinTreeNode<string> c = new BinTreeNode<string>("C");
|
||
BinTreeNode<string> d = new BinTreeNode<string>("D");
|
||
BinTree<string> bintree = new BinTree<string>(a);
|
||
bintree.Insert(a, b, c);
|
||
bintree.Insert(b, d, null);
|
||
|
||
Console.WriteLine("前序遍历:{0}", bintree.PreOrderTraversal());
|
||
// 前序遍历:A B D C
|
||
Console.WriteLine("中序遍历:{0}", bintree.MidOrderTraversal());
|
||
// 中序遍历:D B A C
|
||
Console.WriteLine("后序遍历:{0}", bintree.PostOrderTraversal());
|
||
// 后序遍历:D B C A
|
||
Console.WriteLine("层次遍历:{0}", bintree.LevelTraversal());
|
||
// 层次遍历:A B C D
|
||
|
||
BinTreeNode<string> parent = bintree.GetParent(d);
|
||
BinTreeNode<string> lSibling = bintree.GetLeftSibling(c);
|
||
BinTreeNode<string> rSibling = bintree.GetRightSibling(b);
|
||
if (parent != null)
|
||
Console.WriteLine("结点{0}的Parent结点:{1}", d.Data, parent.Data);
|
||
else
|
||
Console.WriteLine("结点{0}无Parent.", d.Data);
|
||
// 结点D的Parent结点:B
|
||
|
||
if (lSibling != null)
|
||
Console.WriteLine("结点{0}的左兄弟结点:{1}", c.Data, lSibling.Data);
|
||
else
|
||
Console.WriteLine("结点{0}无左兄弟结点.", c.Data);
|
||
// 结点C的左兄弟结点:B
|
||
|
||
if (lSibling != null)
|
||
Console.WriteLine("结点{0}的右兄弟结点:{1}", b.Data, rSibling.Data);
|
||
else
|
||
Console.WriteLine("结点{0}无右兄弟结点.", b.Data);
|
||
// 结点B的右兄弟结点:C
|
||
|
||
bintree.DeleteSubTree(d);
|
||
Console.WriteLine("把结点{0}从二叉树中移除.", d.Data);
|
||
// 把结点D从二叉树中移除.
|
||
Console.WriteLine("前序遍历:{0}", bintree.PreOrderTraversal());
|
||
// 前序遍历: A B C
|
||
Console.WriteLine("中序遍历:{0}", bintree.MidOrderTraversal());
|
||
// 中序遍历:B A C
|
||
Console.WriteLine("后序遍历:{0}", bintree.PostOrderTraversal());
|
||
// 后序遍历: B C A
|
||
Console.WriteLine("层次遍历:{0}", bintree.LevelTraversal());
|
||
// 层次遍历: A B C
|
||
|
||
BinTreeNode<string> e = bintree.Search("A");
|
||
if (e != null && e.LeftChild != null)
|
||
Console.WriteLine("寻找结点{0}的左孩子为{1}", e.Data, e.LeftChild.Data);
|
||
else
|
||
Console.WriteLine("未找到{0}结点或者{0}结点左孩子为null", a.Data);
|
||
// 寻找结点A的左孩子为B
|
||
|
||
Console.WriteLine("叶子结点的个数:{0}", bintree.GetLeafCount());
|
||
// 叶子结点的个数:2
|
||
|
||
bintree.Exchange();
|
||
Console.WriteLine("前序遍历:{0}", bintree.PreOrderTraversal());
|
||
// 前序遍历:A C B
|
||
Console.WriteLine("中序遍历:{0}", bintree.MidOrderTraversal());
|
||
// 中序遍历: C A B
|
||
Console.WriteLine("后序遍历:{0}", bintree.PostOrderTraversal());
|
||
// 后序遍历: C B A
|
||
Console.WriteLine("层次遍历:{0}", bintree.LevelTraversal());
|
||
// 层次遍历: A C B
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
---
|
||
## 3. 树与森林
|
||
|
||
### 3.1 树的存储
|
||
|
||
（1）顺序存储
|
||
|
||
|
||
|
||
（2）链式存储
|
||
|
||
A. 存储双亲结点
|
||
|
||
|
||
|
||
B. 存储孩子结点
|
||
|
||
|
||
|
||
|
||
C. 存储孩子和兄弟结点
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
### 3.2 树与二叉树的相互转换
|
||
|
||
（1）树转换成二叉树
|
||
|
||
按照左孩子，右兄弟规则。
|
||
|
||
|
||
|
||
|
||
（2）二叉树转换成树
|
||
|
||
按照左孩子，右兄弟规则的逆过程。
|
||
|
||
|
||
|
||
|
||
|
||
|
||
### 3.3 森林与二叉树的相互转换
|
||
|
||
（1）森林转化成二叉树
|
||
|
||
设$F=(T_1,T_2,\cdots,T_n)$为树$T_1,T_2,\cdots,T_n$组成的森林，$B(F)$为其对应的二叉树。
|
||
- 若$n=0$，则$B(F)=\phi$。
|
||
- 若$n>0$，`$B(F)$的根为$Root(T_1)$，$B(F)$的左子树由$T_1$的诸子树组成，右子树由$B(\lbrace T_2,\cdots,T_n\rbrace)$组成。
|
||
|
||
|
||
方式1：
|
||
|
||
|
||
|
||
方式2：
|
||
|
||
|
||
|
||
|
||
（2）二叉树转化成森林
|
||
|
||
设$B=(Root,LB,RB)$是一颗二叉树，$F(B)=\lbrace T_1,T_2,\cdots,T_n \rbrace$为其对应的森林。
|
||
- 若$B=\phi$，则$F(B)=\phi$ $(n=0)$。
|
||
- 若$B$不等于$\phi$，则$T_1$的根为二叉树$B$的根$Root$，$T_1$的子树森林由$B$的左子树$LB$转换而成，其余树组成的森林$F(T)=\lbrace T_2,\cdots,T_n \rbrace$由$B$的右子树$RB$转换而成。
|
||
|
||
方式1：
|
||
|
||
|
||
|
||
方式2：
|
||
|
||
|
||
|
||
|
||
### 3.4 树与森林的遍历
|
||
|
||
（1）树的遍历
|
||
|
||
|
||
|
||
前序遍历：首先访问根结点；然后前序遍历每棵子树。
|
||
- 前序遍历序列：A B E C F H G D
|
||
|
||
后序遍历：首先后序遍历每棵子树；然后访问根结点。
|
||
- 后序遍历序列：E B H F G C D A
|
||
|
||
|
||
（2）森林的遍历
|
||
|
||
|
||
|
||
前序遍历：首先访问第一棵树的根结点；然后前序遍历第一棵树的子树；再前序遍历由其余树组成的森林。
|
||
- 前序遍历序列：A B C D E F G H I J
|
||
|
||
后序遍历：先后序遍历第一棵树的子树；然后访问第一棵树的根结点；再后序遍历由其余树组成的森林。
|
||
- 后序遍历序列：B C D A F E H J I G
|
||
|
||
|
||
---
|
||
## 4. 线索二叉树
|
||
|
||
### 4.1 引入
|
||
|
||
性质：设二叉树利用二叉链表存储且结点个数为$n$，则该二叉树的链域个数为$2n$，空链域个数为$n+1$。
|
||
|
||
|
||
想法：利用空链域存储该树按照某种方式遍历（前序、中序、后序）的前趋或后继结点。
|
||
|
||
|
||
结构：
|
||
|
||
|
||
|
||
|
||
### 4.2 相关概念
|
||
|
||
**线索**：在这种结构中指向其前趋或后继结点的指针。
|
||
|
||
**线索二叉树**：加上线索的二叉树。
|
||
|
||
**线索化**：把二叉树变成线索二叉树的过程。
|
||
|
||
**线索化的方式**：前序线索化、中序线索化、后序线索化
|
||
|
||
例子：中序线索化
|
||
|
||
|
||
|
||
例子：前序线索化
|
||
|
||
|
||
|
||
|
||
---
|
||
## 5. 哈夫曼树及其编码（Huffman）
|
||
|
||
### 5.1 哈夫曼树的定义
|
||
|
||
**路径**：连接两个结点的分支，构成这两个结点的路径。
|
||
|
||
**路径长度**：两个结点路径上的分支数。
|
||
|
||
**结点的权**：为结点赋的一个有意义的实数。
|
||
|
||
**结点的带权路径长度**：根结点到该结点的路径长度与该结点权值的乘积。
|
||
|
||
**树的带权路径长度**：树中所有叶子结点的带权路径长度之和。记为：$WPL=\sum_{i=1}^{n}\omega_iL_i$，$n$为叶子结点的个数。
|
||
|
||
**哈夫曼树**：$n$个带权叶子结点构成的所有二叉树中，带权路径长度$WPL$最小的二叉树。（最优二叉树）
|
||
|
||
|
||
### 5.2 哈夫曼树的构造
|
||
|
||
第1步：根据给定的$n$个权值$\omega_1,\omega_2,\cdots,\omega_n$，构成$n$棵二叉树的森林$F=\lbrace T_1,T_2,\cdots,T_n \rbrace$，其中每棵二叉树$T_i$中都只有一个权值`$\omega_i$的根结点，其左右子树均为空。
|
||
|
||
第2步：在森林$F$中选出两棵根结点权值最小的树作为一棵新树的左右子树，且置新树的根结点的权值为其左右子树上根结点的权值之和。
|
||
|
||
第3步：从$F$中删除构成新树的哪两棵树，同时把新树加入$F$中。
|
||
|
||
第4步：重复第2和3步，直到$F$中只含有一棵树为止，此树便是Huffman树。
|
||
|
||
例子：给定权集$\omega=\lbrace 2,3,4,7,8,9 \rbrace$ ，试构造关于$\omega$的一颗哈夫曼树，并求其带权路径长度 。
|
||
|
||
|
||
|
||
### 5.3 哈夫曼编码的概念
|
||
|
||
**前缀码规则**：对字符集编码时，字符集中任一字符的编码都不是其它字符编码的前缀。
|
||
|
||
例子：
|
||
|
||
`A：0 B：00 C：01 D：10`（违反前缀码规则）
|
||
|
||
000010 BBD、AAAAD、BAAD、AABD （不唯一，解码时有二义性）
|
||
|
||
`A：00 B：01 C：10 D：11`（满足前缀码规则）
|
||
|
||
000010 AAC （唯一）
|
||
|
||
|
||
**哈夫曼编码**：将哈夫曼树中，每个分支结点的左分支标0，右分支标1，把从根结点到每个叶子结点的路径上的标号连接起来作为该叶子结点所代表符号的编码，这样得到的编码称为Huffman编码。（优点：满足前缀码规则）
|
||
|
||
|
||
例子：对所要发送的数据进行二进制编码。
|
||
|
||
state，seat，act，tea，cat，set，a，eat
|
||
|
||
第一种编码方式：
|
||
|
||
` 's'："000” 't'：“001” 'a'：“010” 'e'：“011” 'c'：“100” ','：“110” `
|
||
|
||
此种编码满足前缀码规则，但编码过长。eat：011010001
|
||
|
||
第二种编码方式：
|
||
|
||
统计字符出现的频数：‘s’：3 ‘t’：8 ‘a’：7 ‘e’：5 ‘c’：2 ‘,’：7
|
||
|
||
|
||
|
||
|
||
`
|
||
'a'："00” ','：“01” 't'：“10” 'e'：“110” 'c'：“1110” 's'：“1111”
|
||
`
|
||
|
||
- eat：1100010
|
||
- state：1111100010110
|
||
- seat：11111100010
|
||
|
||
|
||
|
||
|
||
### 5.4 哈夫曼编码的实现
|
||
|
||
|
||
|
||
```c
|
||
namespace NonLinearStruct
|
||
{
|
||
/// <summary>
|
||
/// 表示Huffman树的结点
|
||
/// </summary>
|
||
public class HuffmanTreeNode : BinTreeNode<char>
|
||
{
|
||
/// <summary>
|
||
/// 结点的权值
|
||
/// </summary>
|
||
public int Weight { get; set; }
|
||
|
||
/// <summary>
|
||
/// 叶子结点 -- 字符
|
||
/// </summary>
|
||
/// <param name="data">字符</param>
|
||
/// <param name="weight">结点的权</param>
|
||
public HuffmanTreeNode(char data, int weight) : base(data)
|
||
{
|
||
Weight = weight;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 其它结点
|
||
/// </summary>
|
||
/// <param name="weight">结点的权</param>
|
||
public HuffmanTreeNode(int weight) : base('\0')
|
||
{
|
||
Weight = weight;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
```c
|
||
namespace NonLinearStruct
|
||
{
|
||
/// <summary>
|
||
/// Huffman字典
|
||
/// </summary>
|
||
public class HuffmanDicItem
|
||
{
|
||
/// <summary>
|
||
/// 获取或设置字符
|
||
/// </summary>
|
||
public char Character { get; set; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置编码
|
||
/// </summary>
|
||
public string Code { get; set; }
|
||
|
||
/// <summary>
|
||
/// 构造函数
|
||
/// </summary>
|
||
/// <param name="charactor">字符</param>
|
||
/// <param name="code">编码</param>
|
||
public HuffmanDicItem(char charactor, string code)
|
||
{
|
||
Character = charactor;
|
||
Code = code;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
using System.Collections.Generic;
|
||
using System.Linq;
|
||
namespace NonLinearStruct
|
||
{
|
||
/// <summary>
|
||
/// Huffman树
|
||
/// </summary>
|
||
public class HuffmanTree
|
||
{
|
||
/// <summary>
|
||
/// 构造Huffman树初始的森林
|
||
/// </summary>
|
||
/// <param name="str">字符串</param>
|
||
/// <returns>结点的集合，构成初始的森林</returns>
|
||
private List<HuffmanTreeNode> CreateInitForest(string str)
|
||
{
|
||
if (string.IsNullOrEmpty(str))
|
||
throw new ArgumentNullException();
|
||
|
||
List<HuffmanTreeNode> result = new List<HuffmanTreeNode>();
|
||
char[] charArray = str.ToCharArray();
|
||
List<IGrouping<char, char>> lst = charArray.GroupBy(a => a).ToList();
|
||
|
||
foreach (IGrouping<char, char> g in lst)
|
||
{
|
||
char data = g.Key;
|
||
int weight = g.ToList().Count;
|
||
HuffmanTreeNode node = new HuffmanTreeNode(data, weight);
|
||
result.Add(node);
|
||
}
|
||
return result;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 构造Huffman树
|
||
/// </summary>
|
||
/// <param name="sources">初始的结点的集合</param>
|
||
/// <returns>Huffman树的Root</returns>
|
||
private HuffmanTreeNode CreateHuffmanTree(List<HuffmanTreeNode> sources)
|
||
{
|
||
if (sources == null)
|
||
throw new ArgumentNullException();
|
||
if (sources.Count < 2)
|
||
throw new ArgumentException("构造Huffman树，最少为2个结点。");
|
||
|
||
HuffmanTreeNode root = default(HuffmanTreeNode);
|
||
bool isNext = true;
|
||
|
||
while (isNext)
|
||
{
|
||
List<HuffmanTreeNode> lst = sources.OrderBy(a => a.Weight).ToList();
|
||
HuffmanTreeNode n1 = lst[0];
|
||
HuffmanTreeNode n2 = lst[1];
|
||
int weight = n1.Weight + n2.Weight;
|
||
|
||
HuffmanTreeNode node = new HuffmanTreeNode(weight);
|
||
node.LeftChild = n1;
|
||
node.RightChild = n2;
|
||
|
||
if (lst.Count == 2)
|
||
{
|
||
root = node;
|
||
isNext = false;
|
||
}
|
||
else
|
||
{
|
||
sources = lst.GetRange(2, lst.Count - 2);
|
||
sources.Add(node);
|
||
}
|
||
}
|
||
return root;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 创建Huffman编码的字典
|
||
/// </summary>
|
||
/// <param name="code"></param>
|
||
/// <param name="current"></param>
|
||
/// <returns></returns>
|
||
private List<HuffmanDicItem> CreateHuffmanDict(string code, HuffmanTreeNode current)
|
||
{
|
||
if (current == null)
|
||
throw new ArgumentNullException();
|
||
|
||
List<HuffmanDicItem> result = new List<HuffmanDicItem>();
|
||
if (current.LeftChild == null && current.RightChild == null)
|
||
{
|
||
result.Add(new HuffmanDicItem(current.Data, code));
|
||
}
|
||
else
|
||
{
|
||
List<HuffmanDicItem> dictL = CreateHuffmanDict(code + "0",
|
||
(HuffmanTreeNode)current.LeftChild);
|
||
List<HuffmanDicItem> dictR = CreateHuffmanDict(code + "1",
|
||
(HuffmanTreeNode)current.RightChild);
|
||
|
||
result.AddRange(dictL);
|
||
result.AddRange(dictR);
|
||
}
|
||
return result;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 创建Huffman编码的字典
|
||
/// </summary>
|
||
/// <param name="root">Huffman树</param>
|
||
/// <returns>Huffman字典</returns>
|
||
private List<HuffmanDicItem> CreateHuffmanDict(HuffmanTreeNode root)
|
||
{
|
||
if (root == null)
|
||
throw new ArgumentNullException();
|
||
|
||
return CreateHuffmanDict(string.Empty, root);
|
||
}
|
||
|
||
/// <summary>
|
||
/// 对字符串进行编码
|
||
/// </summary>
|
||
/// <param name="dict">Huffman字典</param>
|
||
/// <param name="str">编码字符串</param>
|
||
/// <returns>编码后的字符串</returns>
|
||
public string StringToHuffmanCode(out List<HuffmanDicItem> dict, string str)
|
||
{
|
||
List<HuffmanTreeNode> forest = CreateInitForest(str);
|
||
HuffmanTreeNode root = CreateHuffmanTree(forest);
|
||
dict = CreateHuffmanDict(root);
|
||
string result = ToHuffmanCode(str, dict);
|
||
return result;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 给定Huffman字典对编码进行解码
|
||
/// </summary>
|
||
/// <param name="dict">Huffman字典</param>
|
||
/// <param name="code">解码的字符</param>
|
||
/// <returns>解码后的字符</returns>
|
||
public string HuffmanCodeToString(List<HuffmanDicItem> dict, string code)
|
||
{
|
||
string result = string.Empty;
|
||
for (int i = 0; i < code.Length;)
|
||
{
|
||
foreach (HuffmanDicItem item in dict)
|
||
{
|
||
if (code[i] == item.Code[0] && item.Code.Length + i <= code.Length)
|
||
{
|
||
string temp = code.Substring(i, item.Code.Length);
|
||
if (temp == item.Code)
|
||
{
|
||
result += item.Character;
|
||
i += item.Code.Length;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
return result;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 利用Huffman字典对字符集进行编码
|
||
/// </summary>
|
||
/// <param name="source">编码的字符</param>
|
||
/// <param name="lst">Huffman字典</param>
|
||
/// <returns>编码后的字符串</returns>
|
||
private string ToHuffmanCode(string source, List<HuffmanDicItem> lst)
|
||
{
|
||
if (string.IsNullOrEmpty(source))
|
||
throw new ArgumentNullException();
|
||
if (lst == null)
|
||
throw new ArgumentNullException();
|
||
|
||
string result = string.Empty;
|
||
for (int i = 0; i < source.Length; i++)
|
||
{
|
||
result += lst.Single(a => a.Character == source[i]).Code;
|
||
}
|
||
return result;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
客户端代码：
|
||
|
||
```c
|
||
class Program
|
||
{
|
||
static void Main(string[] args)
|
||
{
|
||
string str = "state,seat,act,tea,cat,set,a,eat";
|
||
Console.WriteLine(str);
|
||
// state,seat,act,tea,cat,set,a,eat
|
||
|
||
HuffmanTree huffmanTree = new HuffmanTree();
|
||
List<HuffmanDicItem> dic;
|
||
string huffmanCode = huffmanTree.StringToHuffmanCode(out dic, str);
|
||
string temp = string.Empty;
|
||
for (int i = 0; i < dic.Count; i++)
|
||
{
|
||
temp += @"'" + dic[i].Character + "':" + "\"" + dic[i].Code + "\"\r\n";
|
||
}
|
||
Console.WriteLine(temp.Substring(0, temp.Length - 2));
|
||
// 'a':"00"
|
||
// ',':"01"
|
||
// 't':"10"
|
||
// 'e':"110"
|
||
// 'c':"1110"
|
||
// 's':"1111"
|
||
Console.WriteLine(huffmanCode);
|
||
// 1111100010110011111110001001001110100110110000111100010011111110100100011100010
|
||
|
||
string decode = huffmanTree.HuffmanCodeToString(dic, huffmanCode);
|
||
Console.WriteLine(decode);
|
||
//state,seat,act,tea,cat,set,a,eat
|
||
}
|
||
}
|
||
```
|
||
|
||
|