乐趣区

关于java:我所知道的数据结构之线索化二叉树

上一篇咱们学习顺序存储二叉树,这时呈现一个问题,咱们来看看

将数列{1,3,6,8,10,14},构建成一颗二叉树

这时候咱们发现一些问题,一起进行剖析看看
1. 当咱们对 二叉树 进行 中序遍历 时,数列为 {8,3,10,1,14,6}
2.6,8,10,14 节点的 左右指针 没有充沛 利用
3. 遍历二叉树时除了应用递归遍历二叉树,那么有没有其余办法呢?
4. 心愿利用各个节点左右指针,间接指向左右节点怎么解决?

一、什么是线索化二叉树

针对于后面的问题咱们聊聊线索化二叉树

依据上图所示,咱们发现如果 应用二叉链表 展现 二叉树 就会 发现 n 个节点 中会含有 n+ 1 个空指针域,即上图 有七个空指针域

公式:2n - (n-1) = n+1

因为一共有 2n 个指针,除了根节点,每个节点都被自指针援用

咱们来看看是不是这样?如下图所示

线索二叉树根本介绍

1. 利用 二叉表 空指针域 ,寄存指向该结点在 某种遍历秩序下的前驱与后续节点的指针 称为线索

2. 这种加上了 线索的二叉链表 称为 线索链表 ,相应的二叉树也称为 线索二叉树 ,依据性质不同别离有 前序、中序、后序等线索二叉树

3. 一个结点的前一个节点,称为 前驱节点

4. 一个结点的后一个节点,称为 后续节点

二、通过示例意识线索化二叉树

示例利用案例阐明:

将上面的 二叉树 进行 中序线索二叉树,中序后果为{8,3,10,1,14,6}

利用示例图解剖析

中序遍历后果:{8,3,10,1,14,6}进行线索化,该怎么操作?

咱们发现 [节点八]前驱节点 Null后继节点 [节点三],要 关联

[节点三]前驱节点 [节点八]后继节点 [节点十],但 [节点三] 已指向两子节点 ,则 无需关联

[节点十]前驱节点 [节点三],要 关联 后继节点 [节点一],要 关联

[节点一]前驱节点 [节点十]后继节点 [节点十四],但 [节点一] 已指向两子节点 ,则无需 关联

[节点十四]前驱节点 [节点一],要 关联 后继节点 [节点六],要 关联

[节点六]前驱节点 [节点十四]后继节点 Null,则无需 关联

线索化问题发现

那么有没有发现,如果这样安顿关联就会发现 [节点一] 的一些 问题

1.前驱节点 应该是 [节点十],但[节点一] 并没有指向[节点十]

2.后继节点 应该是 [节点十四],但[节点一] 并没有指向[节点十四]

left、right 属性的状况阐明

线索化二叉树 后,Node 节点的属性left、right 会有以下状况

①:[left 指向的是左子树,也可能是指向的前驱节点 ],比方[节点一] 的 left 指向的 左子树 , 而[节点十] 的 left 指向的就是 前驱节点.

②:[right 指向的是右子树,也可能是指向后继节点 ],比方[节点一]right 指向的是 右子树 ,而[节点十] 的 right 指向的是 后继节点.

所以咱们须要加多 [标记 Type] 代表以后是指向 子树、还是节点

利用示例思路剖析

同时咱们进行中序线索化,当初各位小伙伴还记得 二叉树遍历 形式吗?

  • 前序是先输入父节点,再遍历左子树和右子树
  • 中序是先遍历左子树,再输入父节点,最初遍历右子树
  • 后序是先遍历左子树,再遍历右子树,最初输入父节点

所以中序思路步骤分:先线索化左子树、再线索化以后节点、最初线索化右子树

当咱们线索化 [某个节点 node] 时,其实须要一个 [前驱节点 pre] 形成关系关联,这样才有可能实现线索化。如图所示

当初咱们来剖析 [ 线索化前驱节点的思路]:队列的[节点八]

每解决完后,记得让以后 node 成为下一个节点的前驱节点:pre = node

当初咱们来剖析 [ 线索化后继节点的思路]:队列的[节点八]

当初咱们依据思路定义节点 HeroNode 信息

// 创立 HerNode
class HeroNode {

    private int no;
    private String name;

    private HeroNode left;  // 默认 null 左节点
    private HeroNode right; // 默认 null 右节点

