Java資料結構之線索化二元樹的實現

2022-05-18 16:02:09

1.線索化二元樹的介紹

將數列 {1, 3, 6, 8, 10, 14 } 構建成一顆二元樹.

問題分析:

1.當我們對上面的二元樹進行中序遍歷時，數列為 {8, 3, 10, 1, 6, 14 }

2.但是 6, 8, 10, 14 這幾個節點的左右指標，並沒有完全的利用上.

3.如果我們希望充分的利用各個節點的左右指標，讓各個節點可以指向自己的前後節點,怎麼辦?

4.解決方案-線索二元樹

概念：當用二元連結串列作為二元樹的儲存結構時，可以很方便的找到某個結點的左右孩子；但一般情況下，無法直接找到該結點在某種遍歷序列中的前驅和後繼結點。所以使用線索化，利用二元樹結構連結串列的空指標域進行線索化。

2.線索化二元樹的基本特點

n 個結點的二元連結串列中含有 n+1 【公式 2n-(n-1)=n+1】個空指標域。利用二元連結串列中的空指標域，存放指向該結點在某種遍歷次序下的前驅和後繼結點的指標（這種附加的指標稱為"線索"）

這種加上了線索的二元連結串列稱為線索連結串列，相應的二元樹稱為線索二元樹(Threaded BinaryTree)。根據線索性質的不同，線索二元樹可分為前序線索二元樹、中序線索二元樹和後序線索二元樹三種

3.線索化二元樹的應用案例

中序線索化二元樹並遍歷

應用案例說明：將下面的二元樹，進行中序線索二元樹。中序遍歷的數列為 {8, 3, 10, 1, 14, 6}

思路分析

中序遍歷的結果：{8, 3, 10, 1, 14, 6}

那麼線索化之後的二元樹的左右指標如上圖↑

說明: 當線索化二元樹後，Node 節點的屬性 left 和 right ，有如下情況:

left 指向的是左子樹，也可能是指向的前驅節點. 比如 ① 節點 left 指向的左子樹, 而 ⑩ 節點的 left 指向的就是前驅節點.
right 指向的是右子樹，也可能是指向後繼節點，比如 ① 節點 right 指向的是右子樹，而⑩ 節點的 right 指向的是後繼節點.

因此要改變原來的二元樹的結點結構

package com.studySelf.tree.threadedBinaryTree;

/**
 * @author wang
 * @version 1.0
 * @packageName com.studySelf.tree.tree01
 * @className Node
 * @date 2022/4/19 20:15
 * @Description Node結點
 */
public class Node {
    //唯一編號
    private int num;
    //結點的值
    private String name;
    //左結點
    private Node left;
    //右節點
    private Node right;

    //這個屬性用來控制線索二元樹的結點的指向，0代表指向左結點，1代表指向前趨結點
    private int leftType;
    //這個屬性用來控制線索二元樹的結點的指向，0代表指向右結點，1代表指向後繼結點
    private int rightType;


    //構造方法

