树结构入门教程-线索化二叉树

上节我们学习了数组和树之间相互转化储存过程,我们可以将树中的节点按照前中后序的遍历结果存储在数组中,同样也可以将我们数组的中元素转化成一棵树,本节我们来看树的另外一个特点--------->线索化,首先我们来了解下线索化二叉树的概念.

引出

我们先看一个问题,假如我有一组数列{1,3,6,8,10,14},我们准备将它构建成如下图所示的这样一棵二叉树:

二叉树.png

当我们对上述图中的二叉树进行中序遍历时,我们都知道结果为{8,3,10,1,14,6},同时我们也会发现问题了,具体什么问题,如下:

• 首先我们会发现二叉树的节点8 10 6 14其实并没有完全利用

假设我有这样的需求:希望充分利用各个节点的左右指针,让各个节点指向自己的前后节点,那么我们应该怎么办?

• 关于上述这个问题的解决答案就是我们的线索化二叉树

那么既然有了需求,同时也有了解决方案,首先我们来了解下什么是线索化二叉树

线索化二叉树的介绍

n个节点的二叉链表含有n+1个(计算公式为:2n-(n-1)= n+1)个空指针域,我们可以利用这些空指针域来存指向节点在某种遍历次序下的前驱和后继节点的指针,对于这样的指针我们称之为"线索"

同时这种加上了线索的二叉树我们称它为线索二叉树,根据线索性质的不同,线索二叉树可划分为:前序线索二叉树 中序线索二叉树以及后序线索二叉树三种

其中一个节点的前一个节点我们称之为前驱节点

同样的,一个节点的后一个节点我们称之为后继节点

对线索化二叉树有了初步的认识之后,我们来简单的看下它具体实现的过程,我们还是按照上述引出时提出的问题来分析.这里我们首先对二叉树进行中序排序其结果为:{8,3,10,1,14,6}

中序索引化二叉树.png

见谅,这里我们用文字来描述过程,我们就采用中序遍历的方式进行索引化

• 由于我这里需要辅助变量(指针) 来时时刻刻记录我们的前驱节点,假设我的指针为 Node pre
• leftType:如果leftType ==0表示为左子树,如果是为1表示指向前驱节点
• rightType:如果 rightType ==0表示指向右子树,如果是为1时表示指向后继节点

我们分别通过上述三种变量来操作我们中序线索化二叉树的整个过程,接下来我们来看次过程:

• 首先我们来递归左子树直到找到node.left ==null(表示我们已经找到了当前node为叶子节点)也就是图中的节点8,那么我们将开始对该节点进行索引化处理,设置它的前驱节点(因为节点8的前驱节点为null,假设节点8有一个指针指向pre),此时pre就是节点8的前驱节点,我们记录它也就是pre = null.
• 此时我们按照中序遍历的特点我们知到递归的特点会返回上一个栈也就是节点3处,然后节点8有一个指针指向节点3,(如上图所示)那么节点3就是节点8的后继节点,同时记录pre = 3,以便线索化后面的节点

那么节点8我们就完成了线索化,此时我们发现节8的前后指针得到了充分的利用,简单的在来说下,注意:对于一个左右两边都挂满了的节点是无法线索化的,接着我们来看节点10 ,简单的说节点10 的前驱节点为3,后继节点就是1(也就是图中的所画的线的指向)

简单的原理处理逻辑是这样的,有时候文字无法表达清楚,我们接下来看代码实现过程,其实看完代码你就会发现不是很难理解.

代码实现

首先我们需要一个节点类,代码如下:

  //创建HeroNode节点
