Java數據結構學(xué)習之樹(shù)

目錄

一、樹(shù)

1.1 概念

與線(xiàn)性表表示的一一對應的線(xiàn)性關(guān)系不同，樹(shù)表示的是數據元素之間更為復雜的非線(xiàn)性關(guān)系。

直觀(guān)來(lái)看，樹(shù)是以分支關(guān)系定義的層次結構。 樹(shù)在客觀(guān)世界中廣泛存在，如人類(lèi)社會(huì )的族譜和各種社會(huì )組織機構都可以用樹(shù)的形象來(lái)表示。

簡(jiǎn)單來(lái)說(shuō)，樹(shù)表示的是1對多的關(guān)系。

定義（邏輯結構）：

樹(shù)(Tree)是n( n>=0 )個(gè)結點(diǎn)的有限集合，沒(méi)有結點(diǎn)的樹(shù)稱(chēng)為空樹(shù)，在任意一顆非空樹(shù)中： 有且僅有一個(gè)特定的稱(chēng)為根(root)的結點(diǎn) 。

當n>1的時(shí)，其余結點(diǎn)可分為 m( m>0 ) 個(gè)互不相交的有限集T1，T2，…, Tm，其中每一個(gè)集合 Ti 本身又是一棵樹(shù)，并且稱(chēng)之為根的子樹(shù)。

注意：樹(shù)的定義是一個(gè)遞歸定義，即在樹(shù)的定義中又用到樹(shù)的概念。

1.2 術(shù)語(yǔ)

（1）一個(gè)結點(diǎn)的子樹(shù)的根，稱(chēng)為該結點(diǎn)的孩子(兒子)，相應的該結點(diǎn)稱(chēng)為子樹(shù)的根的父親。

（2）沒(méi)有孩子的結點(diǎn)稱(chēng)為樹(shù)葉，又叫葉子結點(diǎn) 。(國外, nil叫葉子) 具有相同父親的結點(diǎn)互為兄弟(同胞, 姐妹)。

（3）從結點(diǎn)n1 到 nk 的路徑定義為節點(diǎn) n1 n2 … nk 的一個(gè)序列，使得對于 1 <= i < k，節點(diǎn) ni是 ni+1 的父親。這條路徑的長(cháng)是為該路徑上邊的條數，即 k-1。從每一個(gè)結點(diǎn)到它自己有一條長(cháng)為 0 的路徑。注意，在一棵樹(shù)中從根到每個(gè)結點(diǎn)恰好存在一條路徑。 如果存在從n1到n2的一條路徑，那么n1是n2的一位祖先 ，而n2是n1的一個(gè)后裔。如果n1 != n2，那么n1是n2的真祖先, 而n2是n1的真后裔。

（4）結點(diǎn)的層級從根開(kāi)始定義，根為第一層，根的孩子為第二層。若某結點(diǎn)在第i層，則其孩子就在i+1層。(樹(shù)有層級定義)

（5）對任意結點(diǎn)ni，ni的深度為從根到ni的唯一路徑的長(cháng)。因此，根的深度為0。(深度)

（6）一顆樹(shù)的高等于它根的高。一顆樹(shù)的深度等于它最深的樹(shù)葉的深度; 該深度總是等于這棵樹(shù)的高。

（7）性質(zhì)：如果一棵樹(shù)有n個(gè)結點(diǎn)，那么它有n-1條邊。(為什么呢?)

每一結點(diǎn)都有一個(gè)邊指向它(除了根節點(diǎn))
每一條邊都指向一個(gè)結點(diǎn)

（8） 概念： 度 (圖這種數據結構) 對圖這種數據結構: 每個(gè)結點(diǎn)的度: 一般指有幾個(gè)結點(diǎn)和我這個(gè)結點(diǎn)相關(guān)

樹(shù)這種數據結構: 度: 一般指有幾個(gè)孩子

1.3 樹(shù)的實(shí)現

