[[388829]]

先看一個問題

將數(shù)列{1,3,6,8,10,14}構(gòu)建成一顆二叉樹.n+1=7,如下圖所示

問題分析：

1. 當(dāng)我們對上面的二叉樹進(jìn)行中序遍歷時，數(shù)列為{8,3,10,1,14,6}
2. 但是6，8，10，14這幾個節(jié)點的左右指針，并沒有完全的利用上。
3. 如果我們希望充分的利用各個節(jié)點的左右指針，讓各個節(jié)點指向自己的前后節(jié)點怎么辦?
4. 解決方案-線索二叉樹

線索二叉樹基本介紹

1. n 個節(jié)點的二叉鏈表中含有n+1【公式 2n-(n-1)=n+1】個空指針域。利用二叉鏈表中的空指針域，存放該節(jié)點在某種遍歷次序下的前驅(qū)和后繼點的指針(這種附加的指針稱為線索)。
2. 這種加了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據(jù)線索的性質(zhì)不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹、后序線索二叉樹三種。
3. 一個節(jié)點的前一個節(jié)點，稱為前驅(qū)節(jié)點。
4. 一個節(jié)點的后一個節(jié)點，稱為后繼節(jié)點。

中序線索二叉樹圖解

中序遍歷的結(jié)果{8,3,10,1,14,6}

說明：當(dāng)線索化二叉樹后，Node節(jié)點的屬性left和right,有如下情況：

1. left指向的值左子樹，也可能是指向的前驅(qū)節(jié)點，比如①節(jié)點left指向的左子樹，而⑩節(jié)點的left指向的就是前驅(qū)節(jié)點。
2. right指向的右子樹，也可能是指向后繼節(jié)點，比如①節(jié)點right指向的是右子樹，而⑩節(jié)點的right指向的是后繼節(jié)點。

代碼案例

package com.xie.tree.threadedbinarytree; 
 
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 threadedBinaryTree = new ThreadedBinaryTree(); 
        threadedBinaryTree.setRoot(root); 
        threadedBinaryTree.threadedNodes(); 
 
        //測試：以10號節(jié)點測試 
        HeroNode left = node5.getLeft(); 
        System.out.println("10號節(jié)點的前驅(qū)節(jié)點是：" + left); 
        HeroNode right = node5.getRight(); 
        System.out.println("10號節(jié)點的后繼節(jié)點是：" + right); 
 
        System.out.println("使用線索化的方式遍歷 線索二叉樹"); 
        threadedBinaryTree.threadedBinaryTreeList(); 
 
        /** 
         * 10號節(jié)點的前驅(qū)節(jié)點是：HeroNode{no=3, name=jack} 
         * 10號節(jié)點的后繼節(jié)點是：HeroNode{no=1, name=tom} 
         * 使用線索化的方式遍歷 線索二叉樹 
         * 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} 
         */ 
 
    } 
} 
 
//實現(xiàn)了線索化功能的二叉樹 
class ThreadedBinaryTree { 
    private HeroNode root; 
    //為了實現(xiàn)線索化，需要創(chuàng)建一個指向當(dāng)前節(jié)點的前驅(qū)節(jié)點的指針 
    //在遞歸進(jìn)行線索化時，pre總是保留前一個節(jié)點 
    private HeroNode pre; 
 
    public void setRoot(HeroNode root) { 
        this.root = root; 
    } 
 
    /** 
     * 遍歷線索化二叉樹的方法。 
     */ 
    public void threadedBinaryTreeList() { 
        //定義一個變量，存儲當(dāng)前遍歷的節(jié)點，從root開始 
        HeroNode node = root; 
        while (node != null) { 
            //循環(huán)找到leftType==1的節(jié)點,第一個找到就是8節(jié)點 
            //后面隨著遍歷而變化，因為當(dāng)leftType==1時，說明該節(jié)點是按照線索化處理后的有效節(jié)點 
            while (node.getLeftType() == 0) { 
                node = node.getLeft(); 
            } 
            //打印當(dāng)前節(jié)點 
            System.out.println(node); 
            //如果當(dāng)前節(jié)點的右指針指向的是后繼節(jié)點，就一直輸出 
            while (node.getRightType() == 1) { 
                //獲取到當(dāng)前節(jié)點的后繼節(jié)點 
                node = node.getRight(); 
                System.out.println(node); 
            } 
            //替換這個遍歷的節(jié)點 
            node = node.getRight(); 
        } 
    } 
 
    /** 
     * 重載threadedNodes方法 
     */ 
    public void threadedNodes() { 
        threadedNodes(root); 
    } 
 
    /** 
     * 編寫對二叉樹進(jìn)行線索化的方法 
     * 
     * @param node 當(dāng)前需要線索化的節(jié)點 
     */ 
    public void threadedNodes(HeroNode node) { 
        if (node == null) { 
            return; 
        } 
 
        //先線索化左子樹 
        threadedNodes(node.getLeft()); 
        //線索化當(dāng)前節(jié)點【有難度】 
 
        //處理當(dāng)前節(jié)點的前驅(qū)節(jié)點 
        //以8節(jié)點來理解，8節(jié)點.left=null 
        if (node.getLeft() == null) { 
            //讓當(dāng)前節(jié)點的左指針指向前驅(qū)節(jié)點 
            node.setLeft(pre); 
            //修改當(dāng)前節(jié)點的左指針類型 
            node.setLeftType(1); 
        } 
 
        //處理后繼節(jié)點 
        if (pre != null && pre.getRight() == null) { 
            //讓前驅(qū)節(jié)點的右指針指向當(dāng)前節(jié)點 
            pre.setRight(node); 
            //修改前驅(qū)節(jié)點的右指針類型 
            pre.setRightType(1); 
        } 
        //每處理一個節(jié)點后，讓當(dāng)前節(jié)點是下一個節(jié)點的前驅(qū)節(jié)點 
        pre = node; 
 
        //再線索化右子樹 
        threadedNodes(node.getRight()); 
    } 
 
} 
 
