线索化二叉树

介绍

二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。二叉树作为存储结构时，一个节点只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱或后继信息。

也就是说，线索二叉树就是充分利用二叉树节点中的空指针，让它们分别指向本节点的前驱或者后继。既充分利用了资源，又方便我们遍历这颗二叉树。

概念

n个节点的二叉树中含有n+1个空指针域。利用二叉树中的空指针域 来存放在某种遍历次序下的前驱和后继 ，这种指针叫“线索”。这种加上了线索的二叉树称为线索二叉树（Threaded BinaryTree）。根据遍历次序的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

java代码

import jdk.jshell.spi.SPIResolutionException;

/**
 *
 * 线索化二叉树
 */


public class ThreadBinaryTree {

    private static Node root;
    private static Node pre = new Node(null);

    public static void main(String[] args) {
        ThreadBinaryTree tree = new ThreadBinaryTree();
        String[] array = {"a","b","c","d","sidf","ijnsdf"};
        root = tree.createTree(array,0);
        //tree.inTraverse(root);
        tree.createThread(root);
        tree.inThreadList(root);
    }

    /**
     * 构建二叉树,利用递归,但是是一颗完全二叉树
     * @param array 所有节点的信息
     * @param index 当前节点下标
     * @return
     */
    public Node createTree(String[] array, Integer index){
        if (array.equals(null) || index >= array.length || index < 0){
            return null;
        }
        Node node = new Node(array[index]);
        node.setLeftChild(createTree(array,index*2+1));
        node.setRightChild(createTree(array,index*2+2));
        return node;
    }

    /**
     *
     * 中序普通遍历 ， 递归实现
     * @param node 当前节点
     */
    public void inTraverse(Node node){
        if (this.root == null){
            System.out.println("binarytree is null");
            return;
        }
        if (node == null) {
            return;
        }
        inTraverse(node.getLeftChild());
        System.out.println(node.getContent());
        inTraverse(node.getRightChild());
    }

    /**
     * 线索化二叉树，将关系链接起来
     * @param node
     */
    public void createThread(Node node){
        if (this.root == null){
            System.out.println("binarytree is null");
            return;
        }
        if (node == null) {
            return;
        }
        createThread(node.getLeftChild());
        if (null == node.getLeftChild()){
            node.setLeftChild(pre);
            node.setLeftType(1);
        }
        if (null == pre.getRightChild() && null != pre){
            pre.setRightChild(node);
            pre.setRightType(1);
        }
        pre = node;

        createThread(node.getRightChild());
    }

    /**
     *
     * 中序遍历线索化二叉树，根据后继节点找
     * @param node
     */
    public void inThreadList(Node node) {
        //1、找中序遍历方式开始的节点
        if (node == null){
            return;
        }
        while(node.getLeftChild() != null && node.getLeftType()==0) {
            node = node.getLeftChild();
        }

        while(node != null) {
            System.out.println(node.getContent());

            //如果右指针是线索
            if(node.getRightType() == 1) {
                node = node.getRightChild();

            } else {    //如果右指针不是线索，找到右子树开始的节点
                node = node.getRightChild();
                while(node != null && node.getLeftType()==0) {
                    node = node.getLeftChild();
                }
            }
        }
    }

}

/**
 *
 * 二叉树的节点
 */
class Node{

    private Node leftChild = null;
    private Node rightChild = null;

    private Integer leftType = 0;
    private Integer rightType = 0;

    private String content = null;

    public Node(String content){
        this.content = content;
    }

    public void setChild(Node leftChild, Node rightChild){
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    public Integer getLeftType() {
        return leftType;
    }

    public void setLeftType(Integer leftType) {
        this.leftType = leftType;
    }

    public Integer getRightType() {
        return rightType;
    }

    public void setRightType(Integer rightType) {
        this.rightType = rightType;
    }

    public String getContent() {
        return content;
    }
}