    /**
     * 阐明
     * 1. leftType == 0 示意指向的是左子树
     * 2. leftType == 1 示意指向的是前驱节点
     *
     * 3.rigthType == 0 示意指向的是右子树
     * 4.rightType == 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 HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {return no;}

    public void setNo(int no) {this.no = no;}

    public String getName() {return name;}

    public void setName(String name) {this.name = name;}

    public HeroNode getLeft() {return left;}

    public void setLeft(HeroNode left) {this.left = left;}

    public HeroNode getRight() {return right;}

    public void setRight(HeroNode right) {this.right = right;}

    @Override
    public String toString() {return "HeroNode [no =" + no +", name =" + name +"]";
    }
}

创立一颗线索化二叉树 ThreadedBinaryTree 信息

class ThreadedBinaryTree{

    private HeroNode root;

    // 为了实现线索化,须要创立要给指向以后节点的前驱节点的指针
    // 在进行递归线索化时,pre 总是保留前一个节点
    private HeroNode prenode = null;

    public void setRoot(HeroNode root) {this.root = root;}

    public void setPrenode(HeroNode prenode) {this.prenode = prenode;}

    public void threadedNodes(){this.threadedNodes(root);
    }

    // 编写对二叉树进行中序线索化办法
    private void threadedNodes(HeroNode node){

        // 如果 node == null 则不进行线索化

        if(node == null){return;}

        // 中序遍历的法则:先遍历左子树,再输入父节点,再遍历右子树

        //(一)先线索化左子树
        threadedNodes(node.getLeft());
        //(二)线索化以后节点
        // 比如说中序队列:{8,3,10,1,14,6}
        // 先解决[节点 8] 那么就要解决节点的前驱节点,判断是否左子树
        if(node.getLeft() == null ){
            // 以后节点左指针指向前驱节点
            node.setLeft(prenode);
            node.setLeftType(1);//1 示意指向的是前驱节点  0 示意指向的是左子树
        }
        // 解决后续节点
        if(prenode!=null && prenode.getRight() == null){
            // 让前驱节点的右指针指向以后节点
            prenode.setRight(node);
            // 批改前驱的右指针类型
            prenode.setRightType(1);
        }
        // 解决完每个节点的操作后,让以后 node 是下一个节点的前驱节点
        prenode = node;

        //(三)再线索化右子树
        threadedNodes(node.getRight());
    }
}

当初让咱们测试看看线索化后 [节点十] 是否已产生扭转,看看是否胜利

public class ThreadedBinaryTreeDemo {public static void main(String[] args) {

        // 创立节点
        HeroNode root = new HeroNode(1,"tom");
        HeroNode node2 = new HeroNode(3,"jack");
        HeroNode node3 = new HeroNode(6,"smith");
        HeroNode node4 = new HeroNode(8,"mary");
        HeroNode node5 = new HeroNode(10,"king");
        HeroNode node6 = new HeroNode(14,"dim");

        // 手动创立二叉树依赖
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        // 创立二叉树
        ThreadedBinaryTree tree =new ThreadedBinaryTree();
        tree.setRoot(root);
        tree.threadedNodes();

        // 测试节点十的前驱代码与后续节点是否扭转
        HeroNode leftNode = node5.getLeft();
        HeroNode rigthNode = node5.getRight();
        System.out.println("[节点十]的前驱节点是" + leftNode);
        System.out.println("[节点十]的后续节点是" + rigthNode);

    }

}

运行后果如下:[节点十]的前驱节点是 HeroNode [no =3, name =jack]
[节点十]的后续节点是 HeroNode [no =1, name =tom]

三、遍历中序线索化二叉树

因为线索化后,各个结点指向有变动,因而原来的遍历形式不能应用。

这时须要应用新的形式遍历线索化二叉树,各个节点能够通过线型形式遍历。

因而无需应用递归形式,这样也进步了遍历的效率,遍历的秩序该当和中序遍历保持一致。

也就说遍历中序线索化二叉树输入的后果也要是:{8,3,10,1,14,6}

class ThreadedBinaryTree{

    // 遍历线索化二叉树的办法
    public void threadedList(){
        // 定义一个变量,存储以后遍历的结点,从 root 开始
        HeroNode node = root;
        while(node != null) {
            // 循环的找到 leftType == 1 的结点,第一个找到就是 8 结点
            // 前面随着遍历而变动, 因为当 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 class ThreadedBinaryTreeDemo {public static void main(String[] args) {
        // 省略..
        tree.threadedList();}

}

运行后果如下:HeroNode [no =8, name =mary]
HeroNode [no =3, name =jack]
HeroNode [no =10, name =king]
HeroNode [no =1, name =tom]
HeroNode [no =14, name =dim]
HeroNode [no =6, name =smith]

咱们就要先找到[节点八],它的特点是leftType = 1

找到后输入这个节点

如果以后节点的右指针也是后继节点则替换成该后也输入

若以后节点的右指针不满足后继节点则替换往下走

退出移动版