//創(chuàng)建HeroNode節(jié)點 
class HeroNode { 
    static int preCount = 0; 
    static int infoxCount = 0; 
    static int postCount = 0; 
 
    private int no; 
    private String name; 
    private HeroNode left; 
    private HeroNode right; 
 
    //0 表示指向的是左子樹，1 表示指向的是前驅(qū)節(jié)點 
    private int leftType; 
    //0 表示指向右子樹，1 表示指向的是后繼節(jié)點 
    private int 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; 
    } 
 
    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; 
    } 
 
    @Override 
    public String toString() { 
        return "HeroNode{" + 
                "no=" + no + 
                ", name=" + name + 
                '}'; 
    } 
 
    //前序遍歷 
    public void preOrder() { 
        System.out.println(this); 
        //遞歸向左子樹前序遍歷 
        if (this.left != null) { 
            this.left.preOrder(); 
        } 
 
        //遞歸向右子樹前序遍歷 
        if (this.right != null) { 
            this.right.preOrder(); 
        } 
    } 
 
    //中序遍歷 
    public void infixOrder() { 
        //遞歸向左子樹中序遍歷 
        if (this.left != null) { 
            this.left.infixOrder(); 
        } 
        System.out.println(this); 
        //遞歸向右子樹中序遍歷 
        if (this.right != null) { 
            this.right.infixOrder(); 
        } 
    } 
 
    //后序遍歷 
    public void postOrder() { 
        //遞歸向左子樹后序遍歷 
        if (this.left != null) { 
            this.left.postOrder(); 
        } 
        //遞歸向右子樹后序遍歷 
        if (this.right != null) { 
            this.right.postOrder(); 
        } 
        System.out.println(this); 
    } 
 
    //遞歸刪除節(jié)點 
    //1.如果刪除的節(jié)點是葉子節(jié)點，則刪除該節(jié)點。 
    //2.如果刪除的節(jié)點是非葉子節(jié)點，則刪除該樹。 
    public void delNo(int no) { 
        /** 
         * 1.因為我們的二叉樹是單向的，所以我們是判斷當(dāng)前節(jié)點的子節(jié)點是否是需要刪除的節(jié)點，而不能去判斷當(dāng)前節(jié)點是否是需要刪除的節(jié)點。 
         * 2.如果當(dāng)前節(jié)點的左子節(jié)點不為空，并且左子節(jié)點就是需要刪除的節(jié)點，就將this.left = null；并且返回（結(jié)束遞歸）。 
         * 3.如果當(dāng)前節(jié)點的右子節(jié)點不為空，并且右子節(jié)點就是需要刪除的節(jié)點，將將this.right = null;并且返回（結(jié)束遞歸）。 
         * 4.如果第2步和第3步?jīng)]有刪除節(jié)點，那么就要向左子樹進(jìn)行遞歸刪除。 
         * 5.如果第4步也沒有刪除節(jié)點，則應(yīng)當(dāng)向右子樹進(jìn)行遞歸刪除。 
         */ 
        if (this.left != null && this.left.no == no) { 
            this.left = null; 
            return; 
        } 
 
        if (this.right != null && this.right.no == no) { 
            this.right = null; 
            return; 
        } 
 
        if (this.left != null) { 
            this.left.delNo(no); 
        } 
 
        if (this.right != null) { 
            this.right.delNo(no); 
        } 
 
    } 
 
    //前序遍歷查找 
    public HeroNode preOrderSearch(int no) { 
 
        HeroNode res = null; 
 
        preCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實際的比較 
        //若果找到，就返回 
        if (this.no == no) { 
            return this; 
        } 
        //沒有找到，向左子樹遞歸進(jìn)行前序查找 
        if (this.left != null) { 
            res = this.left.preOrderSearch(no); 
        } 
        //如果res ！= null 就直接返回 
        if (res != null) { 
            return res; 
        } 
        //如果左子樹沒有找打，向右子樹進(jìn)行前序查找 
        if (this.right != null) { 
            res = this.right.preOrderSearch(no); 
        } 
        //如果找到就返回 
        if (res != null) { 
            return res; 
        } 
        return res; 
    } 
 
    //中序遍歷查找 
    public HeroNode infixOrderSearch(int no) { 
 
        HeroNode res = null; 
        if (this.left != null) { 
            res = this.left.infixOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
        infoxCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實際的比較 
        if (this.no == no) { 
            return this; 
        } 
        if (this.right != null) { 
            res = this.right.infixOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
        return res; 
    } 
 
    //后序遍歷查找 
    public HeroNode postOrderSearch(int no) { 
 
        HeroNode res = null; 
        if (this.left != null) { 
            res = this.left.postOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
 
        if (this.right != null) { 
            res = this.right.postOrderSearch(no); 
        } 
        if (res != null) { 
            return res; 
        } 
        postCount++;//這里必須放在this.no == no 判斷之前，才進(jìn)行實際的比較 
        if (this.no == no) { 
            return this; 
        } 
        return res; 
    } 
} 

 【編輯推薦】