怎么通過(guò)代碼來(lái)模擬一個(gè)樹(shù)
集合類(lèi)： 數據容器
數組 鏈表, 數組+鏈表
數據結構表現形式：樹(shù)

1.3.1 用數組來(lái)實(shí)現一棵樹(shù)？

如果非要用數組存儲一棵樹(shù)的話(huà), 也可以, 不過(guò)會(huì )存在各種問(wèn)題。

1.3.2 用鏈表實(shí)現一棵樹(shù)？

如果用鏈表存儲一棵樹(shù)也會(huì )有一些問(wèn)題( 1, 犧牲內存, 2, 多種結點(diǎn)類(lèi)型)

1.3.3 樹(shù)的轉化

（1）經(jīng)過(guò)轉化的樹(shù)比較容易存儲: 這種根據下面特點(diǎn)轉化的樹(shù) 被稱(chēng)為 二叉樹(shù)。

① 如果一個(gè)結點(diǎn) 有孩子, 那么讓他的第一個(gè)孩子, 作為這個(gè)結點(diǎn)的left子結點(diǎn)。
②如果一個(gè)結點(diǎn)有兄弟結點(diǎn), 那么讓他的兄弟結點(diǎn), 作為這個(gè)結點(diǎn)的right子結點(diǎn)。

1.4 二叉樹(shù)

概念： 一個(gè)樹(shù), 每一個(gè)結點(diǎn)最多有兩個(gè)孩子, 孩子有嚴格的左右之分

1.4.1 二叉樹(shù)的性質(zhì)

（1）二叉樹(shù)具有以下重要性質(zhì)：

①二叉樹(shù)在第i層至多有2的(i-1)次方個(gè)節點(diǎn)
②層次為k的二叉樹(shù)至多有2的k次方 - 1個(gè)節點(diǎn)

（2）對任何一顆二叉樹(shù)T，如果其葉子節點(diǎn)數為n0 , 度為2的節點(diǎn)數為n2，則n0 = n2 + 1

（3）具有n個(gè)節點(diǎn)的完全二叉樹(shù)，樹(shù)的高度為log2n (向下取整)。

（4）如果對一顆有n個(gè)結點(diǎn)的完全二叉樹(shù)的結點(diǎn)按層序從1開(kāi)始編號，則對任意一結點(diǎn)有：

如果編號i為1，則該結點(diǎn)是二叉樹(shù)的根;
如果編號i > 1，則其雙親結點(diǎn)編號為 parent(i) = i/2, 
若 2i > n 則該結點(diǎn)沒(méi)有左孩子，否則其左孩子的編號為 2i,
若 2i + 1 > n 則該結點(diǎn)沒(méi)有右孩子，否則其右孩子的編號為 2i + 1。

（5）二叉樹(shù)的父子結點(diǎn)關(guān)系: 2倍 或者 2倍+1關(guān)系

–> 二叉樹(shù)可以用數組存儲 就是根據上述性質(zhì)(但是一般在實(shí)際應用和開(kāi)發(fā)中, 我們一般用鏈表存儲二叉樹(shù))

1.4.2 二叉樹(shù)的遍歷

深度優(yōu)先遍歷： 棧

（1）先序遍歷：先遍歷根結點(diǎn), 再遍歷左子樹(shù), 再遍歷右子樹(shù)
（2）中序遍歷：先遍歷左子樹(shù), 再遍歷根結點(diǎn), 再遍歷右子樹(shù)
（3）后序遍歷：先遍歷左子樹(shù), 再遍歷右子樹(shù), 再遍歷根結點(diǎn)

廣度優(yōu)先遍歷： 隊列

樹(shù)的廣度優(yōu)先遍歷一般為層級遍歷。（廣度優(yōu)先遍歷–>圖的廣度遍歷）

1.4.3 二叉樹(shù)的建樹(shù)

給一些序列(前中后序), 我們還原出一顆樹(shù)原本的樣子

