第 10 章树结构的基础部分

喜欢ヅ旅行 2022-11-27 00:55 124阅读 0赞

# 第 10 章 树结构的基础部分 #

## 1、二叉树 ##

### 1.1、为什么需要二叉树 ###

#### 1.1.1、数组存储方式的分析 ####

*  优点： 通过下标方式访问元素， 速度快。 对于有序数组， 还可使用二分查找提高检索速度
 *  缺点： 如果要检索具体某个值， 或者插入值(按一定顺序)会整体移动，效率较低

![image-20200717114055463][]

#### 1.1.2、链式存储方式的分析 ####

*  优点： 在一定程度上对数组存储方式有优化(比如： 插入一个数值节点， 只需要将插入节点， 链接到链表中即可，删除效率也很好)。
 *  缺点： 在进行检索时， 效率仍然较低， 比如(检索某个值， 需要从头节点开始遍历)

![image-20200717114117712][]

#### 1.1.3、树存储方式的分析 ####

*  能提高数据存储， 读取的效率, 比如利用 二叉排序树(Binary Sort Tree)， 既可以保证数据的检索速度， 同时也可以保证数据的插入， 删除， 修改的速度。 【示意图，后面详讲】

![image-20200717114133584][]

### 1.2、树的常用术语 ###

*  节点
 *  根节点
 *  父节点
 *  子节点
 *  叶子节点 (没有子节点的节点)
 *  节点的权(节点值)
 *  路径(从 root 节点找到该节点的路线)
 *  层
 *  子树
 *  树的高度(最大层数)
 *  森林 :多颗子树构成森林

![image-20200717114228647][]

### 1.3、二叉树的概念 ###

*  树有很多种， 每个节点最多只能有两个子节点的一种形式称为二叉树，二叉树的子节点分为左节点和右节点

![image-20200812215137568][]

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

![image-20200812215146251][]

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

![image-20200812215156517][]

### 1.4、二叉树的遍历 ###

#### 1.4.1、代码思路 ####

*  前序遍历: **先输出父节点**， 再遍历左子树和右子树
 *  中序遍历: 先遍历左子树， **再输出父节点**， 再遍历右子树
 *  后序遍历: 先遍历左子树， 再遍历右子树， **最后输出父节点**

![image-20200717131131963][]

#### 1.4.2、前 中 后序遍历 ####

*  定义二叉树节点

*  定义二叉树：二叉树需要一个根节点 root 作为整个树的入口

#### 1.4.3、代码测试 ####

*  测试代码

*  程序运行结果

![image-20200812215649619][]

前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=5, name=关胜]
    HeroNode [no=4, name=林冲]
    中序遍历
    HeroNode [no=2, name=吴用]
    HeroNode [no=1, name=宋江]
    HeroNode [no=5, name=关胜]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=4, name=林冲]
    后序遍历
    HeroNode [no=2, name=吴用]
    HeroNode [no=5, name=关胜]
    HeroNode [no=4, name=林冲]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=1, name=宋江]

#### 1.4.4、总结 ####

*  看**输出父节点的顺序**， 就确定是前序， 中序还是后序
 *  前序遍历递归图解

![image-20200717132031221][]

*  中序遍历递归图解

![image-20200717132518380][]

*  后序遍历递归图解

![image-20200717133003958][]

### 1.5、二叉树的查找 ###

#### 1.5.1、代码思路 ####

*  将二叉树的前、中、后序遍历改为查找即可
 *  编码思路：
    
     *  如果查找到目标节点，直接返回，结束递归
     *  如果找不到，继续递归执行前（中、后）序查找

![image-20200717134543329][]

#### 1.5.2、前 中 后序查找 ####

*  定义二叉树节点

*  定义二叉树：二叉树需要一个根节点 root 作为整个树的入口

