数据结构与算法(九)

树结构基础部分

二叉树

为什么需要该数据结构

数组存储方式的分析

• 优点：

  • 通过 下标 方式访问元素，速度快
  • 对于 有序数组，还可以使用二分查找提高检索速度

• 缺点：如果要检索具体某个值或插入值（按一定顺序）会整体移动，效率较低，如下的示意图
  

链表存储方式的分析

优点：在一定程度上对数组存储方式有优化

例如：插入一个数值节点，只需要将插入节点，链接到链表中即可，同理，删除效率也很好

• 缺点：检索效率较低

  需要从头结点开始遍历查找。

简单说：

• 数组访问快，增删慢
• 链表增删快，访问慢

那么就出现了 树 这种数据结构

树存储数据方式分析

提供数据 存储 、读取 效率。

例如：利用 二叉排序树（Binary Sort Tree），既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改 的速度

如图所示：

• 插入时，小的数在 左节点、大的数在 右节点
• 查找时：根据插入事的特性，基本上就类似折半查找了，每次都过滤一半的节点
• 删除时：只需要移动相邻的节点的引用

树的常用术语

• 节点：每一个圆圈表示一个节点，也称节点对象

• 根节点：最上面，最顶部的那个节点，也就是一棵树的入口

• 父节点：有子节点的节点

• 子节点

• 叶子节点：没有子节点的节点

• 节点的权：可以简单的理解为节点值

  有时候也用 路径 来表示

• 路径：从 root 节点找到该节点的路线

• 层

• 子树：有子节点的父子两层就可以称为是一个子树

• 树的高度：最大层数

• 森林：多颗子树构成森林

二叉树的概念

• 树有很多种，每个节点 最多只能有两个子节点 的一种形式称为 二叉树

• 二叉树的子节点分为 左节点 和 右节点
  

• 如果该二叉树的所有 叶子节点 都在 最后一层，并且 节点总数 = 2^n-1 （n 为层数），则我们称为 满二叉树
  

• 如果该二叉树的所有叶子节点都在最 后一层或倒数第二层，而且 最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为 完全二叉树
  

二叉树的遍历说明

有三种：

• 前序遍历：先输出父节点，再遍历左子树（递归）和右子树（递归）
• 中序遍历：先遍历左子树（递归），再输出父节点，再遍历右子树（递归）
• 后序遍历：先遍历左子树（递归），再遍历右子树（递归），最后输出父节点

前、中、后序主要区别是输出父节点的时间来区分

二叉树遍历思路分析

• 前序遍历：

  1. 先输出当前节点（初始节点是 root 节点）
  2. 如果左子节点不为空，则递归继续前序遍历
  3. 如果右子节点不为空，则递归继续前序遍历

  上图的输出顺序为：1、2、3、4

• 中序遍历：

  1. 如果当前节点的左子节点不为空，则递归中序遍历
  2. 输出当前节点
  3. 如果当前节点的右子节点不为空，则递归中序

  上图的输出顺序为：2、1、4、3

• 后序遍历：

  1. 如果左子节点不为空，则递归继续前序遍历
  2. 如果右子节点不为空，则递归继续前序遍历
  3. 输出当前节点

  上图的输出顺序为：2、4、3、1

遍历代码实现

