线索二叉树概念

• 对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
• 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

线索二叉树的优缺点

优点：

• 利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。
• 任意一个结点都能直接找到它的前驱和后继结点。

缺点：

• 结点的插入和删除麻烦，且速度也较慢。

代码实现

这里我只实现了中序线索二叉树的构建和遍历

/**
 * 结点类
 */
public class Node {
    private int id;
    private String name;
    /*左节点*/
    private Node left;
    /*右节点*/
    private Node right;
    /*如果leftType == 0 表示指向的是左子树,如果leftType == 1 则表示指向的是前序结点*/
    private int leftType;
    /*如果rightType == 0 表示指向的是右子树,如果rightType == 1 则表示指向的是后继结点*/
    private int rightType;

    /*构造方法*/
    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

	getter and setter 方法

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

public class ThreadedBinaryTree {
    /*根结点*/
    private Node root;
    /*当前结点的前驱结点*/
    private Node pre;

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

    /**
     * 对二叉树进行中序线索化
     * @param node
     */
    public void threadedNode(Node node){
        if (node == null) {
            /* 如果结点为空就不能线索化*/
            return;
        }
        /*先线索化左子树*/
        threadedNode(node.getLeft());

        /*线索化当前结点*/
        if (node.getLeft() == null) {
            /*如果当前结点的左子结点为空 就让当前结点的左子结点指向前驱结点*/
            node.setLeft(pre);
            /*修改左子结点的类型用于区分是左子树还是前驱结点*/
            node.setLeftType(1);
        }
        /*处理后继结点*/
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        /*使当前结点是下一个结点的前驱结点*/
        pre = node;
        /*线索化右子树*/
        threadedNode(node.getRight());
    }

    /**
     * 遍历线索化后的二叉树
     */
    public void show(){
        /*存储当前遍历的结点*/
        Node temp = root;
        while(temp != null){
            /*循环找到leftType == 1 的结点 就是线索化后的结点*/
            while(temp.getLeftType() == 0){
                temp = temp.getLeft();
            }
            System.out.println(temp);
            /*如果当前解结点指向的是后继结点就输出后继结点*/
            while(temp.getRightType() == 1){
                temp = temp.getRight();
                System.out.println(temp);
            }
            temp = temp.getRight();
        }
    }
}

测试类

public class Test {
    public static void main(String[] args) {
        Node root = new Node(1, "张三");
        Node node2 = new Node(3, "李四");
        Node node3 = new Node(6, "王五");
        Node node4 = new Node(8, "赵六");
        Node node5 = new Node(10, "田七");
        Node node6 = new Node(14, "陈八");

        /*手动创建二叉树*/
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.setRoot(root);
        tree.threadedNode(root);

        Node pre = node5.getLeft();
        Node next = node5.getRight();
        System.out.println("10号结点的前驱结是:id="+pre.getId()+",name="+pre.getName());
        System.out.println("10号结点的后继是:id="+next.getId()+",name="+next.getName());

        System.out.println("使用线索化的方式遍历线索化二叉树");
        tree.show();
    }
}

运行结果

10号结点的前驱结点是:id=3,name=李四
10号结点的后继结点是:id=1,name=张三
使用线索化的方式遍历线索化二叉树
[id=8, name=赵六]
[id=3, name=李四]
[id=10, name=田七]
[id=1, name=张三]
[id=14, name=陈八]
[id=6, name=王五]

Process finished with exit code 0