数据结构基础学习之（树与二叉树）
2019-04-05 本文已影响0人
JiaJianHuang
主要知识点：
- 树的定义及常用术语
- 树的存储表示
- 二叉树、满二叉树和完成二叉树的定义
- 二叉树的遍历此操作实现
- 哈夫曼树及其编码
- 树、森林与二叉树之间的转换
一、树
1. 概念：
- 定义： 树是由n（n≥0）个结点组成的有限集合
- 特点：
- 有且仅有一个称为根(Root)的结点；
- 其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。
- 树的常用术语
结点(node)
- 由一个数据元素及关联其子树的边组成
结点路径
- 若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从k1到kj的一条路径(Path)或道路。
路径的长度
- 指路径所经过的边(即连接两个结点的线段)的数目
结点的度(degree)
- 结点拥有的子树的数目
树的度
- 一棵树中最大的结点度数（拥有最多子树的节点，即结点的度最大值）
叶子结点(leaf)
- 结点的度为0的结点(没有子树的节点)，也叫终端结点
分支结点
- 结点的度不为0的结点（有子树的节点），也叫非终端结点
孩子结点
- 一个结点的孩子结点是指这个结点的子树的根结点
双亲结点(parents)
- 一个结点有孩子结点，则这个结点称为它孩子结点的双亲结点
子孙结点
- 即一个结点A所有子树的结点称为该结点A的子孙结点
祖先结点
- 即一个结点A的祖先结点是指路径中除结点A外的的结点
兄弟结点(sibling)
- 同一双亲结点的孩子结点之间互成为兄弟结点
结点的层次
- 从根结点算起，根为第一层，它的孩子为第二层
树的深度
- 树中结点的最大层次数
有序树与无序树
- 如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树
森林
- m(m>=0)棵互不相交的树的集合
二、 二叉树
定义：
- 二叉树(BinaryTree): 是n(n≥0)个结点的有限集, 它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
- 满二叉树： 是二叉树的特殊形态，除叶节点外的所有结点都有左右子树的二叉树，称为满二叉树
- 完全二叉树： 也是二叉树的特殊形态，
- 单分支树：所有节点都没有左结点（或右结点）的二叉树
二叉树五种基本形态
5.4二叉树的5种基本形态.png
二叉树的性质
- 二叉树第i层上的结点数目最多为
- 深度为k的二叉树至多有
个结点。
- 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
- 具有n个结点的完全二叉树，其深度为
或
- 对于具有n个结点的完全二叉树，若从根结点开始自上而下，从左到右开始编号，对于任意编号i（0<=i<n）的结点有：
1. 若i=0,则结点为根结点，没有双亲，若i>0,则它的双亲结点编号为
2. 若2i+1 >=n ,则编号i结点无左孩子，否则编号2i+1的结点就是它的左孩子
3. 若2i+2 >=n ,则编号i结点无右孩子，否则编号2i+2的结点就是它的右孩子
- 满二叉树和完全二叉树示意图
5.7满二叉树和完全二叉树.png
二叉树存储结构
- 顺序存储结构示意图
5.9二叉树顺序存储结构示意图.png
- 链式存储结构示意图
5.10二叉树链式存储的结点结构.png
5.11二叉树及其三叉链式存储结构.png
二叉树的遍历
- 前序遍历
/**
* 递归的前序遍历
* <p>
* 1. 从根结点出发
* 2. 先遍历完左子树
* 3. 再遍历右子树
* <p>
* （注意：顺序: 中左右）
*
* @param treeNode
*/
public void preOrderTraverse(BiTreeNode treeNode) {
if (treeNode == null) return;
//结点数据
System.out.println(treeNode.data.toString());
//先遍历左子树
preOrderTraverse(treeNode.LChild);
//然后遍历右子树
preOrderTraverse(treeNode.RChild);
}
/**
* 非递归的前序遍历
*/
public void preOrderTraverse() {
//获取根结点
BiTreeNode<T> node = root;
if (node == null) return;
//构造一个栈，由于存储右子树结点
LinkStack<BiTreeNode> stack = new LinkStack<>();
stack.push(node);
while (!stack.isEmpty()) {
//弹出栈顶结点
node = stack.pop();
//访问该结点
System.out.println(node.data.toString());
while (node != null) {
//如果左结点不为空，则访问
if (node.LChild != null)
System.out.println(node.LChild.data);
//如果右结点不为空，则先压入栈中
if (node.RChild != null)
stack.push(node.RChild);
//继续遍历左结点
node = node.LChild;
}
}
}
- 中序遍历
/**
* 中序遍历（递归方式）
* <p>
* 1. 从左子树出发开始遍历
* 2. 遍历到根结点
* 3. 又从根结点出发，遍历右子树
* <p>
* （注意：顺序: 左中右）
*
* @param treeNode
*/
public void inOrderTraverse(BiTreeNode treeNode) {
if (treeNode == null) return;
//遍历左子树
inOrderTraverse(treeNode.LChild);
//结点数据
System.out.println(treeNode.data.toString());
//遍历右子树
inOrderTraverse(treeNode.RChild);
}
/**
* 中序遍历（非递归）
*/
public void inOrderTraverse() {
BiTreeNode<T> node = this.root;
if (node != null) {
LinkStack<BiTreeNode> stack = new LinkStack<>();
stack.push(node);
while (!stack.isEmpty()) {
while (stack.peek() != null)
stack.push(stack.peek().LChild); //把左结点入栈，直到最左下的结点
//弹出空结点
stack.pop();
if (!stack.isEmpty()) {
node = stack.pop();
//打印结点
System.out.print(node.data.toString());
//把该结点的右子结点入栈
stack.push(node.RChild);
}
}
}
}
- 后序遍历
/**
* 后序遍历
* <p>
* 1. 以从左到右的方式
* 2. 先遍历左子树
* 3. 然后遍历右子树
* 4. 最后遍历右子树
* <p>
* 顺序： 左右中
*/
public void postOrderTraverse(BiTreeNode treeNode) {
if (treeNode == null) return;
postOrderTraverse(treeNode.LChild);
postOrderTraverse(treeNode.RChild);
System.out.println(treeNode.data.toString());
}
/**
* 后序遍历（非递归）
*/
public void postOrderTraverse() {
//获取根结点
BiTreeNode node = this.root;
if (node != null) {
LinkStack<BiTreeNode> stack = new LinkStack<>();
//将根结点入栈
stack.push(node);
//设置结点访问标识
boolean flag;
//设置指针，指向访问过的结点
BiTreeNode p = null;
while (!stack.isEmpty()) {
//将结点的左子结点入栈
while (stack.peek() != null)
stack.push(stack.peek().LChild);
//弹出空结点
stack.pop();
while (!stack.isEmpty()) {
//查看栈顶元素
node = stack.peek();
//如果该结点的右子结点为空，或已访问过，则该结点可以出栈访问
if (node.RChild == null || node.RChild == p) {
//访问结点
System.out.print(node.data.toString());
//出栈
stack.pop();
//已访问指针指向该结点
p = node;
//标识为已访问
flag = true;
} else {
//否则，将该结点的右子结点入栈，
stack.push(node.RChild);
// 标识该结点还没访问
flag = false;
}
if (!flag) {
break;
}
}
}
}
}
- 层次遍历
/**
* 层次遍历
*/
public void levelTraverse() {
BiTreeNode<T> node = this.root;
if (node != null) {
//初始化队列
LinkQueue<BiTreeNode> queue = new LinkQueue<>();
//根结点入队列
queue.offer(node);
while (!queue.isEmpty()) {
//出队列
node = queue.poll();
//访问该结点
System.out.println(node.data.toString());
//该结点的左子结点入队列
if (node.LChild != null) {
queue.offer(node.LChild);
}
//该结点的右子结点入队列
if (node.RChild != null) {
queue.offer(node.RChild);
}
}
}
}
二叉树的建立
- 由前序遍历和中序遍历，或后序遍历和中序遍历推导建立二叉树
/**
* 二叉树的建立
*
* @param preOrder 前序遍历的序列
* @param inOrder 中序遍历的序列
* @param preIndex 前序遍历开始位置
* @param inIndex 中序遍历开始位置
* @param count 结点数
*/
public LinkBiTree(String preOrder, String inOrder, int preIndex, int inIndex, int count) {
if (count > 0) {
//获取前序遍历的序列的根结点
char r = preOrder.charAt(preIndex);
//记录根结点在中序遍历中的位置
int i = 0;
for (; i < count; i++) {
if (r == inOrder.charAt(i + inIndex)) {
break;
}
}
root = new BiTreeNode(r);
root.LChild = new LinkBiTree(preOrder, inOrder, preIndex + 1, inIndex, i).root;
root.RChild = new LinkBiTree(preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1).root;
}
}
- 由标明空子树的前序遍历建立二叉树
/**
* 由标明的空子树建立二叉树
*
* @param preOrder
*/
private static int preIndex = 0;
public LinkBiTree(String preOrder) {
//获取前序遍历中的根结点
char c = preOrder.charAt(preIndex++);
//如果字符不为#
if ('#' != c) {
//创建根结点
root = new BiTreeNode(c);
//创建左子树
root.LChild = new LinkBiTree(preOrder).root;
//创建右子树
root.RChild = new LinkBiTree(preOrder).root;
} else {
root = null;
}
}
- 由完全二叉树顺序存储序列建立二叉树
/**
* 使用完全二叉树的顺序存储结构建立二叉链式存储结构
*
* @param sqBiTree 序列
* @param index 根结点标识
*/
public LinkBiTree(String sqBiTree, int index) {
if (index < sqBiTree.length()) {
root = new BiTreeNode(sqBiTree.charAt(index));
//建立左右子树
root.LChild = new LinkBiTree(sqBiTree, 2 * index + 1).root;
root.RChild = new LinkBiTree(sqBiTree, 2 * index + 2).root;
}
}
三、哈夫曼树及哈夫曼编码
1. 基本概念：
- 树的路径长度： 是从树根结点到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
- 结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
- 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
- 树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和
- 公式： wpl=
-
: 第k个结点的权值
-
：根结点到第k个结点的路径长度
- 最优二叉树：二叉树带权路径长度值最小，它就是一棵最优二叉树或哈夫曼树
- 赫夫曼树中不存在度为1的结点(赫夫曼树的每一分支结点都是由两棵子树合并产生的新结点)
2. 构造哈夫曼树
- 步骤：（假设带权值的叶子结点为 {E10,B15,A5,C40,D30}）
- 先把这些叶子结点按权值从小到大排序，组成有序序列：A5, E10, B15, D30, C40
- 取两权值最小的结点，作为新结点N1的左右孩子，注意：权值小的结点作为左孩子；新结点的权值为这两个结点权值的和；即5+10=15；
- 把新结点N1 加入有序序列：
B15, D30, C40
- 重复步骤2，把N1和B结点作为新结点N2的左右孩子, 权值为：15+15=30
- 重复步骤3，有序序列：
` D30, C40
- 重复步骤2，把N2和D结点作为新结点N3的左右孩子, 权值为：30+30=60
- 重复步骤3，有序序列： C40,
`
- 重复步骤2，把C和N3结点作为新结点T的左右孩子, 权值为：40+60=100
- 因为结点T是二叉树的根结点，所以完成的哈夫曼树的构造
- 完成哈夫曼树图
- 带权路径长度为： WPL=401 + 302+153+104+5*4= 205
5.4哈夫曼树构造过程.png
- 构造哈夫曼树总结：
- 根据给定的n个权值{w1,w2,w3...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti中只有一个带权值的根结点，其左右子树为空
- 在集合F中选取权值最小的树，作为左右子树(权值较小的树作为左子树)构造一棵新的二叉树，且新二叉树的权值为其左右子树权值的和
- 在F中删除这两棵树，同时使用新的二叉树加入F中
- 重复步骤2，3，直到F中只含一棵树为止，则可以得到哈夫曼树
3. 哈夫曼树编码
-
定义哈夫曼树左分支代表0， 右分支代表1
-
从根结点到叶子结点所经过的路径分支组成的0和1序列，就是哈夫曼树编码
-
哈夫曼树编码示意图
5.25哈夫曼树及编码.png
四、树、森林与二叉树的转换
1. 树转换为二叉树
-
加线。所有兄弟结点之间加一条线
-
去线。对树的每个结点，只保留它与第一个孩子结点的连线，删除其它孩子结点连线
-
层次调整。以树的根结点为轴心，顺时针旋转一定的角度，注意：第一个孩子结点作为二叉树结点的左孩子结点，兄弟结点转换过来的孩子结点作为右孩子结点。
-
转换示意图
5.29树转换二叉树.png
2. 森林转换二叉树
- 将森林中的每棵树转换为二叉树
- 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用连接起来
- 重复步骤2，直到所有二叉树连接起来，就得到森林转换过来的二叉树
- 示意图
5.31森林转换为二叉树.png
- 二叉树转换为树
- 加线。若某结点是其双亲结点的左孩子，则将该结点沿着右分支向下的所有结点与该结点的双亲结点用线连接
- 删线。 将树中所有双亲结点与右孩子结点的连线删除
- 层次调整。以树的根结点为轴心，逆时针旋转一定的角度
- 示意图
5.30二叉树转换为树.png
- 二叉树转换为森林
- 从根结点开始， 若右孩子存在，则把右孩子结点的连线删除，得分离的二叉树后，看其右孩子是否存在，存在则删除，直到所有右孩子连线都删除为止
- 再将分离后的二叉树转换为树，
- 示意图
5.32二叉树转换森林.png
五、树的存储结构
表示法
-
双亲表示法
5.33双亲链表存储结构.png
-
孩子表示法
5.34孩子链表存储结构.png
-
双亲孩子表示法
5.35双亲孩子链表存储结构.png
-
孩子兄弟表示法（应用最广泛）
5.33孩子兄弟链表存储结构.png