复制代码

	//定义节点
	class HeroNode{
	private int no;//当前节点编号
	private String name;//当前节点名字
	private HeroNode left;//当前节点左子树
	private HeroNode right;//当前节点右子树
	public HeroNode(int no, String name) {
	this.no = no;
	this.name = name;
	}
	public int getNo() {
	return no;
	}
	public void setNo(int no) {
	this.no = no;
	}
	public String getName() {
	return name;
	}
	public void setName(String name) {
	this.name = name;
	}
	public HeroNode getLeft() {
	return left;
	}
	public void setLeft(HeroNode left) {
	this.left = left;
	}
	public HeroNode getRight() {
	return right;
	}
	public void setRight(HeroNode right) {
	this.right = right;
	}
	@Override
	public String toString() {
	return "HeroNode{" +
	"no=" + no +
	", name='" + name + '\'' +
	'}';
	}
	//前序遍历
	public void preOrder(){
	//先输出当前节点
	System.out.println(this);
	//递归遍历左子节点
	if(this.left != null){
	this.left.preOrder();
	}
	//递归遍历右子节点
	if(this.right != null){
	this.right.preOrder();
	}
	}
	//中序遍历
	public void infixOrder(){
	//先输出左子树
	if(this.left != null){
	this.left.infixOrder();
	}
	//输出当前节点
	System.out.println(this);
	//输出右子树
	if(this.right != null){
	this.right.infixOrder();
	}
	}
	//后序遍历
	public void postOrder(){
	//先输出左子树
	if(this.left != null){
	this.left.postOrder();
	}
	//输出右子树
	if(this.right != null){
	this.right.postOrder();
	}
	//输出当前节点
	System.out.println(this);
	}
	}
	//创建二叉树
	class BinaryTree{
	private HeroNode root;
	public void setRoot(HeroNode root) {
	this.root = root;
	}
	//前序遍历
	public void preOrder(){
	if(this.root != null){
	this.root.preOrder();
	}else{
	System.out.println("当前二叉树为空");
	}
	}
	//中序遍历
	public void infixOrder(){
	if(this.root != null){
	this.root.infixOrder();
	}else{
	System.out.println("当前二叉树为空");
	}
	}
	//后序遍历
	public void postOrder(){
	if(this.root != null){
	this.root.postOrder();
	}else{
	System.out.println("当前二叉树为空");
	}
	}
	}
	//创建二叉树
	BinaryTree binaryTree = new BinaryTree();
	//手动创建二叉树
	HeroNode root = new HeroNode(1,"宋江");
	HeroNode hero1 = new HeroNode(2,"吴用");
	HeroNode hero2 = new HeroNode(3,"卢俊义");
	HeroNode hero3 = new HeroNode(4,"林冲");
	root.setLeft(hero1);
	root.setRight(hero2);
	hero2.setRight(hero3);
	binaryTree.setRoot(root);
	//遍历二叉树
	System.out.println("前序遍历");
	binaryTree.preOrder();
	//中序遍历
	System.out.println("中序遍历");
	binaryTree.infixOrder();
	//后序遍历
	System.out.println("后序遍历");
	binaryTree.postOrder();

二叉树查找

要求：

1. 编写前、中、后序查找方法
2. 并分别使用三种查找方式，查找 id=5 的节点
3. 并分析各种查找方式，分别比较了多少次

由于二叉树的查找是遍历查找，所以就简单了，前面遍历规则已经写过了，改写成查找即可

复制代码

	//在节点中增加查找方法
	//前序查找
	public HeroNode preOrderSearch(int no){
	if(this.no == no){
	return this;
	}
	HeroNode resNode = null;
	if(this.left != null){
	resNode = this.left.preOrderSearch(no);
	}
	if(resNode != null){
	return resNode;
	}
	if(this.right != null){
	resNode = this.right.preOrderSearch(no);
	}
	return resNode;
	}
	//中序查找
	public HeroNode infixOrderSearch(int no){
	HeroNode resNode = null;
	if(this.left != null){
	resNode = this.left.infixOrderSearch(no);
	}
	if(resNode != null){
	return resNode;
	}
	if(this.no == no){
	return this;
	}
	if(this.right != null){
	resNode = this.right.infixOrderSearch(no);
	}
	return resNode;
	}
	//后序查找
	public HeroNode postOrderSearch(int no){
	HeroNode resNode = null;
	if(this.left != null){
	resNode = this.left.postOrderSearch(no);
	}
	if(resNode != null){
	return resNode;
	}
	if(this.right != null){
	resNode = this.right.postOrderSearch(no);
	}
	if(resNode != null){
	return resNode;
	}
	if(this.no == no){
	return this;
	}
	return null;
	}
	//在二叉树中增加查找方法
	//前序查找
	public HeroNode preOrderSearch(int no){
	HeroNode resNode = null;
	if(this.root != null){
	resNode = this.root.preOrderSearch(no);
	}else{
	System.out.println("当前二叉树为空");
	}
	return resNode;
	}
	//中序
	public HeroNode infixOrderSearch(int no){
	HeroNode resNode = null;
	if(this.root != null){
	resNode = this.root.infixOrderSearch(no);
	}else{
	System.out.println("当前二叉树为空");
	}
	return resNode;
	}
	//后序
	public HeroNode postOrderSearch(int no){
	HeroNode resNode = null;
	if(this.root != null){
	resNode = this.root.postOrderSearch(no);
	}else{
	System.out.println("当前二叉树为空");
	}
	return resNode;
	}

