package com.guor.tree;
 
public class GirlNode {
 
    private int no;
    private String name;
    private GirlNode left; //默認(rèn)null
    private GirlNode right; //默認(rèn)null
 
    //1、如果leftType == 0表示指向的是左子樹，如果 leftType == 1則表示指向的是前驅(qū)結(jié)點(diǎn)
    //2、如果rightType == 0表示指向的是右子樹，如果 rightType == 1則表示指向的是后繼結(jié)點(diǎn)
    private int leftType;
    private int rightType;
 
    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 GirlNode(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 GirlNode getLeft() {
        return left;
    }
    public void setLeft(GirlNode left) {
        this.left = left;
    }
    public GirlNode getRight() {
        return right;
    }
    public void setRight(GirlNode right) {
        this.right = right;
    }
    @Override
    public String toString() {
        return "GirlNode [no=" + no + ", name=" + name + "]";
    }
 
    //前序遍歷
    public void preOrder() {
        System.out.println(this);//先輸出父節(jié)點(diǎn)
        //遞歸向左子樹前序遍歷
        if(this.left != null) {
            this.left.preOrder();
        }
        //遞歸向右子樹前序遍歷
        if(this.right != null) {
            this.right.preOrder();
        }
    }
 
    //中序遍歷
    public void midOrder() {
        //遞歸向左子樹中序遍歷
        if(this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);//輸出父節(jié)點(diǎn)
        //遞歸向右子樹前序遍歷
        if(this.right != null) {
            this.right.midOrder();
        }
    }
 
    //后序遍歷
    public void postOrder() {
        //遞歸向左子樹后序遍歷
        if(this.left != null) {
            this.left.postOrder();
        }
        //遞歸向右子樹前序遍歷
        if(this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);//輸出父節(jié)點(diǎn)
    }
 
    //遞歸刪除結(jié)點(diǎn)
    //1.如果刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)
    //2.如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，則刪除該子樹
    public void delNode(int no) {
        //思路
		/*
		 * 	1. 因為我們的二叉樹是單向的，所以我們是判斷當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)是否需要刪除結(jié)點(diǎn)，而不能去判斷當(dāng)前這個結(jié)點(diǎn)是不是需要刪除結(jié)點(diǎn).
			2. 如果當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)不為空，并且左子結(jié)點(diǎn) 就是要刪除結(jié)點(diǎn)，就將this.left = null; 并且就返回(結(jié)束遞歸刪除)
			3. 如果當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)不為空，并且右子結(jié)點(diǎn) 就是要刪除結(jié)點(diǎn)，就將this.right= null ;并且就返回(結(jié)束遞歸刪除)
			4. 如果第2和第3步?jīng)]有刪除結(jié)點(diǎn)，那么我們就需要向左子樹進(jìn)行遞歸刪除
			5.  如果第4步也沒有刪除結(jié)點(diǎn)，則應(yīng)當(dāng)向右子樹進(jìn)行遞歸刪除.
		 */
        //2. 如果當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)不為空，并且左子結(jié)點(diǎn) 就是要刪除結(jié)點(diǎn)，就將this.left = null; 并且就返回(結(jié)束遞歸刪除)
        if(this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
 
        //3.如果當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)不為空，并且右子結(jié)點(diǎn) 就是要刪除結(jié)點(diǎn)，就將this.right= null ;并且就返回(結(jié)束遞歸刪除)
        if(this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
 
        //4.我們就需要向左子樹進(jìn)行遞歸刪除
        if(this.left != null) {
            this.left.delNode(no);
        }
 
        //5.則應(yīng)當(dāng)向右子樹進(jìn)行遞歸刪除
        if(this.right != null) {
            this.right.delNode(no);
        }
    }
}

package com.guor.tree;
public class BinaryTreeTest {
    public static void main(String[] args) {
        //創(chuàng)建一個二叉樹
        BinaryTree binaryTree = new BinaryTree();
        //創(chuàng)建結(jié)點(diǎn)
        HeroNode root = new HeroNode(1, "比比東");
        HeroNode node2 = new HeroNode(2, "云韻");
        HeroNode node3 = new HeroNode(3, "美杜莎");
        HeroNode node4 = new HeroNode(4, "納蘭嫣然");
        HeroNode node5 = new HeroNode(5, "雅妃");
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node4);
        node3.setRight(node5);
        binaryTree.setRoot(root);
        System.out.println("前序遍歷");
        binaryTree.preOrder();
        System.out.println("中序遍歷");
        binaryTree.midOrder();
        System.out.println("后序遍歷");
        binaryTree.postOrder();
        binaryTree.delNode(3);
        System.out.println("刪除結(jié)點(diǎn)3，前序遍歷");
        binaryTree.preOrder();
    }
}
 
//定義BinaryTree 二叉樹
class BinaryTree {
    private HeroNode root;
 
    public HeroNode getRoot() {
        return root;
    }
 
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序遍歷
    public void preOrder() {
        if(this.root != null) {
            this.root.preOrder();
        }else {
            System.out.println("二叉樹為空，不能遍歷");
        }
    }
    //中序遍歷
    public void midOrder() {
        if(this.root != null) {
            this.root.midOrder();
        }else {
            System.out.println("二叉樹為空，無法遍歷");
        }
    }
    //后序遍歷
    public void postOrder() {
        if(this.root != null) {
            this.root.postOrder();
        }else {
            System.out.println("二叉樹為空，無法遍歷");
        }
    }
 
    //刪除結(jié)點(diǎn)
    public void delNode(int no) {
        if(root != null) {
            //如果只有一個root結(jié)點(diǎn), 這里立即判斷root是不是就是要刪除結(jié)點(diǎn)
            if(root.getNo() == no) {
                root = null;
            } else {
                //遞歸刪除
                root.delNode(no);
            }
        }else{
            System.out.println("空樹，不能刪除~");
        }
    }
}

package com.guor.tree;
 
//定義ThreadBinaryTree，實(shí)現(xiàn)了線索化功能的二叉樹
public class ThreadedBinaryTree {
    private HeroNode root;
 
    //為了實(shí)現(xiàn)線索化，需要創(chuàng)建指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針
    //在遞歸進(jìn)行線索化時，pre總是保留前一個結(jié)點(diǎn)
    private HeroNode pre = null;
 
    public HeroNode getRoot() {
        return root;
    }
 
    public void setRoot(HeroNode root) {
        this.root = root;
    }
 
    //重載threadedNodes方法
    public void threadedNodes(){
        this.threadedNodes(root);
    }
 
    /**
     * 編寫對二叉樹進(jìn)行中序線索化的方法
     * @param node 當(dāng)前需要線索化的結(jié)點(diǎn)
     */
    public void threadedNodes(HeroNode node){
        //如果node==null，不能線索化
        if(node == null){
            return;
        }
 
        //1、先線索化左子樹
        threadedNodes(node.getLeft());
        //2、線索化當(dāng)前結(jié)點(diǎn)
 
        //處理當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
        //以8為例來理解
        //8結(jié)點(diǎn)的.left = null，8結(jié)點(diǎn)的.leftType = 1
        if(node.getLeft() == null){
            //讓當(dāng)前結(jié)點(diǎn)的左指針指向前驅(qū)結(jié)點(diǎn)
            node.setLeft(pre);
            //修改當(dāng)前結(jié)點(diǎn)的左指針的類型，指向前驅(qū)結(jié)點(diǎn)
            node.setLeftType(1);
        }
 
        //處理后繼結(jié)點(diǎn)
        if(pre != null && pre.getRight() == null){
            //讓當(dāng)前結(jié)點(diǎn)的右指針指向當(dāng)前結(jié)點(diǎn)
            pre.setRight(node);
            //修改當(dāng)前結(jié)點(diǎn)的右指針的類型=
            pre.setRightType(1);
        }
 
        //每處理一個結(jié)點(diǎn)后，讓當(dāng)前結(jié)點(diǎn)是下一個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
        pre = node;
 
        //3、線索化右子樹
        threadedNodes(node.getRight());
    }
 
    //前序遍歷
    public void preOrder() {
        if(this.root != null) {
            this.root.preOrder();
        }else {
            System.out.println("二叉樹為空，不能遍歷");
        }
    }
    //中序遍歷
    public void midOrder() {
        if(this.root != null) {
            this.root.midOrder();
        }else {
            System.out.println("二叉樹為空，無法遍歷");
        }
    }
    //后序遍歷
    public void postOrder() {
        if(this.root != null) {
            this.root.postOrder();
        }else {
            System.out.println("二叉樹為空，無法遍歷");
        }
    }
 
    //刪除結(jié)點(diǎn)
    public void delNode(int no) {
        if(root != null) {
            //如果只有一個root結(jié)點(diǎn), 這里立即判斷root是不是就是要刪除結(jié)點(diǎn)
            if(root.getNo() == no) {
                root = null;
            } else {
                //遞歸刪除
                root.delNode(no);
            }
        }else{
            System.out.println("空樹，不能刪除~");
        }
    }
}

package com.guor.tree;
 
public class ThreadedBinaryTreeTest {
    public static void main(String[] args) {
        //測試中序線索二叉樹的功能
        HeroNode root = new HeroNode(1,"比比東");
        HeroNode node2 = new HeroNode(3,"云韻");
        HeroNode node3 = new HeroNode(6,"納蘭嫣然");
        HeroNode node4 = new HeroNode(8,"雅妃");
        HeroNode node5 = new HeroNode(10,"千仞雪");
        HeroNode node6 = new HeroNode(14,"美杜莎");
 
        //二叉樹，后面我們要遞歸創(chuàng)建，現(xiàn)在簡單處理使用手動創(chuàng)建
        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é)點(diǎn)測試
        HeroNode leftNode = node5.getLeft();
        System.out.println("10號結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)是："+leftNode);//應(yīng)該是3號
 
        HeroNode rightNode = node5.getRight();
        System.out.println("10號結(jié)點(diǎn)的后繼結(jié)點(diǎn)是："+rightNode);//應(yīng)該是1號
    }
}

/**
 * 遍歷線索化二叉樹的方法
 */
public void threadedList(){
    //定義一個變量，存儲當(dāng)前遍歷的結(jié)點(diǎn)，從root開始
    HeroNode node = root;
    while (node != null){
        //循環(huán)找到leftType == 1的結(jié)點(diǎn)，第一個找到就是8結(jié)點(diǎn)
        //后面隨著遍歷而變化，因為當(dāng)leftType==1時，說明該結(jié)點(diǎn)是按照線索化處理后的有效結(jié)點(diǎn)
        while(node.getLeftType() == 0){
            node = node.getLeft();
        }
        //打印當(dāng)前結(jié)點(diǎn)
        System.out.println(node);
        //如果當(dāng)前結(jié)點(diǎn)的右指針指向的是后繼結(jié)點(diǎn)，就一直輸出
        while(node.getRightType() == 1){
            //獲取當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)
            node = node.getRight();
            System.out.println(node);
        }
        //替換這個遍歷的結(jié)點(diǎn)
        node = node.getRight();
    }
}

package com.guor.tree;
 
import java.util.Arrays;
 
public class HeapSort {
    public static void main(String[] args) {
        //要求將數(shù)組進(jìn)行升序排序
        int arr[] = {4,6,8,5,9};
        heapSort(arr);
    }
 
