資料結構---樹結構-有解無憂

為什么需要樹這種資料結構

陣列存盤方式的分析

優點：通過下標方式訪問元素，速度快，對于有序陣列，還可使用二分查找提高檢索速度，
缺點：如果要檢索具體某個值，或者插入值(按一定順序)會整體移動，效率較低，

鏈式存盤方式的分析

優點：在一定程度上對陣列存盤方式有優化(比如：插入一個數值節點，只需要將插入節點，鏈接到鏈表中即可，洗掉效率也很好)，
缺點：在進行檢索時，效率仍然較低，比如(檢索某個值，需要從頭節點開始遍歷)

樹存盤方式的分析

能提高資料存盤，讀取的效率, 比如利用二叉排序樹(Binary Sort Tree)，既可以保證資料的檢索速度，同時也可以保證資料的插入，洗掉，修改的速度，

二叉樹的概念

樹有很多種，每個節點最多只能有兩個子節點的一種形式稱為二叉樹，
二叉樹的子節點分為左節點和右節點
如果該二叉樹的所有葉子節點都在最后一層，并且結點總數= 2^n -1 , n 為層數，則我們稱為滿二叉樹，
如果該二叉樹的所有葉子節點都在最后一層或者倒數第二層，而且最后一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續，我們稱為完全二叉樹

二叉樹遍歷的說明

前序遍歷: 先輸出父節點，再遍歷左子樹和右子樹
中序遍歷: 先遍歷左子樹，再輸出父節點，再遍歷右子樹
后序遍歷: 先遍歷左子樹，再遍歷右子樹，最后輸出父節點
小結: 看輸出父節點的順序，就確定是前序，中序還是后序

二叉樹遍歷的代碼示例

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        // 創建需要的節點
        HeroHode root = new HeroHode(1, "宋江");
        HeroHode hode1 = new HeroHode(2, "吳用");
        HeroHode hode2 = new HeroHode(3, "林沖");
        HeroHode hode3 = new HeroHode(4, "武松");
        HeroHode hode4 = new HeroHode(5, "孫權");
        HeroHode hode5 = new HeroHode(6, "曹操");
        HeroHode hode6 = new HeroHode(7, "劉備");

        // 說明,先手動創建該二叉樹,以后會使用遞回的方式創建二叉樹
        root.setLeft(hode1);
        root.setRight(hode2);
        hode1.setLeft(hode3);
        hode1.setRight(hode4);
        hode2.setLeft(hode5);
        hode2.setRight(hode6);

        binaryTree.setRoot(root);

//        System.out.println(binaryTree.preOrderSearch(5));
//        System.out.println(binaryTree.infixOrderSearch(2));
//        System.out.println(binaryTree.postOrderSearch(4));


        // 1 2 3 5 4
        System.out.println("前序遍歷");
        binaryTree.preOrder();

        // 2 1 5 3 4
        System.out.println("中序遍歷");
        binaryTree.infixOrder();

        // 2 4 3 1
        System.out.println("后序遍歷");
        binaryTree.postOrder();

        binaryTree.deleteNode(5);
        System.out.println("洗掉后: ");
        binaryTree.preOrder();

    }
}

/**
 * 二叉樹
 */
class BinaryTree {

    private HeroHode root;

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

    /**
     * 前序遍歷
     */
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉樹為空,無法遍歷");
        }
    }

    /**
     * 中序遍歷
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉樹為空,無法遍歷");
        }
    }

    /**
     * 后序遍歷
     */
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉樹為空,無法遍歷");
        }
    }

    public HeroHode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    public HeroHode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    public HeroHode postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }

    public void deleteNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.deleteNode(no);
            }
        } else {
            System.out.println("空樹,不能洗掉!!!");
        }
    }
}

/**
 * 節點
 */ 
class HeroHode {
    private int no;
    private String name;
    private HeroHode left;
    private HeroHode right;

    public HeroHode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroHode{" +
                "no=" + no +
                ", 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 HeroHode getLeft() {
        return left;
    }

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

    public HeroHode getRight() {
        return right;
    }

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