可以看出：

• 找到的次数和 查找的顺序 有关，而查找顺序就是哪一序有关
• 找不到的次数则是相当于都遍历完成，所以是相等的次数

二叉树删除

要求：

1. 如果删除的节点是 叶子节点，则删除该节点
2. 如果删除的节点是非叶子节点，则删除该子树

测试：删除 5 号叶子节点和 3 号子树。

说明：目前的二叉树不是规则的，如果不删除子树，则需要考虑哪一个节点会被上提作为父节点。这个后续讲解排序二叉树时再来实现。先实现简单的

思路分析：

• 由于我们的二叉树是单向的

• 所以我们判定一个节点是否可以删除，是判断它的 子节点，是否可删除，否则则没法回到父节点删除了，因为要判断被删除的节点满足前面的两点要求

  1. 当前节点的 左子节点 不为空，并且左子节点就是要删除的节点，则 left = null，并且返回（结束递归删除）
  2. 当前节点的 右子节点 不为空，并且右子节点就是要删除的节点，则 right = null，并且返回（结束递归删除）

  如果前面都没有删除，则继续递归删除。上面的要求是 2 点，实际上是，找到符合条件的节点则直接删除（因为不考虑是否有子树）

  如果树只有一个 root 节点，则将 root 节点置空

复制代码

	//节点中增加删除方法
	public void delete(int no){
	if(this.left != null){
	if(this.left.no == no){
	this.left = null;
	return;
	}
	}
	if(this.right != null){
	if(this.right.no == no){
	this.right = null;
	return;
	}
	}
	//向左递归
	if(this.left != null){
	this.left.delete(no);
	}
	//向右递归
	if(this.right != null){
	this.right.delete(no);
	}
	}
	//二叉树中增加删除方法
	public void delete(int no){
	if(this.root != null){
	if(this.root.getNo() == no){
	this.root = null;
	return;
	}else{
	this.root.delete(no);
	}
	}else{
	System.out.println("当前二叉树为空");
	}
	}

顺序存储二叉树

基本概念

从数据存储来看，数组存储 方式和 树 的存储方式可以 相互转换。即使数组可以转换成树，树也可以转换成数组。如下示意图

上图阅读说明：

• 圆圈顶部的数字对应了数组中的索引
• 圆圈内部的值对应的数数组元素的值

现在有两个要求：

1. 上图的二叉树的节点，要求以数组的方式来存储 arr=[1,2,3,4,5,6,7]
2. 要求在遍历数组 arr 时，仍然可以以 前序、中序、后序的方式遍历

特点

想要 实现上面的两个要求，需要知道顺序存储二叉树的特点：

1. 顺序二叉树 通常只考虑 完全二叉树
2. 第 n 个元素的 左子节点 为 2*n+1
3. 第 n 个元素的 右子节点 为 2*n+2
4. 第 n 个元素的 父节点 为 (n-1)/2

注：n 表示二叉树中的第几个元素（按 0 开始编号）

比如：

• 元素 2 的左子节点为：2 * 1 + 1 = 3，对比上图去查看，的确是 3
• 元素 2 的右子节点为：2 * 1 + 2 = 4，也 就是元素 5
• 元素 3 的左子节点为：2 * 2 + 1 = 5，也就是元素 6
• 元素 3 的父节点为: (2-1)/2= 1/2 = 0，也就是根节点 1