Q1: 如果我們只知道前序，中序，后序中的某一種，能否構建出一棵二叉樹(shù)？如果能，為什么？如果不能，試著(zhù)舉出反例。
答： 能構建一顆二叉樹(shù), 但是不能構建出一顆唯一的二叉樹(shù)

Q2:如果我們只知道前序，中序，后序中的某兩種，能否構建出一棵唯一的二叉樹(shù)？如果能，為什么？如果不能，試著(zhù)舉出反例。

前序 + 中序 可以–> 前序可以確定根節點(diǎn), 中序可以根據根節點(diǎn)劃分左右子樹(shù)
后序 + 中序 可以–> 后序可以確定根節點(diǎn), 中序可以根據根節點(diǎn)劃分左右子樹(shù)
前序 + 后序, 不可以, 都只能確定根節點(diǎn)

二、BST(二叉查找樹(shù), 二分查找樹(shù), 二叉排序樹(shù))

就是在二叉樹(shù)的基礎上增減一個(gè)限定條件: 對樹(shù)中每一個(gè)結點(diǎn) 它的左子樹(shù)的結點(diǎn)比這個(gè)結點(diǎn)都小, 右子樹(shù)上的結點(diǎn)比這個(gè)結點(diǎn)都大

2.1 代碼實(shí)現

注意: 遞歸需要注意的事情

1, 遞歸的核心思想: 設計的時(shí)候不要考慮開(kāi)始和結束是怎么回事, 抓住核心邏輯, 局部樣本
2, 注意出口問(wèn)題: 遞歸要有出口
3, 如果實(shí)現一個(gè)遞歸方法, 不要讓這個(gè)方法被外界直接訪(fǎng)問(wèn)(沒(méi)有語(yǔ)法問(wèn)題, 只不過(guò)操作行為比較危險)
4, 一定要注意問(wèn)題規模。

/**
 * @author: Mr.Du
 * @description: 二叉搜索樹(shù)
 * @date: 2021/05/04 17:00
 */
public class MyBSTree<T extends Comparable<T>> {

    private Node root;//二叉搜索樹(shù)根節點(diǎn)
    private int size;//二叉搜索樹(shù)結點(diǎn)個(gè)數

    //添加結點(diǎn)
    public boolean add(T value) {
        // 對于一個(gè)二叉搜索樹(shù)來(lái)講我們不存儲null: null不能比較大小
        if (value == null)
            throw new IllegalArgumentException("The param is null");
        //判斷原本的樹(shù)是否為空
        if (root == null) {
            // 如果原本的樹(shù)是一個(gè)空樹(shù), 那么這個(gè)添加的元素就是根節點(diǎn)
            root = new Node(value, null, null);
            size++;
            return true;
        }

        //目前來(lái)看，樹(shù)不空，值也不是null
        Node index = root;//比較結點(diǎn)
        Node indexF = null;//比較結點(diǎn)的父結點(diǎn)
        int com = 0;//比較value大小結果
        while (index != null) {
            // 把要存儲的值, 和遍歷結點(diǎn)作比較, 進(jìn)一步確定相對于mid存儲的位置
            com = index.value.compareTo(value);
            indexF = index;
            if (com > 0) {
                index = index.left;
            } else if (com < 0) {
                index = index.right;
            } else {
                // com = 0
                // value 和 index存儲的值一樣
                // 對于重復元素的處理方式
                //       理論上:
                //                1, 計數法:  對于每一個(gè)結點(diǎn)都額外維護一個(gè)參數, 記錄這個(gè)元素的重復數量
                //                2, 拉鏈法: 在某個(gè)結點(diǎn)位置維護一個(gè)鏈表, 用一個(gè)鏈表代表一個(gè)結點(diǎn)
                //                3, 修正的BST: 如果比較的過(guò)程中發(fā)現了重復元素, 向左存儲
                //       實(shí)際上:
                //             不讓存
                return false;
            }
        }

        if (com > 0) {
            indexF.left = new Node(value, null, null);
        } else {
            indexF.right = new Node(value, null, null);
        }
        size++;
        return true;
    }