    /**
     * 前序遍歷
     */
    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);
    }

    /**
     * 根據no前序遍歷查找
     *
     * @param no
     * @return
     */
    public HeroHode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroHode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            // 說明在左子樹上找到了
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 根據no中序遍歷查找
     *
     *
     * @param no
     * @return
     */
    public HeroHode infixOrderSearch(int no) {
        HeroHode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 根據no后序遍歷查找
     *
     * @param no
     * @return
     */
    public HeroHode postOrderSearch(int no) {

        HeroHode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

    /**
     * 遞回洗掉節點
     *
     * @param no
     */
    public void deleteNode(int no) {
        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.deleteNode(no);
        }
        if (this.right != null) {
            this.right.deleteNode(no);
        }
    }
}

順序存盤二叉樹

從資料存盤來看，陣列存盤方式和樹的存盤方式可以相互轉換，即陣列可以轉換成樹，樹也可以轉換成陣列，

順序存盤二叉樹的特點:

順序二叉樹通常只考慮完全二叉樹
第n個元素的左子節點為 2 * n + 1
第n個元素的右子節點為 2 * n + 2
第n個元素的父節點為 (n-1) / 2
n : 表示二叉樹中的第幾個元素(按0開始編號，如上圖所示)

順序存盤二叉樹代碼示例

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
//        arrBinaryTree.preOrder();
//        arrBinaryTree.infixOrder();
        arrBinaryTree.postOrder();
    }
}

class ArrBinaryTree {
    // 存盤資料節點的陣列
    private int[] arr;

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder() {
        preOrder(0);
    }

    /**
     * 順序存盤二叉樹的前序遍歷
     *
     * @param index 陣列的下標
     */
    public void preOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("陣列為空,不能按照二叉樹的前序遍歷");
        }
        // 輸出當前元素
        System.out.println(arr[index]);
        // 向左遞回遍歷
        if ((index * 2 + 1) < arr.length) {
            preOrder(2 * index + 1);
        }
        // 向右遞回遍歷
        if ((index * 2 + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }

    public void infixOrder() {
        infixOrder(0);
    }

    /**
     * 順序存盤二叉樹的前序遍歷
     *
     * @param index 陣列的下標
     */
    public void infixOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("陣列為空,不能按照二叉樹的前序遍歷");
        }
        // 向左遞回遍歷
        if ((index * 2 + 1) < arr.length) {
            infixOrder(2 * index + 1);
        }
        // 輸出當前元素
        System.out.println(arr[index]);
        // 向右遞回遍歷
        if ((index * 2 + 2) < arr.length) {
            infixOrder(2 * index + 2);
        }
    }

    public void postOrder() {
        postOrder(0);
    }

    /**
     * 順序存盤二叉樹的前序遍歷
     *
     * @param index 陣列的下標
     */
    public void postOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("陣列為空,不能按照二叉樹的前序遍歷");
        }
        // 向左遞回遍歷
        if ((index * 2 + 1) < arr.length) {
            postOrder(2 * index + 1);
        }
        // 向右遞回遍歷
        if ((index * 2 + 2) < arr.length) {
            postOrder(2 * index + 2);
        }
        // 輸出當前元素
        System.out.println(arr[index]);
    }

}

赫夫曼樹

基本介紹

給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)，
赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近，

赫夫曼樹幾個重要概念和舉例說明

路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑，通路中分支的數目稱為路徑長度，若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1
結點的權及帶權路徑長度：若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權，結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積
樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹，
WPL最小的就是赫夫曼樹

構成赫夫曼樹的步驟：

從小到大進行排序, 將每一個資料，每個資料都是一個節點，每個節點可以看成是一顆最簡單的二叉樹
取出根節點權值最小的兩顆二叉樹
組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
再將這顆新的二叉樹，以根節點的權值大小再次排序，不斷重復 1-2-3-4 的步驟，直到數列中，所有的資料都被處理，就得到一顆赫夫曼樹

赫夫曼樹的代碼示例