三种遍历方式

复制代码

	//顺序存储二叉树
	class ArrayBinaryTree{
	private int[] array;
	public ArrayBinaryTree(int[] array) {
	this.array = array;
	}
	//前序遍历输出顺序存储二叉树
	public void preOrder(int index){
	if(array == null || array.length == 0){
	System.out.println("数组为空，不能遍历完全二叉树");
	}
	//先输出当前元素
	System.out.println(array[index]);
	//再递归输出左子元素
	if((index*2+1) < array.length){
	preOrder((index*2 + 1));
	}
	//再递归输出右子元素
	if((index*2+2) < array.length){
	preOrder((index*2 +2));
	}
	}
	public void preOrder(){
	preOrder(0);
	}
	//中序遍历输出顺序存储二叉树
	public void infixOrder(int index){
	if(array == null || array.length == 0){
	System.out.println("数组为空，不能遍历完全二叉树");
	}
	if((index*2 +1) < array.length){
	infixOrder((index*2 + 1));
	}
	System.out.println(array[index]);
	if((index*2 + 2) < array.length){
	infixOrder((index*2+2));
	}
	}
	public void infixOrder(){
	infixOrder(0);
	}
	//后序遍历顺序存储二叉树
	public void postOrder(int index){
	if(array == null || array.length == 0){
	System.out.println("数组为空，不能遍历完全二叉树");
	}
	if((index*2 + 1) < array.length){
	postOrder((index*2+1));
	}
	if((index*2 + 2) < array.length){
	postOrder((index*2+2));
	}
	System.out.println(array[index]);
	}
	public void postOrder(){
	postOrder(0);
	}
	}

线索化二叉树

引出线索化二叉树

看如下问题：将数列 {1,3,6,8,10,14} 构成一颗二叉树

可以看到上图的二叉树为一颗 完全二叉树。对他进行分析，可以发现如下的一些问题：

1. 当对上面的二叉树进行中序遍历时，数列为 8,3,10,1,14,6
2. 但是 6,8,10,14 这几个节点的左右指针，并没有完全用上

如果希望充分利用各个节点的左右指针，让各个节点可以 指向自己的前后节点，这个时候就可以使用 线索化二叉树 了

介绍

n 个节点的二叉树链表中含有 n + 1 个空指针域，他的推导公式为 2n-(n-1) = n + 1。

利用二叉链表中的空指针域，存放指向该节点在 某种遍历次序 *下的 **前驱** 和 **后继** 节点的指针，这种附加的指针称为*「线索」

• 前驱：一个节点的前一个节点
• 后继：一个节点的后一个节点

如下图，在中序遍历中，下图的中序遍历为 8,3,10,1,14,6，那么 8 的后继节点就为 3，3 的后继节点是 10

这种加上了线索的二叉树链表称为 线索链表（节点存储了下一个节点，组成了链表，并且一般的二叉树本来就是用链表实现的），相应的二叉树称为 线索二叉树（Threaded BinaryTree）。根据线索性质的不同，线索二叉树可分为：前、中、后序线索二叉树。

思路分析

将上图的二叉树，进行 中序线索二叉树，中序遍历的数列为 8,3,10,1,14,6。

那么以上图为例，线索化二叉树后的样子如下图

• 的后继节点为 3
• 3 由于 左右节点都有元素，不能线索化
• 10 的前驱节点为 3，后继节点为 1
• 1 不能线索化
• 14 的前驱节点为 1，后继节点为 6
• 6 有左节点，不能线索化

注意：当线索化二叉树后，那么一个 Node 节点的 left 和 right 属性，就有如下情况：

1. left 指向的是 左子树，也可能是指向 前驱节点

   例如：节点 1 left 节点指向的是左子树，节点 10 的 left 指向的就是前驱节点

2. right 指向的是 右子树，也可能是指向 后继节点

   例如：节点 3 的 right 指向的是右子树，节点 10 的 right 指向的是后继节点

