线索二叉树

作者: 乙腾 | 来源:发表于2020-11-07 22:23 被阅读0次

线索二叉树操作
二叉树—线索二叉树
javascript线索化二叉树
数据结构线索二叉树
数据结构与算法分析四树(续)
理解线索二叉树
数据结构题目56：线索二叉树的更新
数据结构与算法13-线索二叉树
线索化二叉树的实现
数据结构与算法[线索化二叉树]

Overview

将二叉树中没有子节点的节点称为空指针域，利用二叉树的空指针域，按照前中后某种遍历方式存放对应的前驱节点，后驱节点（这种附加指针称为“线索”）。二叉树的空指针域存储对应前后驱节点的二叉树叫做线索二叉树。（他的空指针域存放着他的前一个后一个节点的信息）。

image.png

特点：

在线索二叉树中，left可以指向左子树，也可能是指向前驱节点。（因为只有空指针域才能线索化，所以lefth或者right只能同时存在一种情况，要么指向左右树，要么指向前后驱节点）。

right指向右子树，也可能指向后驱节点。

空指针域的计算公式

image.png

code

ThreadBinaryTree

package com.pl.arithmetic.binaryTree.threadBinaryTree;

import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * <p>
 *
 * @Description: 中序线索二叉树
 * </p>
 * @ClassName ThreadBinaryTree
 * @Author pl
 * @Date 2020/11/7
 * @Version V1.0.0
 */
@Data
@NoArgsConstructor
public class ThreadBinaryTree {

    private ThreadHeroNode root;
    //前驱节点临时变量 中序遍历第一个节点的前驱节点必为空
    private ThreadHeroNode preTempVal = null;

    public ThreadBinaryTree(ThreadHeroNode root) {
        this.root = root;
    }

    //重载一把threadedNodes方法
    public void buildThreadedNodes() {
        this.buildThreadedNodes(root);
    }

    /**
     * 按照中序遍历 线索化二叉树
     * 因为二叉树节点遍历都是单向的，无法知道其前后节点，所以通过过程变量存储当前节点，作为后一个节点的前驱节点，遍历到后续节点时候再为前驱节点赋值后驱节点
     * 
     * @param node
     * @return void
     * @exception 
     * @author silenter
     * @date 2020/11/7 22:13
    */
    public void buildThreadedNodes(ThreadHeroNode node){
        if (node == null){
            System.out.println("不能线索化空节点");
            return;
        }
        //中序遍历线索二叉树 按照中序遍历顺序来构建线索二叉树 先线索化左节点 在线索化当前节点 后线索化右节点
        //@1 线索化左子树
        buildThreadedNodes(node.leftNode);
        //因为中序遍历是单向的，当前节点是拿不到他的后一顺序的节点，所以用临时变量存储当前节点作为遍历顺序中，下一个节点的前驱节点。
        //当前节点如果是能够线索化的节点，那么只能赋值他的前驱节点，线索化其后驱节点，只能将当前节点存储在前驱临时变量中，让后一个节点为他补齐他的后驱节点。
        //@2 线索化当前节点
        if (node.leftNode == null){
            node.leftNode = preTempVal;
            node.leftTreadType=1;
        }
        if (preTempVal!=null && preTempVal.rightNode == null){
            preTempVal.rightNode = node;
            preTempVal.rightTreadType = 1;
        }
        //当前节点左右节点线索化逻辑执行之后将当前节点存储到临时变量中，作为后一个节点的前驱节点。
        preTempVal = node;
        //线索化右子树
        buildThreadedNodes(node.rightNode);
    }


}

ThreadHeroNode

package com.pl.arithmetic.binaryTree.threadBinaryTree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Objects;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName ThreadHeroNode
 * @Author pl
 * @Date 2020/11/7
 * @Version V1.0.0
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class ThreadHeroNode {
     int value;
     String name;
     ThreadHeroNode leftNode;
     ThreadHeroNode rightNode;

    //是否线索化标记
    //1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    //2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
     int leftTreadType;
     int rightTreadType;

    public ThreadHeroNode(int value, String name) {
        this.value = value;
        this.name = name;
    }


    @Override
    public String toString() {
        return "ThreadHeroNode{" +
                "value=" + value +
                ", name='" + name + '\'' +
                '}';
    }
}

TestDemo

package com.pl.arithmetic.binaryTree.threadBinaryTree;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName TestDemo
 * @Author pl
 * @Date 2020/10/20
 * @Version V1.0.0
 */
