一、线索化二叉树的原理
在前面介绍二叉树的文章中提到，二叉树可以使用两种存储结构：顺序存储和链式存储，在使用链式存储时，会存在大量的空指针域，n个节点的二叉链表中含有n+1[ 2n-(n-1)=n+1 ]个空指针域，为了可以充分利用这些空指针域，引申出了线索化二叉树，将这些空指针域利用起来，提高检索效率。
上图中，紫色区域就是没有指向的空指针域，从存储空间的角度来看，这些空指针域浪费了内存资源。
从另外的角度思考，如果需要知道C节点的前驱节点和后继节点，每次都都需要进行一次遍历，是否可以提前存储C节点的前驱节点和后继节点从而省去遍历的操作从而提高效率呢？
综合以上分析，可以通过充分利用二叉链表中的空指针域，存入节点在某种遍历方式下的前驱和后继节点的指针。
这种指向前驱和后继的指针成为线索，加上线索的二叉链成为线索链表，而对应的二叉树就称为线索化二叉树（Threaded Binary Tree）
二、构建线索化二叉树
- 先对二叉树进行中序遍历（不了解二叉树遍历的可以参考数据结构：二叉树），将所有节点右指针为空的指针域指针它的后继节点，如下图：
通过中序遍历到D节点，得到了D节点right指针为空，并且D节点后继节点为B，于是将D的right节点指向B节点（如上图中的①操作），而B节点right指针也为空，于是将right指针指向A节点（如上图中的②操作），以此类推，到F节点的后继节点为Null，则F的right指针指向Null。
-
接下来将这颗二叉树所有左指针为空的指针指向它的前驱节点，如下图：
如上图，D节点的left指针域指向Null（第⑤部操作），E节点的前驱节点是A，将E的left指针指向A节点，以此类推，F节点的left节点指向C节点。
-
通过上述两步操作完成了整个二叉树的线索化。
通过线索化后，可以看出（蓝色箭头表示前驱，粉色箭头表示后继）线索化二叉树相当于是把二叉树转换成一个特殊的双向链表，这样对新增、删除以及查找节点都带来了方便，提高了效率，转换为链表后的图示如下：
线索化需要对节点的结构进行修改，修改之后的数据结构如下：
class Node
{
private int num;
private Object data; //数据域
private Node left; //左指针域
private Node right; //右指针域
/**
* leftType == 0表示指向的是左子树,如果是1表示指向前驱节点
*/
private int leftType;
/**
* rightType == 0表示指向的是右子树,如果是1表示指向后继节点
*/
private int rightType;
}
三、代码实现线索二叉树
-
节点结构
class Node { private int num; private Object data; private Node left; private Node right; /** * leftType == 0表示指向的是左子树,如果是1表示指向前驱节点 */ private int leftType; /** * rightType == 0表示指向的是右子树,如果是1表示指向后继节点 */ private int rightType; public Node(int num, Object data) { this.num = num; this.data = data; } /** * 前序遍历 */ public void preOrder() { //先输出父节点信息 System.out.println(this); //判断此节点的左节点是否为空 //如果左节点不为空并且指针类型不是前驱类型 if (this.left != null && this.leftType != 1) { //向左前序遍历 this.left.preOrder(); } //判断此节点的右节点是否为空 //如果右节点不为空并且指针类型不是后继类型 if (this.right != null && this.rightType != 1) { //向右前序遍历 this.right.preOrder(); } } /** * 中序遍历线索化二叉树 */ public void infixOrder() { //判断此节点的左节点是否为空 if (this.left != null && this.leftType != 1) { //向左中序遍历 this.left.infixOrder(); } //输出父节点信息 System.out.println(this); //判断此节点的右节点是否为空 if (this.right != null && this.rightType != 1) { //向右中序遍历 this.right.infixOrder(); } } /** * 后序遍历 */ public void postOrder() { //判断此节点的左节点是否为空 if (this.left != null && this.leftType != 1) { //向左后序遍历 this.left.postOrder(); } //判断此节点的右节点是否为空 if (this.right != null && this.rightType != 1) { //向右后序遍历 this.right.postOrder(); } //输出父节点信息 System.out.println(this); } //get set方法省略 @Override public String toString() { return "Node{" + "num=" + num + ", data=" + data + '}'; } } -
线索化二叉树结构
/** * 定义ThreadedBinaryTree 实现了线索化功能的二叉树 */ class ThreadedBinaryTree { /** * 根节点 */ private Node root; /** * 为了实现线索化,需要创建要指向当前节点的前驱节点的指针 * 在递归进行线索化时,pre总是保留前一个节点 */ private Node pre = null; public void setRoot(Node root) { this.root = root; } public void createBinaryTree(ArrayList<Node> list) { this.createBinaryTree(list,0); } /** * 创建二叉树 * @param list 节点列表 * @param index 用于创建的索引 * @return */ private Node createBinaryTree(ArrayList<Node> list, int index) { Node node = null; if (isEmpty()) { setRoot(list.get(0)); } if (index < list.size()) { node = list.get(index); node.setLeft(createBinaryTree(list, (2*index+1))); node.setRight(createBinaryTree(list, (2*index+2))); } return node; } public boolean isEmpty() { return root == null; } public void preThreadNodes() { this.preThreadNodes(root); } public void infixThreadNodes() { this.infixThreadNodes(root); } public void postThreadNodes() { this.postThreadNodes(root); } /** * 前序线索化二叉树 * @param node 当前需要线索化的节点 */ private void preThreadNodes(Node node) { //递归回溯条件 if (node == null) { return; } //遍历到叶子节点(前驱指针未利用) if (node.getLeft() == null) { node.setLeft(pre); node.setLeftType(1); } //pre.getLeft() != node 一定不可少 //否则在第一次回溯后到父节点后,如果不加上此判断会让pre节点后驱指针指向该父节点 //此时pre的前驱后继节点均指向该父节点,必然会发生死循环无法结束递归 if (pre != null && pre.getRight() == null && pre.getLeft() != node) { pre.setRight(node); pre.setRightType(1); } pre = node; if (node.getLeftType() == 0) { preThreadNodes(node.getLeft()); } preThreadNodes(node.getRight()); } /** * 中序线索化二叉树 * @param node 当前需要线索化的节点 */ private void infixThreadNodes(Node node) { if (node == null) { return; } //1.递归线索化左子树 infixThreadNodes(node.getLeft()); //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; //3.递归线索化右子树 infixThreadNodes(node.getRight()); } /** * 后序线索化二叉树 * @param node 当前需要线索化的节点 */ private void postThreadNodes(Node node) { if (node == null) { return; } postThreadNodes(node.getLeft()); postThreadNodes(node.getRight()); if (node.getLeft() == null) { node.setLeft(pre); node.setLeftType(1); } if ( pre!= null && pre.getRight() == null ) { pre.setRight(node); pre.setRightType(1); } pre = node; } /** * 非递归方式中序遍历线索化二叉树的方法 */ public void threadedInfixList() { Node node = root; while (node != null) { //循环地找到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(); } } public void threadedTreePreList() { if (root != null) { root.preOrder(); }else { System.out.println("二叉树为空,无法遍历"); } } public void threadedTreeInfixList() { if (root != null) { root.infixOrder(); }else { System.out.println("二叉树为空,无法遍历"); } } public void threadedTreePostList() { if (root != null) { root.postOrder(); }else { System.out.println("二叉树为空,无法遍历"); } } }
以上。
如有不足或者错误欢迎评论指正。
整理不易，留个三连再走吧！