本文共 11863 字，大约阅读时间需要 39 分钟。

1、线索二叉树的引入

简而言之就是：因为叶子结点或仅一个子结点存在时，二叉树的左右指针会有资源浪费的现象，因此引入线索化二叉树，重新利用起无指向的指针情况

2、线索二叉树的概念

3、线索二叉树的应用与图解

• 问题描述
  
• 由于线索二叉树是通过无指向的指针来指向前驱结点与后继结点的，因此线索二叉树一定与某种特定的遍历方式有关。所以，这里以中序遍历线索二叉树为例，对线索二叉树进行图解分析
  
  由上图的二叉树可以得出其中序遍历序列：8-3-10-1-14-6
  由线索二叉树的概念可知，将无指向的左指针指向遍历序列中的前驱结点，将无指向的右指针指向遍历序列中的后继结点
  对上图进行修改，可以得到下面的二叉树结构
  
• 具体说明
  

4、线索二叉树的代码实现

由于在未经线索化的二叉树结构中，结点的左右指针分别指向其左右子树；而在线索化二叉树结构中，左右指针分别指向其前驱结点和后继结点

因此需要对其左右指针所指向的内容需要进行区分 这里通过为左右指针新增对应的type属性来判断该指针指向的到底代表哪种含义

Node.class