    //是否存在指定值
    public boolean contains(T value) {
        // 對于一個(gè)二叉搜索樹(shù)來(lái)講我們不存儲null: null不能比較大小
        if (value == null)
            throw new IllegalArgumentException("The param is null");

        Node index = root;
        int com = 0;
        while (index != null) {
            com = value.compareTo(index.value);
            if (com > 0) {
                index = index.right;
            } else if (com < 0) {
                index = index.left;
            } else return true;
        }
        //如果代碼走到這個(gè)位置, 意味著(zhù)上述循環(huán)跳出條件是: index == null 意味著(zhù)沒(méi)有這個(gè)元素
        return false;
    }
    //遞歸方法刪除二叉搜索樹(shù)結點(diǎn)
    public boolean removeByRecursive(T value){
        int oldSize = size;
        root = removeByRe(root,value);
        return size<oldSize;
    }
    // 實(shí)現以root為根節點(diǎn)的子樹(shù)上刪除值為value的結點(diǎn)
    private Node removeByRe(Node root,T value){
        if (root == null) return null;
        int com = value.compareTo(root.value);
        if (com>0){
            //如果value存在, 在right子樹(shù)上
            root.right = removeByRe(root.right,value);
            return root;
        }else if (com<0){
            //如果value存在, 在left子樹(shù)上
            root.left = removeByRe(root.left,value);
            return root;
        }else{
            // 找到了要刪除的結點(diǎn)
            if (root.left!=null&&root.right!=null){
                // 刪除的結點(diǎn)是雙分支結點(diǎn)
                // 獲取right子樹(shù)的最小值
                Node rightMin = root.right;
                while (rightMin.left!=null){
                    rightMin = rightMin.left;
                }
                //替換
                root.value = rightMin.value;
                // 接下來(lái), 去right子樹(shù)上刪除rightMin(此時(shí)rightMin一定不是雙分支結點(diǎn))
                // 遞歸調用刪除方法, 在這個(gè)root的right子樹(shù)上刪除這個(gè)替換值
                root.right = removeByRe(root.right,root.value);
                return root;
            }
            // 刪除的是葉子或者單分支
            Node node = root.left != null? root.left : root.right;
            size--;
            return node;
        }
    }
    //非遞歸方法刪除二叉搜索樹(shù)結點(diǎn)
    public boolean removeByNonRecursive(T value) {
        //不存儲null: null不能比較大小
        if (value == null)
            throw new IllegalArgumentException("The param is null");
        /*
        思路:
            先找到要刪除的結點(diǎn)
            判斷要刪除的結點(diǎn)是不是雙分支: 如果是雙分支, 先替換
            刪除單分支或者葉子
         */
        Node index = root;
        Node indexF = null;
        int com;
        while (index != null) {
            com = value.compareTo(index.value);
            if (com > 0) {
                indexF = index;
                index = index.right;
            } else if (com < 0) {
                indexF = index;
                index = index.left;
            } else
                break;
        }
        // indexF 是要刪除結點(diǎn)的父結點(diǎn)
        // index 是找到的要刪除的結點(diǎn)

        //如果index是null,沒(méi)有包含刪除的元素，返回false
        if (index == null)
            return false;

        //到這里，說(shuō)明包含需要刪除的元素
        if (index.left != null && index.right != null) {
            //去right子樹(shù)找一個(gè)最小值, 替換這個(gè)刪除結點(diǎn)
            Node rightMin = index.right;
            //替換結點(diǎn)的父結點(diǎn)
            Node rightMinF = index;
            //找index.right子樹(shù)的最小值, 最left的元素
            while (rightMin.left != null) {
                rightMinF = rightMin;
                rightMin = rightMinF.left;
            }

            //到達這里：rightMin.left=null
            //用查找的right子樹(shù)上的最小值, 替換這個(gè)要刪除的雙分支結點(diǎn)
            index.value = rightMin.value;
            //將替換結點(diǎn)設置為后面需要刪除的單分支結點(diǎn)
            indexF = rightMinF;
            index = rightMin;
        }

        // 有可能原本就是葉子或者單分支
        // 也有可能雙分支已經(jīng)替換了, 現在要刪除的是哪個(gè)替換了的, 葉子或者單分支

        // 必定是個(gè)葉子或者單分支: index
        // 同時(shí)我們還記錄了index 的 父結點(diǎn) indexF

        //尋找index的兒子結點(diǎn)ch:
        // 如果index是葉子 ,那么ch = null
        // 如果index是單分支, ch = 不為null單分支子結點(diǎn)
        Node ch = index.left != null ? index.left : index.right;

        // 如果刪除的是根節點(diǎn), 并且根節點(diǎn)還是個(gè)單分支的結點(diǎn), 對于上述代碼會(huì )導致midF = null
        if (indexF == null) {
            root = ch;
            size--;
            return true;
        }

        //刪除結點(diǎn)
        if (indexF.left == index) {
            indexF.left = ch;
        } else
            indexF.right = ch;
        size--;
        return true;
    }

