共计 3334 个字符,预计需要花费 9 分钟才能阅读完成。
概述
-
一般的二叉树,有左右子节点,如下图
- 对于叶子节点,它的左右子节点为空,有的非叶子节点可能只有一个子节点,而每一个节点又会占据一个空间,这样就会节约了这些创立进去的空间
- 线索化二叉树,利用了这些空间
线索化二叉树
-
线索化二叉树
- 如果节点的左子节点为空,则指向该节点的前驱节点
- 如果节点的右子节点为空,则指向该节点的后继节点
-
前驱和后继:
- 前驱:一个节点的前一个节点
- 后继:一个节点的后一个节点
- 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();}
}
因为算法如果用字数可能不太分明,倡议还是联合代码和图片本人走一遍流程
正文完