    public static void heapSort(int arr[]){
        int temp = 0;
        System.out.println("堆排序。");
 
        //分步完成
        //adjustHeap(arr,1,arr.length);
        //System.out.println("第一次調(diào)整："+ Arrays.toString(arr));//{4,9,8,5,6}
        //adjustHeap(arr,0,arr.length);
        //System.out.println("第二次調(diào)整："+ Arrays.toString(arr));//{9,6,8,5,4}
 
        //完成最終代碼
        //將無序序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆
        //arr.length/2-1為葉子結(jié)點(diǎn)個數(shù)
        for(int i = arr.length/2-1;i>=0;i--){
            adjustHeap(arr, i, arr.length);
        }
        System.out.println("調(diào)整為大頂堆："+ Arrays.toString(arr));//大頂堆{9,6,8,5,4}
 
        //第二步：將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再講堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。
        //第三步：重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個序列有序。
        for(int j = arr.length - 1;j > 0; j--){
            //交換
            temp=arr[j];
            arr[j]= arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println("最終有序序列："+ Arrays.toString(arr));//大頂堆{4,5,6,8,9}
    }
 
    /**
     * 功能：完成將以i為葉子節(jié)點(diǎn)的樹調(diào)整為大頂堆
     * @demo int arr[] = {4,6,8,5,9};i = 1 --> adjustHeap --> {4,9,8,5,6}
     * 如果再調(diào)用adjustHeap，傳入i=0 --> 大頂堆{9,6,8,5,4}
     * @param arr 待調(diào)整的數(shù)組
     * @param i 表示非葉子結(jié)點(diǎn)在數(shù)組中的索引
     * @param length 表示對多少個元素進(jìn)行繼續(xù)調(diào)整，length逐漸減少
     */
    public static void adjustHeap(int arr[], int i, int length){
        //取出當(dāng)前元素的值，保存為臨時變量
        int temp = arr[i];
        //1、k = i * 2 + 1 ,k是i結(jié)點(diǎn)的左子結(jié)點(diǎn)
        for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
            //左子結(jié)點(diǎn)的值小于右子結(jié)點(diǎn)的值
            if(k+1<length && arr[k] < arr[k+1]){
                k++;//k指向右子結(jié)點(diǎn)
            }
            //如果子結(jié)點(diǎn)大于父節(jié)點(diǎn)
            if(arr[k] > temp){
                arr[i] = arr[k];//將較大的值賦給當(dāng)前結(jié)點(diǎn)
                i = k;//i指向k,繼續(xù)循環(huán)比較
            }else{
                break;
            }
        }
        //當(dāng)for循環(huán)結(jié)束后，我們已經(jīng)將以i為父節(jié)點(diǎn)的樹的最大值，放在了最頂，完成局部大頂堆
        arr[i] = temp;//將temp值放到調(diào)整后的位置
    }
}

public static void main(String[] args) {
    //模擬測試1000萬條數(shù)據(jù)
    int[] arr = new int[10000000];
    for(int i = 0; i< 10000000; i++){
        arr[i] = (int)(Math.random() * 10000000);
    }
    long start = new Date().getTime();
    heapSort(arr);
    long end = new Date().getTime();
    System.out.println("1000萬條數(shù)據(jù)，堆排序耗時："+(end-start)+"ms");
}

package com.guor.huffmantree;
 
public class Node implements Comparable<Node>{
    int value;//結(jié)點(diǎn)權(quán)值
    Node left;//指向左子結(jié)點(diǎn)
    Node right;//指向右子結(jié)點(diǎn)
 