//定义 BinaryTree 二叉树
    class BinaryTree {
        
    	private HeroNode root;
    
    	public void setRoot(HeroNode root) {
        
    		this.root = root;
    	}
    
    	// 删除结点
    	public void delNode(int no) {
        
    		if (root != null) {
        
    			// 如果只有一个root结点, 这里立即判断root是不是就是要删除结点
    			if (root.getNo() == no) {
        
    				root = null;
    			} else {
        
    				// 递归删除
    				root.delNode(no);
    			}
    		} else {
        
    			System.out.println("空树，不能删除~");
    		}
    	}
    
    	// 前序遍历查找
    	public HeroNode preOrderSearch(int no) {
        
    		if (root != null) {
        
    			return root.preOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    
    	// 中序遍历查找
    	public HeroNode infixOrderSearch(int no) {
        
    		if (root != null) {
        
    			return root.infixOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    
    	// 后序遍历查找
    	public HeroNode postOrderSearch(int no) {
        
    		if (root != null) {
        
    			return this.root.postOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    }

#### 1.5.3、测试代码 ####

*  测试代码：测试前序、中序、后序查找

public static void main(String[] args) {
        
    		// 先需要创建一颗二叉树
    		BinaryTree binaryTree = new BinaryTree();
    		// 创建需要的结点
    		HeroNode root = new HeroNode(1, "宋江");
    		HeroNode node2 = new HeroNode(2, "吴用");
    		HeroNode node3 = new HeroNode(3, "卢俊义");
    		HeroNode node4 = new HeroNode(4, "林冲");
    		HeroNode node5 = new HeroNode(5, "关胜");
    
    		// 说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setRight(node4);
    		node3.setLeft(node5);
    		binaryTree.setRoot(root);
    
    		// 前序遍历
    		System.out.println("前序遍历方式~~~");
    		HeroNode resNode = binaryTree.preOrderSearch(4);
    		if (resNode != null) {
        
    			System.out.printf("找到了，信息为 no=%d name=%s\n", resNode.getNo(), resNode.getName());
    		} else {
        
    			System.out.printf("没有找到 no = %d 的英雄\n", 4);
    		}
    		System.out.println();
    		
    		// 中序遍历查找
    		System.out.println("中序遍历方式~~~");
    		resNode = binaryTree.infixOrderSearch(5);
    		if (resNode != null) {
        
    			System.out.printf("找到了，信息为 no=%d name=%s\n", resNode.getNo(), resNode.getName());
    		} else {
        
    			System.out.printf("没有找到 no = %d 的英雄\n", 5);
    		}
    		System.out.println();
    		
    		// 后序遍历查找
    		System.out.println("后序遍历方式~~~");
    		resNode = binaryTree.postOrderSearch(6);
    		if (resNode != null) {
        
    			System.out.printf("找到了，信息为 no=%d name=%s\n", resNode.getNo(), resNode.getName());
    		} else {
        
    			System.out.printf("没有找到 no = %d 的英雄\n", 6);
    		}
    		System.out.println();
    
    	}

*  程序运行结果

前序遍历方式~~~
    找到了，信息为 no=4 name=林冲
    
    中序遍历方式~~~
    找到了，信息为 no=5 name=关胜
    
    后序遍历方式~~~
    没有找到 no = 6 的英雄

### 1.6、二叉树的删除 ###

#### 1.6.1、二叉树删除的要求 ####

*  如果删除的节点是叶子节点， 则删除该节点
 *  如果删除的节点是非叶子节点， 则删除该子树

#### 1.6.2、代码思路 ####

*  由于树的本质还是单向链表：
    
     *  单向链表无法实现自删除，我们需要定位至待删除节点的前一个节点，才能执行删除
     *  同样，如果我们直接定位至二叉树中待删除的节点，那么其父节点信息便会丢失，所以我们一定要定位至待删除节点的父节点
 *  编码思路：
    
     *  先判断根节点 root 是不是待删除的节点，如果是，则删除根节点，否则开始执行递归
     *  判断当前节点（this）的左节点是否为待删除的节点，如果是，删除 this.left ，然后返回，结束递归
     *  判断当前节点（this）的左节点是否为待删除的节点，如果是，删除 this.right，然后返回，结束递归
     *  否则继续执行左递归，左递归执行完后，执行右递归

![image-20200717163631462][]

#### 1.6.3、二叉树的递归删除 ####

*  定义二叉树节点

*  定义二叉树：二叉树需要一个根节点 root 作为整个树的入口

#### 1.6.4、测试代码 ####

*  代码

*  程序运行结果

删除前,前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=5, name=关胜]
    HeroNode [no=4, name=林冲]
    
    删除节点 5 后，前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=4, name=林冲]
    
    删除子树 3  后，前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]

### 1.7、二叉树的全部代码 ###

*  叶子节点的定义

//先创建 HeroNode 结点
    class HeroNode {
        
    	private int no;
    	private String name;
    	private HeroNode left; // 默认null
    	private HeroNode right; // 默认null
    
    	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);
    	}
    
    	// 前序遍历查找
    	public HeroNode preOrderSearch(int no) {
        
    		// 比较当前结点是不是
    		if (this.no == no) {
        
    			return this;
    		}
    		// 1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
    		// 2.如果左递归前序查找，找到结点，则返回
    		HeroNode resNode = null;
    		if (this.left != null) {
        
    			resNode = this.left.preOrderSearch(no);
    		}
    		if (resNode != null) {
        // 说明我们左子树找到
    			return resNode;
    		}
    		// 1.左递归前序查找，找到结点，则返回，否继续判断，
    		// 2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
    		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 resNode;
    	}
    
    	// 递归删除结点
    	// 1.如果删除的节点是叶子节点，则删除该节点
    	// 2.如果删除的节点是非叶子节点，则删除该子树
    	public void delNode(int no) {
        
    
    		// 思路
    		/*
    		 * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点. 2.
    		 * 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) 3.
    		 * 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) 4.
    		 * 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除.
    		 * 
    		 */
    		// 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
    		if (this.left != null && this.left.no == no) {
        
    			this.left = null;
    			return;
    		}
    		// 3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
    		if (this.right != null && this.right.no == no) {
        
    			this.right = null;
    			return;
    		}
    		// 4.我们就需要向左子树进行递归删除
    		if (this.left != null) {
        
    			this.left.delNode(no);
    		}
    		// 5.则应当向右子树进行递归删除
    		if (this.right != null) {
        
    			this.right.delNode(no);
    		}
    	}
    
    }

*  二叉树的定义

//定义 BinaryTree 二叉树
    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("二叉树为空，无法遍历");
    		}
    	}
    
    	// 前序遍历查找
    	public HeroNode preOrderSearch(int no) {
        
    		if (root != null) {
        
    			return root.preOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    
    	// 中序遍历查找
    	public HeroNode infixOrderSearch(int no) {
        
    		if (root != null) {
        
    			return root.infixOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    
    	// 后序遍历查找
    	public HeroNode postOrderSearch(int no) {
        
    		if (root != null) {
        
    			return this.root.postOrderSearch(no);
    		} else {
        
    			return null;
    		}
    	}
    
    	// 删除结点
    	public void delNode(int no) {
        
    		if (root != null) {
        
    			// 如果只有一个root结点, 这里立即判断root是不是就是要删除结点
    			if (root.getNo() == no) {
        
    				root = null;
    			} else {
        
    				// 递归删除
    				root.delNode(no);
    			}
    		} else {
        
    			System.out.println("空树，不能删除~");
    		}
    	}
    }

### 1.8、课后练习 ###

*  如果要删除的节点是非叶子节点， 现在我们不希望将该非叶子节点为根节点的子树删除， 需要指定规则, 假如规定如下:
 *  如果该非叶子节点 A 只有一个子节点 B， 则子节点 B 替代节点 A
 *  如果该非叶子节点 A 有左子节点 B 和右子节点 C， 则让左子节点 B 替代节点 A。
 *  请大家思考， 如何完成该删除功能，后面在讲解二叉排序树时， 在给大家讲解具体的删除方法

![image-20200812220551450][]

## 2、顺序存储二叉树 ##

### 2.1、顺序存储二叉树的概念 ###

#### 2.1.1、顺序存储二叉树与数组的转换 ####

*  基本说明：从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可
    
    以转换成树，树也可以转换成数组。
 *  要求：
    
     *  右图的二叉树的结点，要求以数组的方式来存放 arr : \[1, 2, 3, 4, 5, 6, 6\]
     *  要求在遍历数组 arr时，仍然可以用前序遍历，中序遍历和后序遍历的方式完成结点的遍历

![image-20200717172241857][]

#### 2.1.2、顺序存储二叉树的特点 ####

*  顺序存储二叉树特点
    
     *  顺序二叉树通常只考虑完全二叉树
     *  **顺序存储二叉树中第 n 个元素的左子节点对应的数组下标为 2 \* n + 1**
     *  **顺序存储二叉树中第 n 个元素的右子节点对应的数组下标为 2 \* n + 2**
     *  **顺序存储二叉树中第 n 个元素的父节点对应的数组下标为 (n-1) / 2**
     *  n 的含义： 表示二叉树中的第几个元素（按0开始编号，如图所示）
 *  下标怎么来的？
    
     *  顺序存储二叉树通常只考虑完全二叉树，完全二叉树的节点个数规律为：1, 2, 4, 8, 12 , … 即 2 的 n 次方
     *  每个父节点都会延伸出两个子节点，假设当前节点编号为 n （索引从 0 开始），设当前节点在第 x 层（索引从 1 开始），可得如下数据：
        
         *  1~(x-1) 层所拥有的的节点个数：2n-1 \-1
         *  1~x 层所拥有的节点个数：2n \- 1
         *  在第 x 层，节点 n 后面有多少个节点：
            
            back = 2n \- 1 - n - 1 = 2n \-n - 2
         *  在第 x 层，节点 n 前面有多少个节点：
            
            front = n - (2n-1 \-1) = n - 2n-1 \+ 1
         *  在第 x+1 层，节点 n 左节点前面有多少个节点：
            
            frontDouble = 2 \* (n - 2n-1 \+ 1) = 2n - 2n \+ 2
         *  所以节点 n 左节点的索引为：
            
            index = n + back + frontDouble + 1 = n + (2n \-n - 2) + (2n - 2n \+ 2) + 1 = 2\*n + 1

![image-20200717183117711][]

### 2.2、顺序存储二叉树的遍历 ###

#### 2.2.1、代码思路 ####

*  和之前链表二叉树一样，之前用 left 指针和 right 指针寻找左右子节点，实现递归，只不过顺序存储二叉树使用数组下标寻找左右子节点
 *  何时结束递归？**当数组下标越界时，说明当前节点已经没有左节点或右节点，已经递归至最深处**，此时就应该停止递归，开始回溯

#### 2.2.2、前 中 后序遍历 ####

*  编写顺序存储二叉树的前序、中序、后序遍历

//编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
    class ArrBinaryTree {
        
    	private int[] arr;// 存储数据结点的数组
    
    	public ArrBinaryTree(int[] arr) {
        
    		this.arr = arr;
    	}
    
    	// 重载preOrder
    	public void preOrder() {
        
    		this.preOrder(0);
    	}
    
    	// 顺序存储二叉树的前序遍历
    	// index ：数组下标
    	public void preOrder(int index) {
        
    		// 如果数组为空，或者 arr.length = 0
    		if (arr == null || arr.length == 0) {
        
    			System.out.println("数组为空，不能执行二叉树的前序遍历");
    		}
    		// 输出当前这个元素
    		System.out.println(arr[index]);
    		// 向左递归遍历
    		if ((index * 2 + 1) < arr.length) {
        
    			preOrder(2 * index + 1);
    		}
    		// 向右递归遍历
    		if ((index * 2 + 2) < arr.length) {
        
    			preOrder(2 * index + 2);
    		}
    	}
    
    	public void infixOrder() {
        
    		this.infixOrder(0);
    	}
    
    	// 顺序存储二叉树的中序遍历
    	public void infixOrder(int index) {
        
    		// 如果数组为空，或者 arr.length = 0
    		if (arr == null || arr.length == 0) {
        
    			System.out.println("数组为空，不能执行二叉树的前序遍历");
    		}
    		// 向左递归遍历
    		if ((index * 2 + 1) < arr.length) {
        
    			infixOrder(2 * index + 1);
    		}
    		// 输出当前这个元素
    		System.out.println(arr[index]);
    		// 向右递归遍历
    		if ((index * 2 + 2) < arr.length) {
        
    			infixOrder(2 * index + 2);
    		}
    	}
    	
    	public void postOrder() {
        
    		this.postOrder(0);
    	}
    
    	// 顺序存储二叉树的中序遍历
    	public void postOrder(int index) {
        
    		// 如果数组为空，或者 arr.length = 0
    		if (arr == null || arr.length == 0) {
        
    			System.out.println("数组为空，不能执行二叉树的前序遍历");
    		}
    		// 向左递归遍历
    		if ((index * 2 + 1) < arr.length) {
        
    			postOrder(2 * index + 1);
    		}
    		// 向右递归遍历
    		if ((index * 2 + 2) < arr.length) {
        
    			postOrder(2 * index + 2);
    		}
    		// 输出当前这个元素
    		System.out.println(arr[index]);
    	}
    
    }

#### 2.2.3、测试代码 ####

*  代码

public static void main(String[] args) {
        
        int[] arr = {
         1, 2, 3, 4, 5, 6, 7 };
        // 创建一个 ArrBinaryTree
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
        System.out.println();
    
        arrBinaryTree.infixOrder(); // 4,2,5,1,6,3,7
        System.out.println();
    
        arrBinaryTree.postOrder(); // 4,5,2,6,7,3,1
    }

*  程序运行结果

1
    2
    4
    5
    3
    6
    7
    
    4
    2
    5
    1
    6
    3
    7
    
    4
    5
    2
    6
    7
    3
    1

### 2.3、顺序存储二叉树应用实例 ###

*  八大排序算法中的**堆排序**，就会使用到顺序存储二叉树， 关于堆排序，我们放在【树结构实际应用】章节讲解。

## 3、线索化二叉树 ##

### 3.1、引出问题 ###

*  将数列 \{1, 3, 6, 8, 10, 14 \} 构建成一颗二叉树，当我们对这颗二叉树进行中序遍历时， 输出数列为 \{8, 3, 10, 1, 6, 14 \}
 *  但是 6, 8, 10, 14 这几个节点的左右指针，并没有完全的利用上，如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点，怎么办?
 *  解决方案：线索二叉树

![image-20200812221045230][]

### 3.2、线索二叉树基本介绍 ###

*  n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。 利用二叉链表中的空指针域， 存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
 *  这种加上了线索的二叉链表称为线索链表， 相应的二叉树称为线索二叉树(Threaded BinaryTree)。
 *  根据线索性质的不同， 线索二叉树可分为前序线索二叉树、 中序线索二叉树和后序线索二叉树三种
 *  前驱结点和后继节点：
    
     *  一个结点的前一个结点， 称为前驱结点
     *  一个结点的后一个结点， 称为后继结点
 *  当我们对二叉树进行中序遍历时， 得到的数列为 \{8, 3, 10, 1, 6, 14 \}
    
     *  那么 8 节点的前驱结点为 null ，8 和后驱节点为 3
     *  那么 3 节点的前驱结点为 8 ，3 和后驱节点为 10
     *  以此类推…

![image-20200717202649306][]

### 3.3、线索二叉树的生成 ###

#### 3.3.1、代码思路 ####

*  如何实现线索二叉树？以中序线索化为例，按照上面的步骤操作即可
 *  怎么知道当前节点的前驱结点和后继节点？
    
     *  想想单链表的删除是怎么做的？我们记录当前节点的前一个节点，在程序中使用 pre 指针记录当前正在遍历的节点 curNode ，以及其前驱结点 preNode
     *  如果条件满足，preNode 就是 curNode 的前驱结点：`curNode.left = pre;`
     *  如果条件满足，curNode 节点就是 preNode 的后继节点：`pre.right = curNode;`
 *  何时递归完毕？当前递归至最深层，curNode 为空时开始回溯：`curNode == null`
 *  举例说明：
    
     *  我们进行中序遍历时，先执行左递归至最深层
     *  对于图例来说，就是递归到节点 8 左节点，满足 `node.left == null` ，开始执行回溯
     *  于是我们回到节点8 ，该节点并没有前驱结点，即前驱结点为 null ，恰好此时 pre 也为 null
     *  设置节点 8 的前驱结点：`node.left = pre;`
     *  操作完成后，pre 和 node 指针向后移动一步
    
    ![image-20200717204350682][]
    
     *  回溯到节点 3 ，节点 3 的 pre 节点是节点 8
     *  设置节点 8 的后继节点：`pre.right = node;`
     *  操作完成后，pre 和 node 指针向后移动一步
    
    ![image-20200717204434593][]
    
     *  继续执行右递归，节点 10 的前驱结点为 3
     *  设置节点 10 的前驱结点：`node.left = pre;`
     *  操作完成后，pre 和 node 指针向后移动一步
    
    ![image-20200717205442088][]
    
     *  以此类推，递归至最后，所有线索都已设置完毕
     *  操作完成后，pre 和 node 指针向后移动一步，此时 `node == null` ，递归完毕，节点 6 的 right 指针的类型为真正的子节点，并非
    
    ![image-20200717210501640][]
 *  大致流程：
    
     *  递归结束条件：`node == null`
     *  执行左递归
     *  设置前驱结点、后继节点，并后移 pre 和 node 指针（pre 指针需手动移动，node 指针其实是通过递归来移动的）
     *  执行右递归

![image-20200717211619274][]

*  关于线索化之后的二叉树：只有一个右节点的 right 域为 null ，这个右节点是整棵树最深层的右节点，遍历到该右节点时，表示整棵树遍历完成

#### 3.3.2、代码实现 ####

*  由于将原有的指针域（left 和 right 指针）指向了前驱节点和后继节点，所以代码里面需要表示当前指针到底是指向了真正的子节点还是前驱节点或后继节点
 *  leftType 、rightType：0 表示指向真正的子节点，1 表示指向前驱节点或后继节点

//先创建HeroNode 结点
    class HeroNode {
        
    	private int no;
    	private String name;
    	private HeroNode left; // 默认null
    	private HeroNode right; // 默认null
    	// 说明
    	// 1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    	// 2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
    	private int leftType;
    	private int rightType;
    
    	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;
    	}
    
    	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 + "]";
    	}
    
    }

*  线索二叉树的定义：

#### 3.3.3、测试代码 ####

*  代码

public static void main(String[] args) {
        
    
        // 测试一把中序线索二叉树的功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");
    
        // 二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
    
        // 测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();
    
        // 测试: 以10号节点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
        System.out.println("10号结点的后继结点是=" + rightNode); // 1
    
    }

*  程序运行结果

10号结点的前驱结点是 =HeroNode [no=3, name=jack]
    10号结点的后继结点是=HeroNode [no=1, name=tom]

### 3.4、线索二叉树的遍历 ###

#### 3.4.1、代码思路 ####

*  为什么我们要做线索化？
    
     *  因为线索化后， 各个结点指向有变化， 因此原来的遍历方式不能使用， 这时需要使用新的方式遍历线索化二叉树， 各个节点可以通过线性方式遍历， 因此无需使用递归方式， 这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
     *  以中序遍历为例，线索化可以让每个**具有前驱结点的左节点**的 **right 指针**都能指向其下一个要遍历的节点（后继节点）
     *  我们先找到第一个具有前驱结点的左节点（整棵树最深层的左叶子节点），我们沿着该左叶子节点的后继节点遍历，可以中序遍历的结果
     *  如果遍历到的节点没有后继节点，那么说明该节点 left 和 right 都有节点，直接输出其右节点，并以该右节点根节点，继续执行上一步操作，往最深处寻找第一个具有前驱结点的左节点（当前步骤最深层的左叶子节点），我们继续沿着左叶子节点的后继节点遍历
     *  如此往复，直到最后得到的右节点为 null，上面有讲过，线索二叉树有且只有一个为 null 的 right 指针，该值为 null 时代表整棵树的结束
 *  举例说明：
    
     *  因为执行的中序遍历：左 --> 中 --> 后，先执行深度搜索，找到第一个有前驱结点的节点，第一次搜索找到节点 8 ，其前驱结点为 null ，从节点 8 的后继节点为节点 3
    
    ![image-20200717215619784][]
    
     *  节点 3 并没有后继节点，只有右节点 10 ，我们拿到节点 10
    
    ![image-20200717215712109][]
    
     *  寻找节点 10 下第一个具有前驱结点的节点，恰好就是它本身，然后寻找其后继节点
    
    ![image-20200717220255940][]
    
     *  以此类推…
 *  大致思路：
    
     *  寻找最深层的具有前驱结点的左节点
     *  沿着左节点遍历其后继节点
     *  如果没有后继节点，则直接输出其右节点，并以该右节点根节点，继续寻找最深层的具有前驱结点的左节点
     *  如此往复，直到最后得到的右节点值为 null

![image-20200717223526050][]

#### 3.4.2、代码实现 ####

*  HeroNode 节点的定义与之前一样

*  在 ThreadedBinaryTree 类中添加遍历方法

//定义ThreadedBinaryTree 实现了线索化功能的二叉树
    class ThreadedBinaryTree {
        
    	private HeroNode root;
    
    	// 为了实现线索化，需要创建一个指向当前结点的前驱结点的指针
    	// 在递归进行线索化时，pre 总是保留前一个结点
    	private HeroNode pre = null;
    
    	public void setRoot(HeroNode root) {
        
    		this.root = root;
    	}
    
    	// 重载一把threadedNodes方法
    	public void threadedNodes() {
        
    		this.threadedNodes(root);
    	}
    
    	// 编写对二叉树进行中序线索化的方法
    	// node 就是当前需要线索化的结点
    	public void threadedNodes(HeroNode node) {
        
    
    		// 如果node==null, 不能线索化
    		if (node == null) {
        
    			return;
    		}
    
    		// (一)先线索化左子树
    		threadedNodes(node.getLeft());
    		
    		// (二)线索化当前结点[有难度]
    		// 处理当前结点的前驱结点
    		// 以8结点来理解
    		// 8结点的.left = null , 8结点的.leftType = 1
    		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 threadedList() {
        
    		// 定义一个变量，存储当前遍历的结点，从root开始
    		HeroNode node = root;
    		while (node != null) {
        
    			// 循环的找到leftType == 1的结点，第一个找到就是8结点
    			// 后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化处理后的有效结点
    			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();
    
    		}
    	}
    }

#### 3.4.3、测试代码 ####

*  代码

*  程序运行结果

使用线索化的方式遍历 线索化二叉树
    HeroNode [no=8, name=mary]
    HeroNode [no=3, name=jack]
    HeroNode [no=10, name=king]
    HeroNode [no=1, name=tom]
    HeroNode [no=14, name=dim]
    HeroNode [no=6, name=smith]

#### 3.4.4、课后作业 ####

*  这里讲解了中序线索化二叉树，前序线索化二叉树和后序线索化二叉树的分析思路类似， 同学们作为课后作业完成

### 3.5、线索二叉树全部代码 ###

public class ThreadedBinaryTreeDemo {
        
    
    	public static void main(String[] args) {
        
    		
    		// 测试一把中序线索二叉树的功能
    		HeroNode root = new HeroNode(1, "tom");
    		HeroNode node2 = new HeroNode(3, "jack");
    		HeroNode node3 = new HeroNode(6, "smith");
    		HeroNode node4 = new HeroNode(8, "mary");
    		HeroNode node5 = new HeroNode(10, "king");
    		HeroNode node6 = new HeroNode(14, "dim");
    
    		// 二叉树，后面我们要递归创建, 现在简单处理使用手动创建
    		root.setLeft(node2);
    		root.setRight(node3);
    		node2.setLeft(node4);
    		node2.setRight(node5);
    		node3.setLeft(node6);
    
    		// 测试中序线索化
    		ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
    		threadedBinaryTree.setRoot(root);
    		threadedBinaryTree.threadedNodes();
    
    		// 测试: 以10号节点测试
    		HeroNode leftNode = node5.getLeft();
    		HeroNode rightNode = node5.getRight();
    		System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
    		System.out.println("10号结点的后继结点是=" + rightNode); // 1
    
    		// 当线索化二叉树后，不能再使用原来的遍历方法
    		System.out.println("使用线索化的方式遍历 线索化二叉树");
    		threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
    
    	}
    
    }
    
    //定义ThreadedBinaryTree 实现了线索化功能的二叉树
    class ThreadedBinaryTree {
        
    	private HeroNode root;
    
    	// 为了实现线索化，需要创建一个指向当前结点的前驱结点的指针
    	// 在递归进行线索化时，pre 总是保留前一个结点
    	private HeroNode pre = null;
    
    	public void setRoot(HeroNode root) {
        
    		this.root = root;
    	}
    
    	// 重载一把threadedNodes方法
    	public void threadedNodes() {
        
    		this.threadedNodes(root);
    	}
    
    	// 编写对二叉树进行中序线索化的方法
    	// node 就是当前需要线索化的结点
    	public void threadedNodes(HeroNode node) {
        
    
    		// 如果node==null, 不能线索化
    		if (node == null) {
        
    			return;
    		}
    
    		// (一)先线索化左子树
    		threadedNodes(node.getLeft());
    		
    		// (二)线索化当前结点[有难度]
    		// 处理当前结点的前驱结点
    		// 以8结点来理解
    		// 8结点的.left = null , 8结点的.leftType = 1
    		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 threadedList() {
        
    		// 定义一个变量，存储当前遍历的结点，从root开始
    		HeroNode node = root;
    		while (node != null) {
        
    			// 循环的找到leftType == 1的结点，第一个找到就是8结点
    			// 后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化处理后的有效结点
    			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();
    
    		}
    	}
    }
    
    //先创建HeroNode 结点
    class HeroNode {
        
    	private int no;
    	private String name;
    	private HeroNode left; // 默认null
    	private HeroNode right; // 默认null
    	// 说明
    	// 1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    	// 2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
    	private int leftType;
    	private int rightType;
    
    	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;
    	}
    
    	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 + "]";
    	}
    
    }

[image-20200717114055463]: /images/20221124/8dbcb18d7b74461cba6a286191a81a93.png
[image-20200717114117712]: /images/20221124/3bad3a7b4dc244599e1b4aa8dda41913.png
[image-20200717114133584]: /images/20221124/7a41d5bac1ad4092a1dce9ec8bc57b03.png
[image-20200717114228647]: /images/20221124/a8929057d80f4a1b9ece63bb772ba882.png
[image-20200812215137568]: /images/20221124/a7f20962b55d4c97a64e7dd28fdcf4b2.png
[image-20200812215146251]: /images/20221124/35f944e6a77840c29b066a5310bdfb68.png
[image-20200812215156517]: /images/20221124/b516cb7c2e8d4fb69981d8d3c0231fab.png
[image-20200717131131963]: /images/20221124/29a739e96254468bb8ee79c29ebed829.png
[image-20200812215649619]: /images/20221124/4404f018474b45c08ac960421cf2b502.png
[image-20200717132031221]: /images/20221124/98b758e9877a4cc4be92fb7a759e208d.png
[image-20200717132518380]: /images/20221124/0e2f70ffaf774d3b83106fd06b00d20e.png
[image-20200717133003958]: /images/20221124/cf1f003861a64fe8b86c45fddce06d7e.png
[image-20200717134543329]: /images/20221124/e033a3b10c464ad49f9636db5c0845bf.png
[image-20200717163631462]: /images/20221124/c9f5af0b6b7d457198d5224b082cd009.png
[image-20200812220551450]: /images/20221124/ea7a174ff4a84544b7fcfb61028f9f4e.png
[image-20200717172241857]: /images/20221124/2f7370667e194740865f85faded1e537.png
[image-20200717183117711]: /images/20221124/ef4ed8cf8f1b4acc8f7fe0f3c69f3fea.png
[image-20200812221045230]: /images/20221124/80f78d2c125c4006a029d0e1e1365ca7.png
[image-20200717202649306]: /images/20221124/2fd304612ea8466b8c7955c57d6d3033.png
[image-20200717204350682]: /images/20221124/facff94fa9af4551ada85ba913e0fd11.png
[image-20200717204434593]: /images/20221124/308a1ffcf9554f39833fe025cd9b8b5c.png
[image-20200717205442088]: /images/20221124/b5ce46cfdcf0489ba754908d8d9dc0fb.png
[image-20200717210501640]: /images/20221124/63eadd59beab4bbba669d15684477249.png
[image-20200717211619274]: /images/20221124/01061e349fea4da9bcd6854cd21fef33.png
[image-20200717215619784]: /images/20221124/4a5ca4ee666449a5852d6ea11a3d8294.png
[image-20200717215712109]: /images/20221124/4ceddaad66ac489e9f8f774eb9644029.png
[image-20200717220255940]: /images/20221124/99c1b295a54b437891355a98ad2c76c8.png
[image-20200717223526050]: /images/20221124/d96063c7bfb94b96a9969e8bbfc4d277.png