线索化二叉树（线索化二叉树遍历方法，倒序线索化二叉树遍历结果）

淩亂°似流年 2023-02-20 07:28 26阅读 0赞

本篇介绍线索化二叉树、线索化后的中序遍历以及反向输出中序遍历。  
注：（不管是前序遍历、中序遍历或者后序遍历，道理都是一样的，只不过顺序不一样，所以本篇的就拿中序遍历作为讲解，方便统一与理解）

### 文章目录 ###

*  1.线索化二叉树
 *   *  1.1-什么是线索化二叉树
     *  1.2-线索化二叉树的意义
     *  1.3-线索化二叉树完整代码
 *  2.线索化后的中序遍历
 *   *  2.1-思路
     *  2.2-完整代码
 *  3.（拓展）利用线索化后的二叉树反向输出中序遍历
 *   *  3.1-思路
     *  3.2-完整代码

# 1.线索化二叉树 #

## 1.1-什么是线索化二叉树 ##

首先思考一下：我们知道，不管是二叉树的前序遍历、中序遍历还是后序遍历最简单的方法就是通过递归进行。由于递归需要系统堆栈，会消耗大量的空间，如果一个二叉树过于“庞大”导致需要递归到很深的时候，系统就可能崩溃。这时我们就会想到，能否根据前序、中序或者后序遍历的过程，用一个数组或者链表来存储二叉树相应的节点呢？显而易见，数组是不可能实现的。由于二叉树的结构就是用地址相互连接起来的，所以只能用链表来实现。那么这个链表还需不需要我们来重新创建？答案是不用的，前人已经为我们设计好了在原二叉树上创建链表的方法。先观察观察这一个二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
图中节点的个数总共有`6`个，我们知道每个节点都有两个指针域分别指向左，右子节点。但是我们可以看到，不是每个节点这两个指针域都有使用，恰恰许多浪费了。例如上图，节点4，5，6left,right都是null,节点3right也为null。结论就是：`空指针的个数 =节点个数 + 1`而我们线索化二叉树的方法就是将这些浪费的指针利用起来。

> 由于遍历方法有前、中、后续遍历，所以对应的线索化方法也有前序遍历、中序遍历、后续遍历二叉树线索化。本篇只介绍中序遍历线索化二叉树方法，其他道理都是相同的

具体方法就是:将空出来的left用来指向前驱节点，right用来指向后继节点。**同时为了区分节点left指向的到底是原二叉树左孩子节点还是遍历结果的前驱节点、right指向的是原二叉树右孩子节点还是遍历结果的后继节点。我们定义leftType,rightType做标记，规则就是当leftType,rightType等于1时代表left，right指向前驱或者后继节点，当leftType,rightType等于0时代表left，right指向左孩子节点或者右孩子节点。**（这里必须理解）。`以上话总结就是：一个节点的left,right指向的节点有两层含义，一、指向的是左孩子或右孩子节点，二、指向的是前驱或者后继节点，而leftType,rightType这两个标记的作用就是用来区分这两层含义。`  
所以我们需要将原节点改造为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
每个节点不再只包含数据域，指针域，还需要包含两个标记元素。  
线索化过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]  
解释：以上图片中，`红色指针代表指向的是中序遍历结果的前驱或者后继节点及线索化，并且标记元素的值为1。可以看到节点4在遍历结果是第一位，没有前驱节点，所以节点4的left指向null,并且打上标记。节点4的后继节点为节点2，所以节点4空出来的right指向后继节点（节点2），并打上标记。`后面的过程以此类推，不再赘述。

经过线索化后的二叉树，此时已经相当于一个双向链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]

## 1.2-线索化二叉树的意义 ##

可以看到，经过线索化的二叉树相当于一个双向链表。我们既可以通过这个链表中的某个节点找到前驱和后继节点，也可以很方便的删除或者添加节点。以及进行更加复杂的操作。同时，在我们遍历二叉树的时候，不再使用递归进行，避免了空间资源的浪费。而是通过遍历链表的方式进行。是不是非常的巧妙？

