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結(jié)點
 */
public class Node {
    //唯一編號
    private int num;
    //結(jié)點的值
    private String name;
    //左結(jié)點
    private Node left;
    //右節(jié)點
    private Node right;

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


    //構(gòu)造方法

    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() {
        //首先輸出根結(jié)點
        System.out.println(this);
        //其次判斷是否有左結(jié)點
        if (this.left != null) {
            //沒有左結(jié)點，就遞歸調(diào)用本方法輸出該結(jié)點。
            this.left.preSelect();
        }
        if (this.right != null) {
            this.right.preSelect();
        }
    }

    /**
     * 中序遍歷
     */
    public void infixSelect() {
        //首先判斷左結(jié)點
        if (this.left != null) {
            //如果左結(jié)點不為空，遞歸向左子樹調(diào)用
            this.left.infixSelect();
        }
        //當(dāng)左結(jié)點為空，再輸出根結(jié)點。當(dāng)他本身就是最后一個左結(jié)點的時候，會直接輸出，且沒有右節(jié)點
        System.out.println(this);
        if (this.right != null) {
            //右節(jié)點同樣如此，遞歸調(diào)用。直到?jīng)]有結(jié)點為止。
            this.right.infixSelect();
        }
    }

    /**
     * 設(shè)二叉樹有三個結(jié)點，根結(jié)點，左結(jié)點，右節(jié)點。
     * 后序遍歷,解釋，當(dāng)一個二叉樹的左結(jié)點不為空，那么他會進入下一個遞歸調(diào)用自己的后序遍歷方法
     * 此時，根結(jié)點就是左結(jié)點，這時判斷左結(jié)點，右節(jié)點均為空，就會輸出左結(jié)點
     * 回退到根結(jié)點為this的時候，左結(jié)點已經(jīng)判斷完畢，接下來是右節(jié)點，右節(jié)點不為空，進入后續(xù)遍歷遞歸，
     * 此時的this就是右節(jié)點，進入遞歸后，判斷，不存在左右結(jié)點，輸出this，也就是整個二叉樹的右節(jié)點
     * 回退到this為根結(jié)點時，右節(jié)點也已經(jīng)輸出，走到最后一步，輸出自己也就是this。
     * 整個后序遍歷就結(jié)束，那么該二叉樹的遍歷結(jié)果就是左，右，根
     */

    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 根據(jù)結(jié)點的編號來查詢結(jié)點, 前序遍歷查詢，根，左，右
     */
    public Node preSearchByNum(int num) {
        //首先判斷傳進來的num與該結(jié)點的num是否相等
        //如果相等，那該結(jié)點就是我們要找的結(jié)點。
        if (this.num == num) {
            return this;
        }

        //如果不相等，該結(jié)點就不是我們要找的結(jié)點
        //那么我們就遍歷該結(jié)點的左子節(jié)點，和右子結(jié)點
        //定義一個結(jié)點用于接收最后的返回結(jié)果
        Node resultNode = null;
        //如果該結(jié)點的左子結(jié)點不為空，就遞歸調(diào)用前序遍歷，繼續(xù)查找，如果找到了，那么resultNode就是我們想要的值
        if (this.left != null) {
            resultNode = this.left.preSearchByNum(num);
        }

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

        //如果左子結(jié)點為空，且沒有找到我們想要的結(jié)點的情況下。那就判斷右子結(jié)點
        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) {
        //首先判斷左子結(jié)點,如果存在左子結(jié)點，遞歸繼續(xù)查詢遍歷即可即可。
        Node resultNode = null;
        if (this.left != null) {
            resultNode = this.left.infixSearchByNum(num);
        }

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

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

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


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

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

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

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

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

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

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

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

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

    }
}

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

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

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

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

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

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

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

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

            /**當(dāng)右子結(jié)點類型為1，當(dāng)前結(jié)點輸出完畢后
             * 中序遍歷就應(yīng)該輸出右子結(jié)點，那么就是當(dāng)前結(jié)點的右子結(jié)點類型只要為1，就往后移動
             * 并且輸出，當(dāng)他為0，說明沒有線索化，那么沒有后繼結(jié)點，但是他有右子結(jié)點，
             * 因此要在循環(huán)結(jié)束以后向后移動。*/
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            /**當(dāng)右子結(jié)點循環(huán)退出，說明這里到了類型為0也就是后繼結(jié)點*/
            node = node.getRight();
        }

 /**
     * 前序線索化二叉樹
     */
    public void preThreadNodes(Node node) {
        /**首先判斷當(dāng)前節(jié)點是否為空*/
        if (node == null) {
            return;
        }

        /**如果是前序遍歷，那么先對當(dāng)前結(jié)點進行判斷，當(dāng)前結(jié)點的前趨結(jié)點的操作*/
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        /**處理后繼結(jié)點,定義的前趨結(jié)點不為空，說明他有值，就是已經(jīng)存在了上一個結(jié)點的值，他的右子結(jié)點沒有值的話，就可以
         * 給他賦予后繼結(jié)點為當(dāng)前結(jié)點，這里賦予的也就是上一個結(jié)點*/
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }

        /**這里是關(guān)鍵的一步*/
        pre = node;

        /**對左子結(jié)點進行線索化,注意，這里需要排除已經(jīng)被線索化掉的結(jié)點,因為這里要考慮一個情況，
         * 比如這里已將到了最下面一個左子結(jié)點，由于是前序遍歷，遍歷到左子結(jié)點，他的前趨結(jié)點在上面就設(shè)置了
         * 如果這里不判斷左子結(jié)點的類型，那么就會進入遞歸，但是這個遞歸如果進去了，就是錯誤的遞歸，因為他傳過去的結(jié)點
         * 是我們剛剛給他賦值的前趨結(jié)點，也就是根結(jié)點。會發(fā)生錯誤。因此得判斷類型*/
        if (node.getLeftType() != 1) {
            preThreadNodes(node.getLeft());
        }


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

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

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

    /**先后續(xù)線索化左子結(jié)點*/
    postThreadedBinaryTree(node.getLeft());
    /**在后續(xù)線索化右子結(jié)點*/
    postThreadedBinaryTree(node.getRight());

    /**處理當(dāng)前結(jié)點的前趨結(jié)點*/
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }

    /**處理后繼結(jié)點*/
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
}