    //用棧來(lái)實(shí)現先中后序遍歷：
    //①先序
    public List<T> preOrder() {
        //保存遍歷結果
        List<T> list = new ArrayList<>();
        //用棧來(lái)臨時(shí)存儲結點(diǎn)
        MyLinkedStack<Node> stack = new MyLinkedStack<>();
        //根節點(diǎn)入棧
        stack.push(root);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            list.add(pop.value);
            if (pop.right != null)
                stack.push(pop.right);
            if (pop.left != null)
                stack.push(pop.left);
        }
        return list;
    }

    //②中序
    public List<T> inOrder() {
        Stack<Node> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        Node index = root;
        while (index != null || !stack.empty()) {
            while (index != null) {
                stack.push(index);
                index = index.left;
            }
            Node pop = stack.pop();
            list.add(pop.value);
            index = pop.right;
        }
        return list;
    }

    //③后序
    public List<T> postOrder() {
        Stack<Node> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        stack.push(root);
        while (!stack.empty()) {
            Node pop = stack.pop();
            list.add(0, pop.value);
            if (pop.left != null)
                stack.push(pop.left);
            if (pop.right != null)
                stack.push(pop.right);
        }
        return list;
    }

    //用遞歸來(lái)實(shí)現先中后序遍歷
    //①先序
    public List<T> preOrderRecursive() {
        List<T> list = new LinkedList<>();
        preRecursive(list, root);
        return list;
    }

    // 先序：根 左 右
    private void preRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        list.add(node.value);
        preRecursive(list, node.left);
        preRecursive(list, node.right);
    }

    //②中序
    public List<T> inOrderRecursive() {
        List<T> list = new LinkedList<>();
        inRecursive(list, root);
        return list;
    }

    // 中序遍歷： 左 根 右
    private void inRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        inRecursive(list, node.left);
        list.add(node.value);
        inRecursive(list, node.right);
    }

    //③ 后序遍歷
    public List<T> postOrderRecursive() {
        List<T> list = new LinkedList<>();
        postRecursive(list, root);
        return list;
    }

    // 后序： 左 右 根
    private void postRecursive(List<T> list, Node node) {
        if (node == null)
            return;
        preRecursive(list, node.left);
        preRecursive(list, node.right);
        list.add(node.value);
    }

    // 層級： 廣度優(yōu)先搜索(BFS)
    public List<T> levOrder() {
        List<T> list = new ArrayList<>();
        Queue<Node> queue = new LinkedBlockingQueue<>();

        //根節點(diǎn)入隊列
        queue.offer(root);
        while (!queue.isEmpty()) {
            //出隊列元素
            Node poll = queue.poll();
            //遍歷
            list.add(poll.value);
            //把出隊列元素的左右子節點(diǎn)入隊列
            if (poll.left != null)
                queue.offer(poll.left);
            if (poll.right != null)
                queue.offer(poll.right);
        }
        return list;
    }


    //  建樹(shù): 給定前中序, 或者給定中后序,  構建出一棵二叉樹(shù)


    //  中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //  后序 [-20, -25, -50, -10, -5, 7, 2, 25, 30, 100, 10, 1]
    public Node buildTreeByInAndPostOrder(List<T> inOrder, List<T> postOrder) {
        Node treeRoot = buildTreeByInAndPostOrder2(inOrder, postOrder);
        return treeRoot;
    }

    private Node buildTreeByInAndPostOrder2(List<T> inOrder, List<T> postOrder) {
        if (inOrder.size() == 0) return null;
        if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);
        //找根結點(diǎn): 后序的最后一個(gè)元素
        T rootValue = postOrder.get(postOrder.size() - 1);
        //獲得根節點(diǎn)在中序的位置
        int rootAtInOrderIndex = inOrder.indexOf(rootValue);

        // 左子樹(shù)的中序(中序中切割): 0 ~ rootAtInOrderIndex-1
        // 左子樹(shù)的后序(后序中切割): 0 ~ rootAtInOrderIndex -1

        // 右子樹(shù)的中序(中序中切割): rootAtInOrderIndex + 1 ~ size -1
        // 右子樹(shù)的后序(后序中切割): rootAtInOrderIndex ~ size - 2

        //左子樹(shù)
        //subList()：左閉右開(kāi)
        List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
        List<T> leftPostOrder = postOrder.subList(0, rootAtInOrderIndex);

        //右子樹(shù)
        //subList()：左閉右開(kāi)
        List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex + 1, inOrder.size());
        List<T> rightPostOrder = postOrder.subList(rootAtInOrderIndex, postOrder.size() - 1);
        //構建這次遞歸的根節點(diǎn)
        Node node = new Node(rootValue, null, null);
        // 用遞歸方法處理, 獲得左子樹(shù)
        node.left = buildTreeByInAndPostOrder2(leftInOrder, leftPostOrder);
        // 用遞歸方法處理, 獲得右子樹(shù)
        node.right = buildTreeByInAndPostOrder2(rightInOrder, rightPostOrder);

        return node;
    }

    //  中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //  前序 1  -5  -10  -50  -25  -20   10  2  7  100  30  25
    public Node buildTreeByInAndPreOrder(List<T> inOrder, List<T> preOrder) {
        Node treeRoot = buildTreeByInAndPreOrder2(inOrder, preOrder);
        return treeRoot;
    }

    private Node buildTreeByInAndPreOrder2(List<T> inOrder, List<T> preOrder) {
        if (inOrder.size() == 0) return null;
        if (inOrder.size() == 1) return new Node(inOrder.get(0), null, null);

        T rootValue = preOrder.get(0);
        int rootAtInOrderIndex = inOrder.indexOf(rootValue);

        //左子樹(shù)
        //subList()：左閉右開(kāi)
        List<T> leftInOrder = inOrder.subList(0, rootAtInOrderIndex);
        List<T> leftPreOrder = preOrder.subList(1, rootAtInOrderIndex + 1);
        //右子樹(shù)
        //subList()：左閉右開(kāi)
        List<T> rightInOrder = inOrder.subList(rootAtInOrderIndex+1,inOrder.size());
        List<T> rightPreOrder = preOrder.subList(rootAtInOrderIndex+1,preOrder.size());

        Node node = new Node(rootValue,null,null);
        node.left = buildTreeByInAndPreOrder2(leftInOrder,leftPreOrder);
        node.right = buildTreeByInAndPreOrder2(rightInOrder,rightPreOrder);
        return node;
    }

    //判空
    public boolean isEmpty() {
        return size == 0;
    }

    //返回結點(diǎn)個(gè)數
    public int size() {
        return size;
    }

    class Node {
        T value;
        Node left;
        Node right;

        public Node(T value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

到此這篇關(guān)于Java數據結構學(xué)習之樹(shù)的文章就介紹到這了,更多相關(guān)Java樹(shù)內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！