线索化二叉树
通过一个问题来引入线索化二叉树
将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7
问题分析:
当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.
如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?
解决方案-线索二叉树
线索二叉树基本介绍
n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向 该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质 的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
一个结点的前一个结点，称为前驱结点
一个结点的后一个结点，称为后继结点
线索二叉树应用案例
将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
说明: 当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:
left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的
就是前驱节点.
right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩ 节点的 right 指向 的是后继节点.
代码实现
package com.hyc.DataStructure.tree.ThreadedBinaryTree; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.tree.ThreadedBinaryTree * @className: ThreadedBinaryTreeDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2022/2/5 16:38 * @version: 1.0 */ 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.setLeftNode(node2); root.setRightNode(node3); node2.setLeftNode(node4); node2.setRightNode(node5); node3.setLeftNode(node6); //测试中序线索化 ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setHead(root); threadedBinaryTree.postThreadedNodes(root); //测试: 以10号节点测试 heroNode leftNode = node5.getLeftNode(); heroNode rightNode = node5.getRightNode(); System.out.println("10号结点的前驱结点是 =" + leftNode); //3 System.out.println("10号结点的后继结点是=" + rightNode); //1 //当线索化二叉树后，能在使用原来的遍历方法 //threadedBinaryTree.infixOrder(); System.out.println("使用线索化的方式遍历 线索化二叉树"); threadedBinaryTree.preThreaddeList(); // 8, 3, 10, 1, 14, 6 } } class ThreadedBinaryTree { //确定根节点 private heroNode head; //递归的时候用来存放上一个节点的变量用于线索化树的遍历和线索化节点 private heroNode pre; public void setHead(heroNode head) { this.head = head; } //线索化遍历 public void ThreaddeList() { // 这里我们需要一个变量，存储当前的节点 heroNode tempNode = head; while (tempNode != null) { /* 开始循环遍历 * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点 * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了 * 之后只需要处理线索化之后的有效节点即可 * */ while (tempNode.getLefttype() == 0) { tempNode = tempNode.getLeftNode(); } // 因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了 System.out.println(tempNode); /* 如果当前节点的右指针指向的是后继节点那么就一直输出 * */ while (tempNode.getRighttype() == 1) { tempNode = tempNode.getRightNode(); System.out.println(tempNode); } // 替换这个遍历的节点 tempNode = tempNode.getRightNode(); } } public void preThreaddeList() { // 这里我们需要一个变量，存储当前的节点 heroNode tempNode = head; while (tempNode != null) { /* 开始循环遍历 * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点 * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了 * 之后只需要处理线索化之后的有效节点即可 * */ while (tempNode.getLefttype() == 0) { System.out.println(tempNode); tempNode = tempNode.getLeftNode(); } // 因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了 System.out.println(tempNode); // 替换这个遍历的节点 tempNode = tempNode.getRightNode(); } } //线索化节点 public void ThreadedNodes(heroNode node) { // 非空判断 if (node == null) { return; } // 线索化左子树 ThreadedNodes(node.getLeftNode()); // 线索化节点 //不太好理解这里以 8 举例子 // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点 if (node.getLeftNode() == null) { //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点 //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1 node.setLeftNode(pre); // 指向之后 将type改变为1 node.setLefttype(1); } //处理后继节点 //这里判断的前置节点非空并且前置节点没有后继结点 if (pre != null && pre.getRightNode() == null) { //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre = 8这里指向的意思是 8 的rightnode为3 pre.setRightNode(node); //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点 pre.setRighttype(1); } //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中 //否则会造成死递归 pre = node; // 线索化右子树 ThreadedNodes(node.getRightNode()); } //线索化节点 public void preThreadedNodes(heroNode node) { // 非空判断 if (node == null) { return; } // 线索化节点 //不太好理解这里以 8 举例子 // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点 if (node.getLeftNode() == null) { //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点 //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1 node.setLeftNode(pre); // 指向之后 将type改变为1 node.setLefttype(1); } //处理后继节点 //这里判断的前置节点非空并且前置节点没有后继结点 if (pre != null && pre.getRightNode() == null) { //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre = 8这里指向的意思是 8 的rightnode为3 pre.setRightNode(node); //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点 pre.setRighttype(1); } //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中 //否则会造成死递归 pre = node; if (node.getLefttype() == 0) { // 线索化左子树 preThreadedNodes(node.getLeftNode()); } if (node.getRighttype() == 0) { // 线索化右子树 preThreadedNodes(node.getRightNode()); } } //线索化节点 public void postThreadedNodes(heroNode node) { // 非空判断 if (node == null) { return; } // 线索化左子树 ThreadedNodes(node.getLeftNode()); // 线索化右子树 ThreadedNodes(node.getRightNode()); // 线索化节点 //不太好理解这里以 8 举例子 // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点 if (node.getLeftNode() == null) { //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点 //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1 node.setLeftNode(pre); // 指向之后 将type改变为1 node.setLefttype(1); } //处理后继节点 //这里判断的前置节点非空并且前置节点没有后继结点 if (pre != null && pre.getRightNode() == null) { //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre = 8这里指向的意思是 8 的rightnode为3 pre.setRightNode(node); //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点 pre.setRighttype(1); } //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中 //否则会造成死递归 pre = node; } // 前序遍历 public void preOrder() { if (this.head != null) { this.head.PreOrder(); } else { System.out.println("二叉树没有根节点，无法遍历"); } } //中序遍历 public void InfixOrder() { if (this.head != null) { this.head.infixOrder(); } else { System.out.println("二叉树没有根节点，无法遍历"); } } //后续遍历 public void PostOrder() { if (this.head != null) { this.head.postOrder(); } else { System.out.println("二叉树没有根节点，无法遍历"); } } //前序查找 public heroNode preOrderSearch(int no) { if (this.head != null) { return this.head.PreOrderSearch(no); } else { return null; } } //中序查找 public heroNode infixOrderSearch(int no) { if (this.head != null) { return this.head.infixOrderSearch(no); } else { return null; } } //后序查找 public heroNode postOrderSearch(int no) { if (this.head != null) { return this.head.postOrderSearch(no); } else { return null; } } // 删除节点 public void deleteNode(int no) { if (head != null) { if (head.getId() == no) { head = null; return; } else { head.deleteNode(no); } } else { System.out.println("空树,无法删除"); } } } class heroNode { private int id; private String name; private heroNode leftNode; private heroNode rightNode; //如果type 为 0 那么代表还有子树，如果type为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 getLeftNode() { return leftNode; } public void setLeftNode(heroNode leftNode) { this.leftNode = leftNode; } public heroNode getRightNode() { return rightNode; } public void setRightNode(heroNode rightNode) { this.rightNode = rightNode; } public heroNode(int id, String name) { this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } @Override public String toString() { return "heroNode{" + "id=" + id + ", name='" + name + '\'' + '}'; } public void setName(String name) { this.name = name; } // 前序遍历 public void PreOrder() { System.out.println(this); if (this.getLeftNode() != null) { this.leftNode.PreOrder(); } if (this.getRightNode() != null) { this.rightNode.PreOrder(); } } // 中序遍历 public void infixOrder() { if (this.leftNode != null) { this.leftNode.infixOrder(); } System.out.println(this); if (this.rightNode != null) { this.rightNode.infixOrder(); } } // 后序遍历 public void postOrder() { if (this.leftNode != null) { this.leftNode.postOrder(); } if (this.rightNode != null) { this.rightNode.postOrder(); } System.out.println(this); } // 前序查找 public heroNode PreOrderSearch(int no) { System.out.println("前序查找"); //比较当前节点的no 是不是我们要搜索的 if (this.id == no) { return this; } //要返回的节点 heroNode resNode = null; // 判断左边节点是不是空 如果不是空的话 那么就递归前序查找 // 如果找到的话 就返回找到的节点 if (this.leftNode != null) { resNode = this.leftNode.PreOrderSearch(no); } //如果不为null 那么代表左边找到了直接返回即可 if (resNode != null) { return resNode; } // 判断右边节点是不是空 如果不是空的话 那么就递归前序查找 // 如果找到的话 就返回找到的节点 if (this.rightNode != null) { resNode = this.rightNode.PreOrderSearch(no); } return resNode; } // 中序查找 public heroNode infixOrderSearch(int no) { //要返回的节点 heroNode resNode = null; // 判断左边节点是不是空 如果不是空的话 那么就递归中序查找 // 如果找到的话 就返回找到的节点 if (this.leftNode != null) { resNode = this.leftNode.infixOrderSearch(no); } //如果不为null 那么代表左边找到了直接返回即可 if (resNode != null) { return resNode; } //比较当前节点的no 是不是我们要搜索的 System.out.println("中序查找"); if (this.id == no) { return this; } // 判断右边节点是不是空 如果不是空的话 那么就递归中序查找 // 如果找到的话 就返回找到的节点 if (this.rightNode != null) { resNode = this.rightNode.infixOrderSearch(no); } return resNode; } // 后序查找 public heroNode postOrderSearch(int no) { //要返回的节点 heroNode resNode = null; // 判断左边节点是不是空 如果不是空的话 那么就递归后序查找 // 如果找到的话 就返回找到的节点 if (this.leftNode != null) { resNode = this.leftNode.postOrderSearch(no); } //如果不为null 那么代表左边找到了直接返回即可 if (resNode != null) { return resNode; } // 判断右边节点是不是空 如果不是空的话 那么就递归后序查找 // 如果找到的话 就返回找到的节点 if (this.rightNode != null) { resNode = this.rightNode.postOrderSearch(no); } //如果不为null 那么代表右边找到了直接返回即可 if (resNode != null) { return resNode; } System.out.println("后序查找"); //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的 if (this.id == no) { return this; } return resNode; } // 删除 public void deleteNode(int no) { // 向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边 if (this.leftNode != null && this.leftNode.id == no) { this.leftNode = null; return; } // 向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除 if (this.rightNode != null && this.rightNode.id == no) { this.rightNode = null; return; } // 如果上面两步都不成功那么我们先向左边递归删除 if (this.leftNode != null) { this.leftNode.deleteNode(no); } // 如果递归删除左子树也没有成功删除，那么就递归删除右边子树 if (this.rightNode != null) { this.rightNode.deleteNode(no); } } }
遍历线索化二叉树
说明：对前面的中序线索化的二叉树， 进行遍历
分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历
线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
public void preThreaddeList() { // 这里我们需要一个变量，存储当前的节点 heroNode tempNode = head; while (tempNode != null) { /* 开始循环遍历 * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点 * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了 * 之后只需要处理线索化之后的有效节点即可 * */ while (tempNode.getLefttype() == 0) { System.out.println(tempNode); tempNode = tempNode.getLeftNode(); } // 因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了 System.out.println(tempNode); // 替换这个遍历的节点 tempNode = tempNode.getRightNode(); } }