/**
 * 赫夫曼樹
 *
 * @author jianjieming
 * @date 2019/11/20 14:09
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node root = createHuffmanTree(arr);
        perOrder(root);
    }

    /**
     * 創建赫夫曼樹
     *
     * @param arr 需要創建成赫夫曼樹的陣列
     * @return 回傳創建好的赫夫曼樹的root節點
     */
    public static Node createHuffmanTree(int[] arr) {
        ArrayList<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        while (nodes.size() > 1) {
            nodes.sort(Comparator.comparing(Node::getValue));
            System.out.println(nodes);

            // 1.取出權值最小的兩個二叉樹
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);

            // 2.構建一個新的二叉樹
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            // 3.從ArrayList中洗掉處理過的二叉樹
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            // 4.將parent加入到nodes
            nodes.add(parent);
        }
        // 回傳赫夫曼樹的root節點
        return nodes.get(0);
    }

    public static void perOrder(Node root) {
        if (root != null) {
            root.perOrder();
        } else {
            System.out.println("樹是空的,無法遍歷!!!");
        }
    }
}

/**
 * 節點類
 */
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = https://www.cnblogs.com/jianjieming/p/value;
    }

    @Override
    public String toString() {
        return"Node{" +
                "value="https://www.cnblogs.com/jianjieming/p/+ value +'}';
    }

    public int getValue() {
        return value;
    }

    /**
     * 前序遍歷
     */
    public void perOrder() {
        System.out.println(this.value);
        if (this.left != null) {
            this.left.perOrder();
        }
        if (this.right != null) {
            this.right.perOrder();
        }
    }
}

二叉排序樹

二叉排序樹：BST: (Binary Sort(Search) Tree), 對于二叉排序樹的任何一個非葉子節點，要求左子節點的值比當前節點的值小，右子節點的值比當前節點的值大，

特別說明：如果有相同的值，可以將該節點放在左子節點或右子節點，

比如(7, 3, 10, 12, 5, 1, 9)，對應的二叉排序樹為：

二叉排序樹的洗掉情況比較復雜，有下面三種情況需要考慮：

洗掉葉子節點 (比如上圖：2, 5, 9, 12)
洗掉只有一顆子樹的節點 (比如上圖：1)
洗掉有兩顆子樹的節點. (比如上圖：7, 3，10 )

二叉排序樹的代碼示例

/**
 * 二叉排序樹測驗
 *
 * @author jianjieming
 * @date 2019/11/21 9:48
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new NodeDemo(arr[i]));
        }
        System.out.println("中序遍歷二叉排序樹: ");
        binarySortTree.infixOrder();

        // 測驗洗掉葉子節點(2, 5, 9, 12)
        binarySortTree.delNode(2);
        binarySortTree.delNode(5);
        binarySortTree.delNode(9);
        binarySortTree.delNode(12);
        binarySortTree.delNode(7);
        binarySortTree.delNode(3);
        binarySortTree.delNode(10);
        binarySortTree.delNode(1);
        System.out.println("洗掉節點后: ");
        binarySortTree.infixOrder();

    }
}

/**
 * 創建二叉排序樹
 */
class BinarySortTree {
    private NodeDemo root;