class HeroNode{
private int no; //编号
private String name;
private HeroNode left;//默认为null
private HeroNode right;//默认为null
private int leftType; //如果leftType ==0表示为左子树,如果是为1表示指向前驱节点
private int rightType;//如果 rightType ==0表示指向右子树,如果是为1时表示指向后继节点
//构造器
public HeroNode(int no, String name) {
    this.no = no;
    this.name = name;
}
//中序遍历
public void midOrder(){
    //1.先输出左子树的节点信息
    if (this.left !=null){
        this.left.midOrder();
    }
    //2.输出父节点信息
    System.out.println(this);
    //3.输出右子树的节点信息
    if (this.right !=null){
        this.right.midOrder();
    }
}
....

关于它的 set和get和toString这里我就省略了...,接着我们看核心方法那就是线索化过程

class BinaryTree{
private HeroNode root;

//为了方便处理,pre用来保留当前节点的前驱节点的指针
private HeroNode pre = null;
public void setRoot(HeroNode root) {
    this.root = root;
}
/**
 *
 * @param node 要被线索化的节点
 */
public void threadedNodes(HeroNode node){
    //如果我们的root为null,是无法线索化的
    if (node == null){
        return;
    }
    //1.先先线索化左子树
    threadedNodes(node.getLeft());

    //2.线索化当前节点
    //2.1 首先我们来处理当前节点的前驱节点
    //以节点8为例
    //此时8节点的left == null, 8节点的leftType = 1的
    //因为8节点的前驱节点是为null的
    if (node.getLeft() == null){
        //设置前驱节点
        node.setLeft(pre);
        //设置类型为前驱节点类型
        node.setLeftType(1);
    }
    //处理后继节点
    //只有 pre.getRight() ==null时我们才去处理
    //当处理完前驱结点后,处理后继节点时,我们让node指向3,pre指向8
    if (pre !=null && pre.getRight() ==null){
        //让前驱节点的右指针指向当前节点
        pre.setRight(node);
        //修改后继节点的节点节点类型
        pre.setRightType(1);
    }
    //没处理一个节点后,我们让当前节点是下一个节点的前驱节点
    pre = node;
    //3.最后线索化右子树
    threadedNodes(node.getRight());

}

这就是我们最核心的方法,我们接着来测试一把,测试代码如下:

/**
 * 线索化二叉树
 */
public class ThreadedBinaryTreeCase {
public static void main(String[] args) {

    HeroNode root = new HeroNode(1,"小明");
    HeroNode node2 = new HeroNode(3,"小黑");
    HeroNode node3 = new HeroNode(6,"小虎");
    HeroNode node4 = new HeroNode(8,"小张");
    HeroNode node5 = new HeroNode(10,"小三");
    HeroNode node6 = new HeroNode(14,"小狗");

    root.setLeft(node2);
    root.setRight(node3);
    node2.setLeft(node4);
    node2.setRight(node5);

    node3.setLeft(node6);
    //手动创建二叉树,并设置节点之间的关系
    BinaryTree binaryTree = new BinaryTree();
    //设置根节点
    binaryTree.setRoot(root);

我们的节点也创建好了,这里我们以node5作为测试节点,测试前我们先看下这颗二叉树前序遍历的结果是怎么样的

在 BinaryTree 类中我们重载HerNode的midOrder方法,其目的是为了我们调用方便

     public void midOrder(){
    if (this.root !=null){
        this.root.midOrder();
    }else {
        System.out.println("二叉树为null");
    }
}

来测试前序遍历的结果,在我们的main函数里直接调用binaryTree.midOrder();方法,测试结果如下:

中序遍历结果图.png

按照我们之前的分析,那么节点10的前驱节点为3,后继节点是1,我们来测试一把,因为我们知道对于已经线索化的节点,节点之间的指向是已经发生了改变,所以我们不能采用之前的那种遍历方式进行操作,具体如何如何遍历我们来看代码:

在BinaryTree类中新增遍历方法:

   //线索化二叉树的中序遍历
public void threadedList(){
    //定义一个变量来存储当前遍历的节点,先从root节点开始
    HeroNode node = root;
    while (node !=null){
        //循环找到leftType=1的那个节点,第一个应该是节点8
        //注意:node是发生变化的,因为当leftType==1时,表明了该节点是按照线索化处理后的节点
        while (node.getLeftType() ==0){ //一直找==1的
            node = node.getLeft();
        }
        //打印当前这个节点
        System.out.println(node);
        //如果当前节点的右指针指向的是后继节点,我们就一直输出
        while (node.getRightType() ==1){
            //获取到当前节点的后继节点
            node = node.getRight();
            System.out.println(node);
        }
        //替换遍历的节点
        node = node.getRight();
    }
}

对节点node5进行索引化的测试,代码如下:

//测试以10号节点为例
    binaryTree.threadedNodes();
    HeroNode leftNode = node5.getLeft();
    HeroNode rightNode = node5.getRight();
    System.out.println("10号节点的前驱节点为:"+leftNode);
    System.out.println("10号节点的后继节点为:"+rightNode);
    System.out.println("使用线索化遍历的方式来遍历 线索化二叉树(采用中序遍历)");
    binaryTree.threadedList();

来看测试结果如下图:

中序线索化二叉树测试结果图.png

跟我们之前预想的结果是一样的,那么关于中序线索化二叉树的学习就到这里了,关于前序和后序线索化的代码已经上传到git上感兴趣的可以自己去看看

• git地址: https://gitee.com/cblove_java/nacos_learning_demo