代码实现

复制代码

	//创建节点
	class HeroNode{
	private int no;
	private String name;
	private HeroNode left;
	private HeroNode right;
	//左右子树的类型，如果是左右子树就是0，如果是前驱或者后继节点就是1
	private int leftType;
	private int rightType;
	public HeroNode(int no, String name) {
	this.no = no;
	this.name = name;
	}
	public int getNo() {
	return no;
	}
	public void setNo(int no) {
	this.no = no;
	}
	public String getName() {
	return name;
	}
	public void setName(String name) {
	this.name = name;
	}
	public HeroNode getLeft() {
	return left;
	}
	public void setLeft(HeroNode left) {
	this.left = left;
	}
	public HeroNode getRight() {
	return right;
	}
	public void setRight(HeroNode right) {
	this.right = right;
	}
	public int getLeftType() {
	return leftType;
	}
	public void setLeftType(int leftType) {
	this.leftType = leftType;
	}
	public int getRightType() {
	return rightType;
	}
	public void setRightType(int rightType) {
	this.rightType = rightType;
	}
	@Override
	public String toString() {
	return "HeroNode{" +
	"no=" + no +
	", name='" + name + '\'' +
	'}';
	}
	}
	//创建线索化二叉树
	class ThreadBinaryTree{
	private HeroNode root;//表示跟节点
	private HeroNode pre;//表示前驱节点
	public void setRoot(HeroNode root) {
	this.root = root;
	}
	public void threadedNodes(){
	threadedNodes(root);
	}
	//中序线索化遍历
	public void threadedList(){
	if(root == null){
	System.out.println("线索化二叉树为空");
	return;
	}
	HeroNode node = root;
	while(node != null){
	//找到第一个有前驱节点的元素
	while(node.getLeftType() != 1){
	node = node.getLeft();
	}
	//输出第一个元素
	System.out.println(node);
	//当有后继节点的情况会进入
	while(node.getRightType() == 1){
	node = node.getRight();
	System.out.println(node);
	}
	//当一个节点没有后继节点的时候直接获取右子树
	node = node.getRight();
	}
	}
	//中序线索化
	public void threadedNodes(HeroNode node){
	if(node == null){
	return;
	}
	//先线索化左子树
	threadedNodes(node.getLeft());
	//再线索化当前节点
	/*
	* 1.设置前驱节点，
	* 2.设置后继节点
	* */
	if(node.getLeft() == null){
	node.setLeft(pre);
	node.setLeftType(1);
	}
	//线索化后继节点，需要遍历到下一个节点的时候，通过下一个节点设置
	if(pre != null && pre.getRight() == null){
	pre.setRight(node);
	pre.setRightType(1);
	}
	//将前驱节点后移
	pre = node;
	//线索化右子树
	threadedNodes(node.getRight());
	}
	}

前序线索化和遍历

复制代码

	//前序线索化
	public void preThreadedNodes(HeroNode node){
	if(node == null){
	return;
	}
	//先序列化自己
	if(pre != null && node.getLeft() == null){
	node.setLeft(pre);
	node.setLeftType(1);
	}
	if(pre != null && pre.getRight() == null){
	pre.setRight(node);
	pre.setRightType(1);
	}
	pre = node;
	//再序列化递归左子树
	if(node.getLeftType() == 0){
	preThreadedNodes(node.getLeft());
	}
	//再递归序列化右子树
	if(node.getRightType() == 0){
	preThreadedNodes(node.getRight());
	}
	}
	//前序序列化遍历
	public void preThreadedList(){
	if(root == null){
	System.out.println("线索化二叉树为空");
	return;
	}
	HeroNode node = root;
	while(node != null){
	System.out.println(node);
	while(node.getLeftType() == 0){
	node = node.getLeft();
	System.out.println(node);
	}
	while (node.getRightType() == 1) {
	node = node.getRight();
	System.out.println(node);
	}
	node = node.getRight();
	}
	}