概述
-
一般的二叉树，有左右子节点，如下图
- 对于叶子节点，它的左右子节点为空，有的非叶子节点可能只有一个子节点，而每一个节点又会占据一个空间，这样就会节约了这些创立进去的空间
- 线索化二叉树，利用了这些空间
线索化二叉树
-
线索化二叉树
- 如果节点的左子节点为空，则指向该节点的前驱节点
- 如果节点的右子节点为空，则指向该节点的后继节点
-
前驱和后继：
- 前驱：一个节点的前一个节点
- 后继：一个节点的后一个节点
- n个节点的二叉链表中含有n+1个为空的空间
- 依据遍历秩序的不同（即线索不同），线索二叉树可分为：前序线索二叉树、中序线索二叉树和后序线索二叉树
- 举个例子，将上图的一般二叉树线索化，如下图所示：依据前序遍历的后果，16的前驱节点是20，所以16的左子节点指向了20，16的后继节点是42，所以16的右子节点指向了42，以此类推
创立
-
基本思路：
- 采纳中序线索化的办法，先线索化左子树，再线索化以后节点，最初线索化右子树
- 1）线索化左子树
- 2）解决大以后节点的前驱节点：判断以后节点的左子节点是否为空，如果为空就把以后节点的左子节点指向前一个节点
- 3）解决以后节点的后继节点：判断以后节点的前驱节点是否为空，如果前一个节点不为空并且前以一个节点的右子节点为空，则把前一个节点的右子节点指向以后节点
- 4）让前驱节点指向以后节点
- 5）线索化右子树
- 留神：每一次递归，只能判断以后节点的左子节点和前驱节点的右子节点，因为没有方法晓得以后节点的下一个节点，只能晓得上一个节点
遍历
-
基本思路：
- 先从左子树循环的找到线索化节点，而后再从找到的这个节点，循环的去找她的线索化的右子节点
- 最初让以后节点指向后继节点
- 留神：因为咱们是中序线索化二叉树，所以第一个节点肯定是一个左子树的叶节点
代码如下
数据结构：
package 树;
public class TreeNode {
private Integer val;//序号
private TreeNode left;//左孩子
private TreeNode right;//右孩子
//leftType：0示意指向的左子树,如果1示意指向前驱节点
private int leftType;
//rightType：0示意指向的是右子树，如果1示意指向后继节点
private int rightType;
public TreeNode(int val){
this.val = val;
}
public Integer getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode 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 "TreeNode{" +
"val=" + val +
'}';
}
}具体算法：
package 树;
public class ThreadedBinaryTree {
//以后节点的上一个节点
private static TreeNode pre = null;
//根节点
private static TreeNode root;
private static final int IS_LEFT_CHILD = 0; //0示意是以后节点的左子节点指向的是左子树
private static final int IS_RIGHT_CHILD = 0; //0示意是以后节点的右子节点指向的是右子树
private static final int IS_PRE_NODE = 1; //1示意是以后节点的左子节点指向的是前驱节点
private static final int IS_AFTER_NODE = 1; //1示意是以后节点的右子节点指向的是后继节点
public static void setRoot(TreeNode root) {
ThreadedBinaryTree.root = root;
}
//线索化遍历二叉树
public static void threadedList(){
//设置以后节点
TreeNode node = root;
if (node == null) return;
while (node != null){
//找到leftType == 1的节点
while (node.getLeftType() == IS_LEFT_CHILD){
node = node.getLeft();
}
//打印以后节点
System.out.println(node.getVal());
//如果以后节点的右子节点指向的是后继节点，就统一输入
while (node.getRightType() == IS_AFTER_NODE){
node = node.getRight();
System.out.println(node.getVal());
}
//替换这个遍历的节点
node = node.getRight();
}
}
//对二叉树进行中序线索化的办法
public static void threadedNodes(TreeNode node){
if (node == null) return;
//1、先线索化左子树
threadedNodes(node.getLeft());
//2、线索化以后节点
//2.1 解决以后节点的前驱节点
if (node.getLeft() == null){
//批改以后节点的左子节点，指向前驱节点
node.setLeft(pre);
node.setLeftType(IS_PRE_NODE);
}
//2.2 解决以后节点的后继节点
if (pre != null && pre.getRight() == null){
//让前驱节点的右子节点指向以后节点
pre.setRight(node);
pre.setRightType(IS_AFTER_NODE);
}
//每次解决一个节点后，让下一个节点的前驱节点指向以后节点
pre = node;
//3、线索化右子树
threadedNodes(node.getRight());
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(6);
TreeNode node4 = new TreeNode(8);
TreeNode node5 = new TreeNode(10);
TreeNode node6 = new TreeNode(14);
node1.setLeft(node2);
node1.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
setRoot(node1);
threadedNodes(node1);
// TreeNode right = node3.getRight();
// TreeNode preNode = node5.getLeft();
// TreeNode afterNode = node5.getRight();
// System.out.println(right);
// System.out.println(preNode);
// System.out.println(afterNode);
//
threadedList();
}
}因为算法如果用字数可能不太分明，倡议还是联合代码和图片本人走一遍流程
发表回复