class ThreadedBinaryTree{
    private Node root;
    private Node pre=null;

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

    public void threadNodes(){
        this.threadedNodes(root);
    }
    //中序線索化
    public void threadedNodes(Node node){
        if(node==null)
            return;
        threadedNodes(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;
        threadedNodes(node.getRight());
    }

    //前序線索化
    public void threadedNodesPre(Node node){
        if(node==null)
            return;
        if(node.getLeft()==null)
        {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;
        if(node.getLeftType()==0)
            threadedNodes(node.getLeft());
        if(node.getRightType()==0)
            threadedNodes(node.getRight());
    }

    //后序線索化
    public void threadedNodesPost(Node node){
        if(node==null)
            return;
        if(node.getLeftType()==0)
            threadedNodes(node.getLeft());
        if(node.getRightType()==0)
            threadedNodes(node.getRight());
        if(node.getLeft()==null)
        {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;
    }
}

Node節(jié)點類添加了：

    private int leftType;//0表示指向左子樹户辞，1表示指向前驅(qū)節(jié)點
    private int rightType;//0表示指向右子樹，1表示指向后繼節(jié)點

    public int getLeftType() {
        return leftType;
    }

    public int getRightType() {
        return rightType;
    }

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

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

遍歷中序線索化二叉樹

  //遍歷中序線索化二叉樹
    public void threadedList(){
        Node node=root;
        while(node!=null){
            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();
        }
    }

優(yōu)勢

(1)利用線索二叉樹進(jìn)行中序遍歷時癞谒，不必采用堆棧處理底燎，速度較一般二叉樹的遍歷速度快，且節(jié)約存儲空間

(2)任意一個結(jié)點都能直接找到它的前驅(qū)和后繼結(jié)點

不足

(1)結(jié)點的插入和刪除麻煩扯俱，且速度也較慢

(2)線索子樹不能共用

https://baike.baidu.com/item/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91/10810037?fr=aladdin