    public Node(int value){
        this.value = value;
    }
 
    @Override
    public String toString(){
        return "Node [value="+value+"]";
    }
 
    @Override
    public int compareTo(Node o) {
        //表示從小到大排序
        return this.value - o.value;
    }
 
    //寫一個前序遍歷
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }
}

package com.guor.huffmantree;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        Node root = createHuffmanTree(arr);
 
        //測試
        preOrder(root);
    }
 
    //編寫一個前序遍歷的方法
    public static void preOrder(Node root){
        if(root != null){
            root.preOrder();
        }else {
            System.out.println("空樹不能遍歷.");
        }
    }
 
    //創(chuàng)建赫夫曼樹的方法
    public static Node createHuffmanTree(int[] arr){
        List<Node> nodeList = new ArrayList<>();
        for(int value : arr){
            nodeList.add(new Node(value));
        }
 
        //處理的過程是一個循環(huán)的過程
        while (nodeList.size() > 1){
            //從小到大排序
            Collections.sort(nodeList);
            System.out.println("nodes="+nodeList);
 
            //取出根結(jié)點(diǎn)權(quán)值最小的兩顆二叉樹
            //1、取出權(quán)值最小的結(jié)點(diǎn)
            Node leftNode = nodeList.get(0);
 
            //2、取出權(quán)值第二小的結(jié)點(diǎn)
            Node rightNode = nodeList.get(1);
 
            //3、構(gòu)建一顆新的二叉樹
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
 
            //4、從list中刪除處理過的二叉樹
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);
 
            //5、將parent加入list
            nodeList.add(parent);
        }
 
        //返回赫夫曼樹的root結(jié)點(diǎn)
        return nodeList.get(0);
    }
}