public class TestDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        ThreadHeroNode root = new ThreadHeroNode(1, "tom");
        ThreadHeroNode node2 = new ThreadHeroNode(3, "jack");
        ThreadHeroNode node3 = new ThreadHeroNode(6, "smith");
        ThreadHeroNode node4 = new ThreadHeroNode(8, "mary");
        ThreadHeroNode node5 = new ThreadHeroNode(10, "king");
        ThreadHeroNode node6 = new ThreadHeroNode(14, "dim");

        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);

        //测试中序线索化
        ThreadBinaryTree threadedBinaryTree = new ThreadBinaryTree(root);
        threadedBinaryTree.buildThreadedNodes();

        //测试: 以10号节点测试
        ThreadHeroNode leftNode = node5.getLeftNode();
        ThreadHeroNode rightNode = node5.getRightNode();

        System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1
    }
}

image.png

遍历中序线索化二叉树

image.png

code
ThreadBinaryTree

package com.pl.arithmetic.binaryTree.threadBinaryTree;

import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * <p>
 *
 * @Description: 中序线索二叉树
 * </p>
 * @ClassName ThreadBinaryTree
 * @Author pl
 * @Date 2020/11/7
 * @Version V1.0.0
 */
@Data
@NoArgsConstructor
public class ThreadBinaryTree {

    private ThreadHeroNode root;
    //前驱节点临时变量 中序遍历第一个节点的前驱节点必为空
    private ThreadHeroNode preTempVal = null;

    public ThreadBinaryTree(ThreadHeroNode root) {
        this.root = root;
    }

    //重载一把threadedNodes方法
    public void buildThreadedNodes() {
        this.buildThreadedNodes(root);
    }

    /**
     * 按照中序遍历 线索化二叉树
     *
     * @param node
     * @return void
     * @exception
     * @author silenter
     * @date 2020/11/7 22:13
    */
    public void buildThreadedNodes(ThreadHeroNode node){
        if (node == null){
            System.out.println("不能线索化空节点");
            return;
        }
        //中序遍历线索二叉树 按照中序遍历顺序来构建线索二叉树 先线索化左节点 在线索化当前节点 后线索化右节点
        //@1 线索化左子树
        buildThreadedNodes(node.leftNode);
        //因为中序遍历是单向的，当前节点是拿不到他的后一顺序的节点，所以用临时变量存储当前节点作为遍历顺序中，下一个节点的前驱节点。
        //当前节点如果是能够线索化的节点，那么只能赋值他的前驱节点，线索化其后驱节点，只能将当前节点存储在前驱临时变量中，让后一个节点为他补齐他的后驱节点。
        //@2 线索化当前节点
        if (node.leftNode == null){
            node.leftNode = preTempVal;
            node.leftTreadType=1;
        }
        if (preTempVal!=null && preTempVal.rightNode == null){
            preTempVal.rightNode = node;
            preTempVal.rightTreadType = 1;
        }
        //当前节点左右节点线索化逻辑执行之后将当前节点存储到临时变量中，作为后一个节点的前驱节点。
        preTempVal = node;
        //线索化右子树
        buildThreadedNodes(node.rightNode);
    }

    /**
     * 遍历中序线索化二叉树，输出顺序和原有中序遍历顺序相同
     *
     * @param
     * @return void
     * @exception
     * @author silenter
     * @date 2020/11/9 20:51
    */
    public void infixOrder(){
        ThreadHeroNode tempNode = root;
        while (tempNode!=null){
            //查找起始节点，起始线索化节点
            while (tempNode.leftTreadType == 0){
                tempNode = tempNode.leftNode;
            }
            System.out.println(tempNode);
            //如果右节点一直都是线索化节点，则一直输出
            while (tempNode.rightTreadType ==1){
                tempNode = tempNode.rightNode;
                System.out.println(tempNode);
            }
            //如果当前节点不是线索化节点，则将其右节点替换当前节点
            tempNode = tempNode.rightNode;
        }
    }
}

TestDemo

package com.pl.arithmetic.binaryTree.threadBinaryTree;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName TestDemo
 * @Author pl
 * @Date 2020/10/20
 * @Version V1.0.0
 */
public class TestDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        ThreadHeroNode root = new ThreadHeroNode(1, "tom");
        ThreadHeroNode node2 = new ThreadHeroNode(3, "jack");
        ThreadHeroNode node3 = new ThreadHeroNode(6, "smith");
        ThreadHeroNode node4 = new ThreadHeroNode(8, "mary");
        ThreadHeroNode node5 = new ThreadHeroNode(10, "king");
        ThreadHeroNode node6 = new ThreadHeroNode(14, "dim");

        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);

        //测试中序线索化
        ThreadBinaryTree threadedBinaryTree = new ThreadBinaryTree(root);
        threadedBinaryTree.buildThreadedNodes();

        //测试: 以10号节点测试
        ThreadHeroNode leftNode = node5.getLeftNode();
        ThreadHeroNode rightNode = node5.getRightNode();

        System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1

        threadedBinaryTree.infixOrder();
    }
}

输出

image.png