## 1.3-线索化二叉树完整代码 ##

最后给出完整代码：

//中序遍历线索化方法
        public void threadedNodes(Node root){
        
            Node node = root;
            if (node == null){
        
                return;
            }
            //先线索化左子树
            threadedNodes(node.getLeft());
            //再线索化当前节点
            //处理前驱节点
            if (node.getLeft() == null){
        
                //当前节点指向前驱节点
                node.setLeft(pre);
                //修改类型
                node.setLeftType(1);
            }
            //处理后续节点
            if (pre != null && pre.getRight() == null){
        
                //当前节点right指向后续节点
                pre.setRight(node);
                //修改类型
                pre.setRightType(1);
            }
            //再当前节点递归到下一个节点之前，保存该节点。
            // 作用就是：指向当前线索节点的前一个节点
            pre = node;
            //最后线索化右子树
            threadedNodes(node.getRight());
        }

> 注意：以上代码中的pre定义在了该方法所在的类中，初始化为null,这里只给出了方法片段。pre代表着指向节点的指针，且该指针的作用就是指向当前节点的前一个节点。

# 2.线索化后的中序遍历 #

## 2.1-思路 ##

毫无疑问，我们首先需要找到第一个节点。由于线索化后的二叉树，每个节点都保存了下了一个节点的位置。所以可以根据节点的right指针域找到后继节点。由于每个节点的right指针域有两次含义，所以需要判断rightType标记的值。

## 2.2-完整代码 ##

具体代码：

//找到中序遍历下一个节点的方法
        public Node findNext(Node node){
        
            Node p = node;
            //表明right指向后继节点
            if (node.getRightType() == 1){
        //标记等于1则代表right存储的是后继节点
                p = node.getRight();
            }else {
        
                //表明right指向孩子节点
                p = node.getRight();//关键
                //标记等于0则代表left存储的是孩子节点
                //循环结束后表示找到了最左下节点
                while (p.getLeftType() == 0){
        
                    p = p.getLeft();
                }
            }
            return p;
        }
        //中序线索化遍历
        public void threadedInfixOrder(Node root){
        
            Node p;//存储root
            if (root == null){
        
                return;
            }
            p = root;
            //找到中序遍历的第一个节点
            while (p.getLeft() != null){
        
                p = p.getLeft();
            }
            System.out.println(p);//输出第一个节点
    
            while (p.getRight() != null){
        //循环输出后继节点，当p.getRight() == 则代表已经到了最后
                p = findNext(p);//调用前面定义的方法
                System.out.println(p);
            }
        }

# 3.（拓展）利用线索化后的二叉树反向输出中序遍历 #

## 3.1-思路 ##

前面我们进行了二叉树线索化后的中序遍历，思路就是要找到中序遍历序列的第一个节点，如果在此基础上反向输出，则需要找到最后一个节点。根据节点的left域依次向前查找，由于left域也有两层含义，前驱节点或者左孩子节点。所以还是要先判断标记leftType的值。

## 3.2-完整代码 ##

//找到中序遍历前一个节点的方法
        public Node findFront(Node node){
        
            Node p = node;
            if (node.getLeftType() == 1){
        //表示是前驱节点
                p = node.getLeft();
            }else {
        
                p = node.getLeft();
                //找到最右下的节点
                while (p.getRightType() == 0){
        
                    p = p.getRight();
                }
            }
            return p;
        }
         //线索化反序中序遍历
        public void threadedInvertedInfixOrder(Node root){
        
            Node p;
            if (root == null){
        
                return;
            }
            p = root;
            //找到中序遍历最后一个节点
            while (p.getRight() != null){
        
                p = p.getRight();
            }
            System.out.println(p);
            //循环向前查找
            while (p.getLeft() != null){
        
                p = findFront(p);
                System.out.println(p);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200624163706307.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/2020062417204467.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020062417223428.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200624173551426.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center