    /**
     * 添加節點的方法
     */
    public void add(NodeDemo node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序樹為空,無法遍歷!!!");
        }
    }

    /**
     * 洗掉節點
     */
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            // 1. 先找到要洗掉的節點 targetNode
            NodeDemo targetNode = search(value);
            // 如果沒有找到要洗掉的節點
            if (targetNode == null) {
                return;
            }
            // 如果當前這顆二叉排序樹只有一個節點
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            // 查找targetNode的父節點
            NodeDemo parent = searchParent(value);
            // 如果要洗掉的節點是葉子節點
            if (targetNode.left == null && targetNode.right == null) {
                // 判斷targetNode是父節點的左子節點還是右子節點
                if (parent.left != null && parent.left.value =https://www.cnblogs.com/jianjieming/p/= value) {
                    // 是左子節點
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {
                    // 是右子節點
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                // 洗掉有兩顆子樹的節點
                int minVal = delRightTreeMin(targetNode.right);
//                int maxVal = delLeftTreeMax(targetNode.right);
                targetNode.value = minVal;
            } else {
                // 洗掉只有一顆子樹的節點
                // 如果要洗掉的節點有左子節點
                if (targetNode.left != null) {
                    if (parent != null) {
                        // 如果targetNode是parent的左子節點
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            // targetNode是parent的右子節點
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    if (parent != null) {
                        // 要洗掉的節點有右子節點
                        // 如果targetNode是parent的左子節點
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            // targetNode是parent的右子節點
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 查找要洗掉的節點
     */
    public NodeDemo search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 查找父節點
     */
    public NodeDemo searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 洗掉以node 為根節點的二叉排序樹最小節點
     *
     * @param node 傳入的節點(當做二叉排序樹的根節點)
     * @return 回傳的 以node 為根節點的二叉排序樹最小節點的值
     */
    public int delRightTreeMin(NodeDemo node) {
        NodeDemo target = node;
        // 回圈查找左節點,就會找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // 這時target就指向了最小節點, 洗掉最小節點
        delNode(target.value);
        return target.value;
    }

    public int delLeftTreeMax(NodeDemo node) {
        NodeDemo target = node;
        // 回圈查找左節點,就會找到最小值
        while (target.right != null) {
            target = target.right;
        }
        // 這時target就指向了最小節點, 洗掉最小節點
        delNode(target.value);
        return target.value;
    }
}

/**
 * 節點
 */
class NodeDemo {
    int value;
    NodeDemo left;
    NodeDemo right;

    public NodeDemo(int value) {
        this.value = https://www.cnblogs.com/jianjieming/p/value;
    }

    @Override
    public String toString() {
        return"NodeDemo{" +
                "value="https://www.cnblogs.com/jianjieming/p/+ value +'}';
    }

    /**
     * 添加節點的方法
     */
    public void add(NodeDemo node) {
        if (node == null) {
            return;
        }
        // 判斷傳入節點的值,和當前子樹的根節點的值關系
        if (node.value < this.value) {
            // 如果當前節點左子節點是否為null
            if (this.left == null) {
                this.left = node;
            } else {
                // 遞回向左子樹添加
                this.left.add(node);
            }
        } else {
            // 添加的節點的值大于當前節點的值
            if (this.right == null) {
                this.right = node;
            } else {
                // 遞回向左子樹添加
                this.right.add(node);
            }
        }
    }

    /**
     * 中序遍歷
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 查找要洗掉的節點
     *
     * @param value 希望洗掉節點的值
     */
    public NodeDemo search(int value) {
        if (value =https://www.cnblogs.com/jianjieming/p/= this.value) {
            return this;
        } else if (value < this.value) {
            // 如果查找的值,小于當前節點,則向左子樹遞回查找
            if (this.left == null) {
                // 如果左子節點為空
                return null;
            }
            return this.left.search(value);
        } else {
            // 如果查找的值,不小于當前節點,則向右子樹遞回查找
            if (this.right == null) {
                // 如果左子節點為空
                return null;
            }
            return this.right.search(value);
        }
    }

    /**
     * 查找要洗掉節點的父節點
     *
     * @param value 要找到的節點的值
     * @return 回傳的是要洗掉節點的父節點, 沒有回傳null
     */
    public NodeDemo searchParent(int value) {
        // 如果當前節點就是要洗掉的節點的父節點,就回傳
        if ((this.left != null && this.left.value == value)
                || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 如果要查找的值小于當前節點的值,并且當前節點的左子節點不為空
            if (value < this.value && this.left != null) {
                // 向左子樹遞回查找
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                // 向右子樹遞回查找
                return this.right.searchParent(value);
            } else {
                // 沒有找到父節點
                return null;
            }
        }
    }

}

如果覺得對你有幫助，歡迎來訪我的博客：http://jianjieming.com

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121149.html

標籤：其他

上一篇：CodeForces - 1255C（構造+模擬）

下一篇：Empire基本使用方法