国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數據結構與算法——二叉樹(下)

Awbeci / 1467人閱讀

摘要:所以,如果中序遍歷二叉搜索樹,會得到一個有序的數據,時間復雜度是,所以二叉搜索樹又叫做二叉排序樹。所以,我們需要一種方式來維持二叉樹的平衡,最好是將其維持為滿二叉樹或者完全二叉樹,這就是后面會說到的平衡二叉查找樹,常見的有樹,紅黑樹。

1. 概述

前面的文章說到了二叉樹,其實今天講的二叉搜索(查找)樹就是二叉樹最常用的一種形式,它支持高效的查找、插入、刪除操作,它的定義是這樣的:對于樹中的任意一個節點,其左子節點值必須小于該節點,其右子節點必須大于該節點。例如下圖中的幾種樹都是二叉查找樹:

2. 二叉搜索樹的查找

我們直接拿查找的數據和根節點數據作比較,如果大于根節點,則在右子樹中遞歸查找,如果小于根節點,則在左子樹中查找,如果等于,則直接返回。就像下圖的查找過程:

結合代碼能夠更直觀的理解:

public class BinaryTree {
    private Node head = null;//樹的根節點
    //1.查找節點
    public Node find(int value){
        Node p = head;
        while (p != null){
            if (p.getData() > value) p = p.left;
            else if (p.getData() < value) p = p.right;
            else return p;
        }
        return null;
    }
    //定義樹的節點
    public static class Node{
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }

        public int getData() {
            return data;
        }
    }
}
3. 二叉搜索樹的插入

插入操作和查找其實比較的類似,都是需要拿插入的數據和樹中的數據進行比較,如果插入的數據大于樹節點數據,并且節點的右子樹為空,則直接插入到右子樹,否則繼續在右子樹中遞歸查找位置;如果插入的數據小于樹節點數據,并且節點的左子樹為空,則直接插入到左子樹,否則繼續在左子樹中遞歸查找位置。

結合代碼理解一下:

 public void insert(int value){
        Node node = new Node(value);
        if (head == null){
            head = node;
            return;
        }
        Node p = head;
        while (p != null){
            if (p.getData() > value){
                if (p.left == null) {
                    p.left = node;
                    return;
                }
                p = p.left;
            }
            else {
                if (p.right == null) {
                    p.right = node;
                    return;
                }
                p = p.right;
            }
        }
    }
4. 二叉搜索樹的刪除

前面的查找和插入操作都比較的簡單易懂,但是二叉搜索樹的刪除操作就比較的復雜了,分為了幾種情況。

第一種情況:要刪除的節點沒有子節點,這樣的話,可以直接將指向該節點的父節點指針設為 null。

第二種情況:要刪除的節點只有一個子節點,直接將該節點的父節點的指針,指向該節點的子節點即可。

第三種情況:要刪除的節點有兩個子節點,我們需要在刪除節點的右子樹中,尋找到最小的那個節點,然后將其放在刪除的節點的位置上。

三種情況對應下圖:

結合代碼來理解一下:

    //3.刪除數據
    public void delete(int value){
        Node p = head;
        Node pParent = null;//p節點的父節點

        //先找到這個節點
        while (p != null && p.getData() != value){
            pParent = p;
            if (p.getData() > value)p = p.left;
            else p = p.right;
        }
        if (p == null) return;//表示沒有找到值為value的節點

        //1.假如要刪除的節點有兩個子節點
        if (p.left != null && p.right != null){
            //查找p節點的右子節點中的最小值
            Node minP = p.right;
            Node minPP = p;//minPP表示minP的父節點
            while (minP.left != null){
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.getData();
            if (minPP == p) p.right = null;
            else minPP.left = null;
            return;
        }

        //2.假如刪除的節點p是葉子節點或只有一個子節點
        Node child = null;
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;

        if (pParent == null) head = child;
        else if (pParent.left == p) pParent.left = child;
        else pParent.right = child;
    }
5. 二叉搜索樹分析

最后,還有兩個需要說明一下,前面說到了二叉樹的三種遍歷方式,其中,中序遍歷的方式是先遍歷節點的左子節點,再遍歷這個節點本身,然后遍歷節點的右子節點。所以,如果中序遍歷二叉搜索樹,會得到一個有序的數據,時間復雜度是 O(n),所以二叉搜索樹又叫做二叉排序樹

在理想的情況下,我們的二叉樹是一棵滿二叉樹或者完全二叉樹,那么查找、插入、刪除操作十分的高效,時間復雜度是 O(logn),但是,如果二叉樹的左右子樹非常的不平衡,極端的情況下,可能會退化為鏈表,那么性能就下降了。

所以,我們需要一種方式來維持二叉樹的平衡,最好是將其維持為滿二叉樹或者完全二叉樹,這就是后面會說到的平衡二叉查找樹,常見的有 AVL 樹,紅黑樹。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74019.html

相關文章

  • 數據結構算法:叉樹算法

    摘要:因此,根據題目給出的先序遍歷和中序遍歷,可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題 內容銜接上一章 數據結構與算法:常見排序算法 內容提要 什么是樹   - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 B、B+樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

    Little_XM 評論0 收藏0
  • 數據結構算法——叉樹(上)

    摘要:什么是樹前面說到的幾種數據結構都是線性的,例如鏈表棧隊列等,今天就來學習一種非線性的數據結構樹。在上圖中的幾種二叉樹中,有兩個是比較特殊的,分別是滿二叉樹和完全二叉樹。除了使用數組存儲二叉樹外,最常用的便是使用鏈表法來儲存二叉樹了。 1. 什么是樹? 前面說到的幾種數據結構都是線性的,例如鏈表、棧、隊列等,今天就來學習一種非線性的數據結構——樹。先來看看幾種樹的結構: showImg(...

    xeblog 評論0 收藏0
  • Javascript 數據結構算法——叉樹

    摘要:一個節點可以有多個子節點二叉樹二叉樹是一種特殊的樹,子節點數不超過個。以某種特定的順序訪問樹中所有的節點稱為樹的遍歷樹的層數稱為樹的深度一個父節點的兩個子節點分別稱為左節點和右節點二叉查找樹又稱二叉排序樹是一種特殊的二叉樹。 原文地址:http://www.brandhuang.com/article/1564967352592 1、樹 一棵樹最上面的節點:根結點 一個節點下面連接多個...

    shengguo 評論0 收藏0
  • Java數據結構算法——叉樹及操作(包括叉樹遍歷)

    摘要:本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度,可能是考試中的,也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。 聲明:碼字不易,轉載請注明出處,歡迎文章下方討論交流。 前言:Java數據結構與算法專題會不定時更新,歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作(三種遍歷...

    muddyway 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<