8.1 树结构基础 - 8.1.3 线索化二叉树 - 《数据结构与算法》

1. 概念
2. 实现
- 2.1 定义结构
- 2.2 实现线索化

1. 概念

1. 相关术语
      线索化：将节点的空指针域指向在【某种遍历次序】下的前驱节点和后驱节点的操作
    线索：上述线索化所附加的指针
    前驱节点：【某种遍历次序】下的前一个节点
    后驱节点：【某种遍历次序】下的后一个节点
2.二叉树的线索化：
    将二叉树线索化（将子叶的空指针利用起来）
        left 指向前驱动节点
        right 指向后驱节点
3.二叉树线索化的目的： 
     是为了解决二叉树每次遍历的时候都需要递归的问题
     线性化一次之后的二叉树就可以向链表那样遍历了，不需要每次都递归
4.什么时候线索化
         一般在构造器中完成
                 线索化过程中需要递归
                  后续遍历就不需要递归了
                       需要通过类链表的方式遍历
                        1）第一步找到头节点
                        2）根据指针那样往后走（无需递归）

2. 实现

2.1 定义结构

/**
 * 定义Node
 *    相对普通的二叉树： 增加了两个指针指向类型
 */
class ThreadedNode {

    private int no;
    private ThreadedNode left;
      private ThreadedNode right;

    // 0：表示左子节点；1表示前置节点
    private int rightType;
         // 0: 表示右子节点；1表示后继节点
    private int leftType;    

}

/**
 * 定义树
 */
class  ThreadedTree {


    ThreadedNode root;


    // 线索化 TODO 
    public void threaded(ThreadedNode node){}

    // 线索化下使用中序遍历 TODO
    public void threadedList() {}
}

2.2 实现线索化

实现线索化方法 ```java

/* 注意点：

（1）线索化要依据【指定遍历次序】线索化，这里是中序
（2）在线索化过程中需要使用一个成员变量保存前一个节点 */ class ThreadedTree { ThreadedNode root; // 记录在线索化过程中的上一节点 private static ThreadedNode pre;

// 直接在构造中线索化 public ThreadedTree(ThreadedNode root) { this.root = root; threaded(root); }

/**
- 线索化当前节点
- 这里采用中序线索化 */ public void threaded(ThreadedNode node) {
  
  if(node.getLeft() != null) { threaded(node.getLeft()); } /———-中序线索化——————-/ // 当前：处理左指针（保存了前驱节点） if(node.getLeft()==null){ node.setLeft(pre); node.setLeftType(1); } // 当前不能处理右指针（不知道后驱节点） // 但是可以处理上一次的，当前节点是pre的后驱节点 if(pre!=null && pre.getRight()==null) { pre.setRight(node); pre.setRightType(1); } // 更新pre pre = node; /——————————————/ if(node.getRight() != null) { threaded(node.getRight()); } } } ```

测试线索化 ```java /**
- 测试线索化是否成功
- 1
- / \
- 3 6
- / \ /
- 8 10 14
- 中序遍历次序：【 8,3,10,1,14,6 】
- 测试：
- 查看 node_10 的前驱节点和后驱节点 */
  
  public static void main(String[] args) { // 1.定义节点 ThreadedNode node_1 = new ThreadedNode(1); ThreadedNode node_3 = new ThreadedNode(3); ThreadedNode node_6 = new ThreadedNode(6); ThreadedNode node_8 = new ThreadedNode(8); ThreadedNode node_10 = new ThreadedNode(10); ThreadedNode node_14 = new ThreadedNode(14);
  
  // 2.设置关系 node_1.setLeft(node_3); node_1.setRight(node_6); node_3.setLeft(node_8); node_3.setRight(node_10); node_6.setLeft(node_14);
  
  // 3.创建树(在创建树的时候，完成线索化) new ThreadedTree(node_1);
  
  System.out.println(String.format(“node_10的前驱节点：【%s】”, node_10.getLeft().getNo())); System.out.println(String.format(“node_10的后驱节点：【%s】”, node_10.getRight().getNo())); }

//=======================测试结果输出======================================== // node_10的前驱节点：【3】 // node_10的后驱节点：【1】


<a name="qb8Ca"></a>
#### 2.3 对线索化后的二叉树遍历（中序）

1. 实现遍历方法
```java
public void threadedList() {

    // 从root开始
    ThreadedNode node = root;

    while (node!=null) {

        // 1. 找到次序头结点（处理左边的）
        while (node.getLeftType()==0){
            node = node.getLeft();
        }

        // 2. 中序输出
        System.out.print("【"+node.getNo()+"】"+"\t");

        // 3.处理右边的
        // 3.1 如果右指针指向后驱节点，直接输出
        while (node.getRightType()==1) {
            node = node.getRight();
            System.out.print("【"+node.getNo()+"】"+"\t");
        }

        node = node.getRight();
    }

}

测试 ```java /**
- 测试线索化后的遍历方法
- 1
- / \
- 3 6
- / \ /
- 8 10 14
- 中序遍历次序：【 8,3,10,1,14,6 】 */
  
  public static void main(String[] args) { // 1.定义节点 ThreadedNode node_1 = new ThreadedNode(1); ThreadedNode node_3 = new ThreadedNode(3); ThreadedNode node_6 = new ThreadedNode(6); ThreadedNode node_8 = new ThreadedNode(8); ThreadedNode node_10 = new ThreadedNode(10); ThreadedNode node_14 = new ThreadedNode(14);
  
  // 2.设置关系 node_1.setLeft(node_3); node_1.setRight(node_6); node_3.setLeft(node_8); node_3.setRight(node_10); node_6.setLeft(node_14);
  
  // 3.创建树(在创建树的时候，完成线索化) ThreadedTree tree = new ThreadedTree(node_1);
  
  // 测试遍历 tree.threadedList(); }

//================================输出==================================== // 【8】【3】【10】【1】【14】【6】 ```