package threaded_bin_tree;/** * @author zhihua.li * @date 2021/2/15 - 23:46 **/public class Node {       private Integer no;    private String name;    private Node left;    private Node right;//    若 leftType/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 Node(Integer no, String name) {           this.no = no;        this.name = name;    }    //    前序遍历： 根 左 右    public void preOrderIterate() {   //        不用判断该节点是否为空        System.out.println(this);        if (this.left != null) {               this.left.preOrderIterate();        }        if (this.right != null) {               this.right.preOrderIterate();        }    }    //    中序遍历：左 根 右    public void midOrderIterate() {           if (this.left != null) {               this.left.midOrderIterate();        }        System.out.println(this);        if (this.right != null) {               this.right.midOrderIterate();        }    }    //    后序遍历：左 右 根    public void postIterate() {           if (this.left != null) {               this.left.postIterate();        }        if (this.right != null) {               this.right.postIterate();        }        System.out.println(this);    }    @Override    public String toString() {           return "binary_tree.Node{" +                "no=" + no +                ", name='" + name + '\'' +                '}';    }    public Integer getNo() {           return no;    }    public void setNo(Integer no) {           this.no = no;    }    public String getName() {           return name;    }    public void setName(String name) {           this.name = name;    }    public Node getLeft() {           return left;    }    public void setLeft(Node left) {           this.left = left;    }    public Node getRight() {           return right;    }    public void setRight(Node right) {           this.right = right;    }}

ThreadedBinaryTree.class

package threaded_bin_tree;/** * @author zhihua.li * @date 2021/2/16 - 19:41 **//** * @program: DataStructure * @description: 线索二叉树代码实现 * @author: zhihua li * @create: 2021-02-16 19:41 */public class ThreadedBinaryTree {       private Node root;    //    设置前驱结点，初始化为null    private Node pre = null;    public ThreadedBinaryTree(Node root) {           this.root = root;    }    public Node getPre() {           return pre;    }    public void setPre(Node pre) {           this.pre = pre;    }    //    先序线索化二叉树    public void preThreadedNodes(Node node) {   //        若传入结点为空，则直接返回        if (node == null) {               return;        }//        对当前节点进行线索化：//        如果当前节点的左子节点为空，则设置当前结点的左子节点为pre，并且设置type为1        if (node.getLeft() == null) {               node.setLeft(pre);            node.setLeftType(1);        }//        若保存的pre结点不为空且该节点的右子节点为空，说明可以保存其后继结点到right中        if (pre != null && pre.getRight() == null) {   //            给pre结点（上一次递归的结点，也为本次执行的前驱结点）设置后继结点为node            pre.setRight(node);            pre.setRightType(1);        }//        让pre后移为当前节点        pre = node;//        对其左子节点进行递归线索化.不加判断的话会造成死循环//        比如 3-8-3-8....        if(node.getLeftType()==0) {               preThreadedNodes(node.getLeft());        }//        对其右子节点进行递归线索化        if(node.getRightType()==0) {               preThreadedNodes(node.getRight());        }    }    //中序线索化二叉树    public void midThreadedNodes(Node node) {   //        当前递归的终止条件        if (node == null) {               return;        }//        线索化左子树        midThreadedNodes(node.getLeft());//        线索化当前结点//        1.处理当前结点的前驱结点：        if (node.getLeft() == null) {   //            让当前节点的左指针指向前驱结点            node.setLeft(pre);//            修改左指针类型            node.setLeftType(1);        }//        2.处理当前结点的后继结点        if (pre != null && pre.getRight() == null) {               pre.setRight(node);            pre.setRightType(1);        }//        将当前结点设置为前驱结点以便下次递归设置，pre也是动态的        pre = node;//        线索化右子树        midThreadedNodes(node.getRight());    }    //后序线索化二叉树    public void postThreadedNodes(Node node) {           if (node == null) {               return;        }//        线索化当前结点的左子结点        postThreadedNodes(node.getLeft());//        线索化当前结点的右子结点        postThreadedNodes(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也是动态的        pre = node;    }    public void preThreadedList(){           if(root!=null){               root.preOrderIterate();        }        System.out.println("当前根节点为空");    }    public void midThreadedList(){           if(root!=null){               root.midOrderIterate();        }        System.out.println("当前根节点为空");    }    public void postThreadedList(){           if(root!=null){               root.postIterate();        }        System.out.println("当前根节点为空");    }}

注意：先序遍历线索化二叉树时，需要对当前结点的左右结点进行判断，看其是否为前驱/后继结点，如果当前结点的左指针已经修改为其前驱结点，就不对其左子树进行递归操作了，同理，右子树也一样

5、线索二叉树的测试

设计二叉树结构为下图，分别对三种遍历方式的线索化进行测试：

1、先序线索化

ThreadedBinaryTreeTest

package threaded_bin_tree;/** * @author zhihua.li * @date 2021/2/16 - 21:16 **//** *@program: DataStructure *@description: 测试线索二叉树 *@author: zhihua li *@create: 2021-02-16 21:16 */public class ThreadedBinaryTreeTest {       public static void main(String[] args) {           Node root = new Node(1,"tom");        Node node2 = new Node(3,"jack");        Node node3 = new Node(6,"smith");        Node node4 = new Node(8,"mary");        Node node5 = new Node(10,"king");        Node node6 = new Node(14,"dim");        root.setLeft(node2);        root.setRight(node3);        node2.setLeft(node4);        node2.setRight(node5);        node3.setLeft(node6);//        测试线索化,以node5为例，若正常线索化，则包含前驱结点和后继结点//		  由下图中的先序遍历分析可知//        node5（no=10）的前驱结点为8，后继结点为6        ThreadedBinaryTree tree = new ThreadedBinaryTree(root);        tree.preThreadedNodes(root);                System.out.println(node5.getLeft());        System.out.println(node5.getRight());    }}

测试结果：

2、中序线索化

package threaded_bin_tree;/** * @author zhihua.li * @date 2021/2/16 - 21:16 **//** *@program: DataStructure *@description: 测试线索二叉树 *@author: zhihua li *@create: 2021-02-16 21:16 */public class ThreadedBinaryTreeTest {       public static void main(String[] args) {           Node root = new Node(1,"tom");        Node node2 = new Node(3,"jack");        Node node3 = new Node(6,"smith");        Node node4 = new Node(8,"mary");        Node node5 = new Node(10,"king");        Node node6 = new Node(14,"dim");        root.setLeft(node2);        root.setRight(node3);        node2.setLeft(node4);        node2.setRight(node5);        node3.setLeft(node6);//        测试线索化,以node5为例，若正常线索化，则包含前驱结点和后继结点//		  由下图中的先序遍历分析可知//        node5（no=10）的前驱结点为3，后继结点为1        ThreadedBinaryTree tree = new ThreadedBinaryTree(root);        tree.midThreadedNodes(root);                System.out.println(node5.getLeft());        System.out.println(node5.getRight());    }}

测试结果：

3、后序线索化

package threaded_bin_tree;/** * @author zhihua.li * @date 2021/2/16 - 21:16 **//** *@program: DataStructure *@description: 测试线索二叉树 *@author: zhihua li *@create: 2021-02-16 21:16 */public class ThreadedBinaryTreeTest {       public static void main(String[] args) {           Node root = new Node(1,"tom");        Node node2 = new Node(3,"jack");        Node node3 = new Node(6,"smith");        Node node4 = new Node(8,"mary");        Node node5 = new Node(10,"king");        Node node6 = new Node(14,"dim");        root.setLeft(node2);        root.setRight(node3);        node2.setLeft(node4);        node2.setRight(node5);        node3.setLeft(node6);//        测试线索化,以node5为例，若正常线索化，则包含前驱结点和后继结点//		  由下图中的先序遍历分析可知//        node5（no=10）的前驱结点为8，后继结点为3        ThreadedBinaryTree tree = new ThreadedBinaryTree(root);        tree.postThreadedNodes(root);                System.out.println(node5.getLeft());        System.out.println(node5.getRight());    }}

测试结果：

6、线索二叉树的遍历

1、问题描述

注意点： 遍历线索化二叉树的前提是与线索化的顺序相同，比如中序遍历线索化二叉树时，对象必须是经过中序线索化后的二叉树

2、代码实现

public void midThreadedList() {           //        定义变量接收当前结点的root结点        Node node = root;        while (node != null) {   //            循环的找到leftType为1的点,当leftType为1时，说明该节点已经历过线索化处理            while (node.getLeftType() == 0) {                   node = node.getLeft();            }            System.out.println(node);//            循环找到rightType为1的点并打印            while (node.getRightType() == 1) {                   node = node.getRight();                System.out.println(node);            }            node = node.getRight();        }    }

3、代码测试

public class ThreadedBinaryTreeTest {       public static void main(String[] args) {           Node root = new Node(1,"tom");        Node node2 = new Node(3,"jack");        Node node3 = new Node(6,"smith");        Node node4 = new Node(8,"mary");        Node node5 = new Node(10,"king");        Node node6 = new Node(14,"dim");        root.setLeft(node2);        root.setRight(node3);        node2.setLeft(node4);        node2.setRight(node5);        node3.setLeft(node6);		ThreadedBinaryTree tree = new ThreadedBinaryTree(root);        tree.midThreadedNodes(root);        // 遍历顺序与线索化顺序必须一致        tree.midThreadedList();

4、扩展

1、先序遍历线索化二叉树

前序遍历代码如下：

//    遍历线索化二叉树（先序）的方法：    public void preThreadedList() {           Node node = root;        while (node != null) {   //            先序遍历线索二叉树//            先打印当前二叉树的根节点            System.out.println(node);            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();        }    }

2、后序遍历线索化二叉树【推导较难】

后序遍历遇到的问题：

在本例中，由所给二叉树后序遍历序列为：8-10-3-14-6-1 由后序线索化可得下图中的线索二叉树

在遍历的过程中会遇到这样的情况：

• 1-3-8-10的过程省略。。。

  当遍历到10结点时，其后继结点为3，而3的右指针指向的仅仅为右子树而并不代表后继结点，所以在这里会造成一直访问3-8-10-3…而无法直接跳转到右子树中的14结点

• 因此我想到了需要对左右子树分别遍历，左子树中断后跳转到右子树对右子树进行遍历，最后遍历根结点

• 其次对于一直3-8-10-3-8-…的循环，为了打破这个死循环，我能想到的只有为遍历过的结点添加一个标志，来避免一直循环该结点

具体代码实现

//    遍历线索化二叉树（后序）的方法：    public void postThreadedList() {           Node node = root;        //为了避免死循环，为Node.class新增hasList属性        while(node.getLeftType()==0&&node.hasList == false){               node.hasList = true;            node = node.getLeft();        }        System.out.println(node);        while (node.getRightType()==1) {               node = node.getRight();            System.out.println(node);        }        //左子树遍历结束，开始遍历右子树        node = root.getRight();        //对右子树进行相同遍历操作        while(node.getLeftType()==0&&node.hasList == false){               node.hasList = true;            node = node.getLeft();        }        System.out.println(node);        while (node.getRightType()==1) {               node = node.getRight();            //注意这里不需要对根结点再次输出，因为6结点的后缀结点就为1结点，因此直接循环即可打印出root结点            System.out.println(node);        }        }