    public Node(int num, String name) {
        this.num = num;
        this.name = name;
    }

    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;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name +
                '}';
    }

    /**
     * 前序遍歷
     */
    public void preSelect() {
        //首先輸出根結點
        System.out.println(this);
        //其次判斷是否有左結點
        if (this.left != null) {
            //沒有左結點，就遞迴呼叫本方法輸出該結點。
            this.left.preSelect();
        }
        if (this.right != null) {
            this.right.preSelect();
        }
    }

    /**
     * 中序遍歷
     */
    public void infixSelect() {
        //首先判斷左結點
        if (this.left != null) {
            //如果左結點不為空，遞迴向左子樹呼叫
            this.left.infixSelect();
        }
        //當左結點為空，再輸出根結點。當他本身就是最後一個左結點的時候，會直接輸出，且沒有右節點
        System.out.println(this);
        if (this.right != null) {
            //右節點同樣如此，遞迴呼叫。直到沒有結點為止。
            this.right.infixSelect();
        }
    }

    /**
     * 設二元樹有三個結點，根結點，左結點，右節點。
     * 後序遍歷,解釋，當一個二元樹的左結點不為空，那麼他會進入下一個遞迴呼叫自己的後序遍歷方法
     * 此時，根結點就是左結點，這時判斷左結點，右節點均為空，就會輸出左結點
     * 回退到根結點為this的時候，左結點已經判斷完畢，接下來是右節點，右節點不為空，進入後續遍歷遞迴，
     * 此時的this就是右節點，進入遞迴後，判斷，不存在左右結點，輸出this，也就是整個二元樹的右節點
     * 回退到this為根結點時，右節點也已經輸出，走到最後一步，輸出自己也就是this。
     * 整個後序遍歷就結束，那麼該二元樹的遍歷結果就是左，右，根
     */

    public void afterSelect() {
        if (this.left != null) {
            this.left.afterSelect();
        }

        if (this.right != null) {
            this.right.afterSelect();
        }
        System.out.println(this);
    }

    /**
     * @param num
     * @Date 2022/4/21 17:51
     * @Param
     * @Return Node
     * @MetodName preSearchByNum
     * @Author wang
     * @Description 根據結點的編號來查詢結點, 前序遍歷查詢，根，左，右
     */
    public Node preSearchByNum(int num) {
        //首先判斷傳進來的num與該結點的num是否相等
        //如果相等，那該結點就是我們要找的結點。
        if (this.num == num) {
            return this;
        }

        //如果不相等，該結點就不是我們要找的結點
        //那麼我們就遍歷該結點的左子節點，和右子結點
        //定義一個結點用於接收最後的返回結果
        Node resultNode = null;
        //如果該結點的左子結點不為空，就遞迴呼叫前序遍歷，繼續查詢，如果找到了，那麼resultNode就是我們想要的值
        if (this.left != null) {
            resultNode = this.left.preSearchByNum(num);
        }

        //如果遍歷完左子結點，已經找到了我們想要的結果，直接返回結果即可，
        if (resultNode != null) {
            return resultNode;
        }

        //如果左子結點為空，且沒有找到我們想要的結點的情況下。那就判斷右子結點
        if (this.right != null) {
            resultNode = this.right.preSearchByNum(num);
        }
        //最後，如果找到了，那麼resultNode一定會被賦值，如果沒找到，就會返回null
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/21 17:58
     * @Param
     * @Return Node
     * @MetodName infixSearchByNum
     * @Author wang
     * @Description 中序遍歷查詢，左，根，右進行查詢即可。
     */
    public Node infixSearchByNum(int num) {
        //首先判斷左子結點,如果存在左子結點，遞迴繼續查詢遍歷即可即可。
        Node resultNode = null;
        if (this.left != null) {
            resultNode = this.left.infixSearchByNum(num);
        }

        //如果左子結點已經找到了我們想要的結點，直接返回當前結點即可
        if (resultNode != null) {
            return resultNode;
        }

        //判斷根結點
        if (this.num == num) {
            return this;
        }

        //判斷右子結點，
        if (this.right != null) {
            resultNode = this.right.infixSearchByNum(num);
        }
        //最後返回我們的結果即可。
        return resultNode;
    }


    /**
     * @param num
     * @Date 2022/4/21 19:15
     * @Param
     * @Return Node
     * @MetodName afterSearchNum
     * @Author wang
     * @Description 後續遍歷結點進行查詢結點。左，右，根
     */
    public Node afterSearchNum(int num) {
        Node resultNode = null;
        //首先遍歷左結點
        if (this.left != null) {
            resultNode = this.left.afterSearchNum(num);
        }

        //判斷左結點是否找到哦啊
        if (resultNode != null) {
            return resultNode;
        }

        //判斷右節點是否為空
        if (this.right != null) {
            resultNode = this.right.afterSearchNum(num);
        }

        //判斷右節點是否找到
        if (resultNode != null) {
            return resultNode;
        }

        //判斷根結點是否為我們找的結點
        if (this.num == num) {
            return this;
        }
        //最後返回
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/25 19:30
     * @Param
     * @Return void
     * @MetodName delNodeByNum
     * @Author wang
     * @Description 根據結點的編號刪除結點
     */
    public void delNodeByNum(int num) {
        //首先，判斷當前結點的左結點是否為空，並且左結點的num是否與num相等
        if (this.left != null && this.left.num == num) {
            //如果相等，那就說明該結點就是我們要刪除的結點,將其左結點置空即可
            this.left = null;
            return;
        }

        //如果左結點沒有執行，說明左結點沒有我們想要的結果，也就是要刪除的結點不在左結點
        //那麼就對右節點進行判斷
        if (this.right != null && this.right.num == num) {
            this.right = null;
            return;
        }

        //如果左右結點均沒有找到目標結點
        //那麼就對左子樹進行遞迴刪除操作
        if (this.left != null) {
            this.left.delNodeByNum(num);
        }

        //同理，如果左子樹沒有目標結點，向右子樹進行遞迴刪除操作
        if (this.right != null) {
            this.right.delNodeByNum(num);
        }

    }
}

可以看到我們多出來了這麼兩個屬性：

    //這個屬性用來控制線索二元樹的結點的指向，0代表指向左結點，1代表指向前趨結點
    private int leftType;
    //這個屬性用來控制線索二元樹的結點的指向，0代表指向右結點，1代表指向後繼結點
    private int rightType;

中序線索化二元樹

  /**中序線索化二元樹*/
    /**
     * @param node 該結點為根結點，從根節點開始線索化二元樹，中序
     */
    public void infixThreadNodes(Node node) {
        /**首先判斷二元樹的根節點上會否為空，如果根結點為空，不可以線索化，因為沒有二元樹*/
        if (node == null) {
            return;
        }

        /**接著對左子樹進行線索化*/
        infixThreadNodes(node.getLeft());

        /**對當前結點進行線索化*/
        /**首先判斷當前結點的左子結點是否為空*/
        if (node.getLeft() == null) {
            //如果左子結點為空，說明就找到了我們需要線索化的結點
            //就可以將pre也就是一直在當前結點的前趨結點設定給當前結點的左子結點，
            //如果這是第一個結點，那麼pre為空，正好第一個結點的前趨結點也為空
            node.setLeft(pre);
            //並且將它的左子結點的型別設定為前趨結點。1代表前趨結點
            node.setLeftType(1);
        }

        /**接著判斷前趨結點的右子結點是否為空，前提是前趨結點不能為空，如果他為空，說明這是第一個結點還沒走完*/
        if (pre != null && pre.getRight() == null) {
            //如果條件滿足，說明前趨結點現在已經走到了值，並且還沒有線索到後繼結點，
            // 也就是當前結點的上一個結點（這個上一個結點就是當前的前趨結點）還沒有後繼，
            //那麼上一個結點的後繼結點就是當前結點，因此賦值前趨結點（也就是上一個結點）的後繼結點為當前結點。
            //這樣這條線索就連線上了,並且只有滿足葉子結點的結點才可以進行線索化
            pre.setRight(node);
            pre.setRightType(1);
        }

        //當前兩步走完之後，就可以將pre結點賦值為當前結點，
        // 因為下一個結點一走，當前結點就是前趨結點了。直到走到全部線索化結束
        //這步十分重要，這一步不寫，整個線索化就連線不上
        pre = node;

        /**對右子樹進行線索化*/
        infixThreadNodes(node.getRight());
    }

中序線索化二元樹思路

因為中序遍歷的二元樹順序是左根右，因此，首先對左子樹進行線索化，遞迴線索化即可；
當遞迴到左子樹的最左結點的時候，他的左結點肯定為空，那麼就對他的左結點賦值為pre（pre結點是線上索化的最後一步賦值為當前結點，這樣遞迴才能進行下去）,注意左結點的型別一定要改為1，代表他是前趨結點。前趨結點就線索掉了。
後繼結點的處理則是判斷前趨結點，當前趨結點不為空，並且前趨結點的右節點為空，那麼設定前趨結點的右節點為當前結點，也就是上一個結點未設定的右節點，型別同樣要設定為後繼
最後就是對pre這個結點賦值，為當前結點，因為下一次遞迴，當前結點就成了上一個結點，也就是這裡的pre
最後就是對二元樹的右子結點進行線索化。

中序線索化二元樹的遍歷

遍歷中序線索化二元樹首先應該明確的是他的遍歷順序要和遍歷原來的中序二元樹遍歷的結果是一樣的，才是遍歷成功
那麼第一步應該就是判斷根結點不為空，也就是迴圈結束條件
接著就回圈查詢當前結點的左子結點型別為0的也就是沒有被線索化的結點，只要他為0，那麼結點就一直往左子結點賦值。直到找到第一個被線索化的結點，輸出他，他就是我們第一個線索化並且也是中序遍歷的第一個左子結點。
輸出之後，判斷他的右子結點是否被線索化，如果被線索化，那麼當前結點node就被賦值為它自己的右子結點，並且輸出，如果他之後的結點的右子結點的型別又為1，那麼繼續往後走並賦值，說明他有後繼
直到右子結點的型別為0，退出迴圈之後，也應該向右再賦值，繼續向後遍歷

程式碼演示

    /**遍歷中序線索化二元樹*/
    public void infixThreadNodesSelect() {
        /**第一個結點為根結點*/
        Node node = root;
        while(node != null) {
            /**當結點不為空，就一直遍歷*/
            /**當該結點的左子結點的型別為1的時候，也就是說該結點是被線索化的結點,
             * 因為是中序遍歷，所以應該遍歷到最左邊的最左子結點，那麼就是第一個
             * 左子結點型別為1的結點。*/
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            /**當左子結點的型別為1,輸出左子結點*/
            System.out.println(node);

            /**當右子結點型別為1，當前結點輸出完畢後
             * 中序遍歷就應該輸出右子結點，那麼就是當前結點的右子結點型別只要為1，就往後移動
             * 並且輸出，當他為0，說明沒有線索化，那麼沒有後繼結點，但是他有右子結點，
             * 因此要在迴圈結束以後向後移動。*/
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            /**當右子結點回圈退出，說明這裡到了型別為0也就是後繼結點*/
            node = node.getRight();
        }

4.前序線索化二元樹、遍歷

線索化二元樹

 /**
     * 前序線索化二元樹
     */
    public void preThreadNodes(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() != 1) {
            preThreadNodes(node.getLeft());
        }


        /**對右子結點進行遞迴線索化*/
        if (node.getRightType() != 1) {
            preThreadNodes(node.getRight());
        }
    }

遍歷線索化二元樹

/**
     * 前序遍歷線索二元樹*/
    public void preThreadNodeSelect() {
        Node node = root;
        while(node !=null) {
            while(node.getLeftType() == 0) {
                /**前序遍歷為根左右，先輸出根結點,因為他每次進來回圈肯定是先到根結點，所以一進該回圈
                 * 就要輸出根結點，當他的lefttype=1迴圈結束，說明遇到了被線索化的地方了。*/
                System.out.println(node);
                /**再最左子結點進行遍歷*/
                node = node.getLeft();
            }
            /**上面的迴圈結束之後就應該輸出當前結點，也就是那個序列化的結點
             * 之後結點向右移動繼續遍歷*/
            System.out.println(node);
            node = node.getRight();
        }
  }

圖解

5.後序線索化二元樹

後續線索化二元樹

/**
 * 後序線索化二元樹的方法
 */
public void postThreadedBinaryTree(Node node) {
    /**首先判斷結店不能為空*/
    if (node == null) {
        return;
    }

    /**先後續線索化左子結點*/
    postThreadedBinaryTree(node.getLeft());
    /**在後續線索化右子結點*/
    postThreadedBinaryTree(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;
}

後續線索化思路類似，只不過將順序改為了左右根。

以上就是Java資料結構之線索化二元樹的實現的詳細內容，更多關於Java線索化二元樹的資料請關注it145.com其它相關文章！