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

資訊專欄INFORMATION COLUMN

Java數據結構與算法——樹(基本概念,很重要)

MangoGoing / 2412人閱讀

摘要:有網友私信我,期待我的下一篇數據結構。前言數據結構與算法專題會不定時更新,歡迎各位讀者監督。本文介紹數據結構里一些復雜的數據結構樹,相應的會補充一些算法。除根節點外,每個節點又可以分為多個不相交的子樹。

聲明:碼字不易,轉載請注明出處,歡迎文章下方討論交流。
有網友私信我,期待我的下一篇數據結構。非常榮幸文章被認可,也非常感謝你們的監督。
前言:Java數據結構與算法專題會不定時更新,歡迎各位讀者監督。本文介紹數據結構里一些復雜的數據結構——樹(Tree),相應的會補充一些算法。本篇主要介紹一些必知必會的,可能是考試中的,也可能是面試中的。
0、樹體系索引(待更)

二叉樹及操作

二叉樹的查找算法
B樹、B+樹
Huffman(哈夫曼)樹和Huffman編碼
堆(Heap)和堆排序
紅黑樹
人生苦短,學會淡定。。。
1、樹的定義及存儲結構 1.1 樹的定義

樹是一種非線性的數據結構,它是由n(n>=1)個有限節點組成的一種具有層次關系的集合,之所以稱之為樹,是因為它長得像一顆倒過來的樹。
舉個例子,每個人都有家族樹,家族樹一般長這樣:

家族樹的樣子看起來像一顆正常的樹,而數據結構中的樹則像是一顆倒過來的樹:

可以看出,一棵樹有多個節點,上圖中帶〇的字母就是一個節點。每個節點可能有0個或更多子節點,每個節點至多有一個父節點,沒有父節點的那個稱之為根節點。除根節點外,每個節點又可以分為多個不相交的子樹。

1.2 樹的相關概念術語
1)節點
樹中每個元素都叫節點
2)根節點或樹根
樹頂端的節點稱之為根節點,也叫樹根
3)子樹
除根節點之外,其他節點可以分為多個樹的集合,叫做子樹,在上圖中,K這個節點可以稱之為一顆子樹,而H、K、L三個節點組合起來也可以叫做一顆子樹
4)節點的度
一個節點直接含有的子樹的個數,稱之為節點的度。比如上圖中B節點的度為3,C節點的度是2,I、J、K、L節點的度是0
5)葉子節點、葉節點、終端節點
度為0的節點叫做葉子節點,也叫葉節點、終端節點,其實就是沒有子節點的節點,或者說沒有子樹的節點
6)雙親節點、父節點
父節點就是一個節點上頭的那個節點,如果一個節點包含若干子節點,那么這個節點就是這些子節點的父節點,也叫雙親節點
7)兄弟節點
擁有相同父節點的節點互稱為兄弟節點
8)樹的度
一棵樹中最大節點的度稱之為樹的度,即樹中哪個節點的子節點最多,那么這個節點的度也就是樹的度
9)節點的層次
從根這一層開始,根算1層,根的子節點算2層,一直到最下面一層
10)樹的高度、深度
樹的深度是從根節點開始、自頂向下逐層累加(根節點的高度是1)助記:深度從上到下
樹的高度是從葉節點開始、自底向上逐層累加(葉節點的高度是1)助記:高度由下向上
雖然樹的高度和深度一樣,但是具體到某個節點上,其高度和深度通常是不一樣的。
11)堂兄弟節點
堂兄弟節點是同一層,父節點不同,或者說雙親節點在同一層的節點稱之為堂兄弟節點
12)節點的祖先
從根節點到某一節點一路順下來的除了該節點的所有節點都是該節點的祖先節點
13)節點的子孫
以某節點為根的子樹中,任何一個節點都是其子孫,也就是說這個節點下面與這個節點有關的節點都是這個節點的子孫
14)森林
由m棵不相交的樹組成的集合,叫做森林
1.3 都有哪些樹

樹的種類有很多,我們接觸到的樹有二叉樹、平衡二叉樹、二叉查找樹、B樹、B+樹、哈夫曼樹、B*樹、紅黑樹和trie樹等。

2、樹的存儲結構及實現

樹,首先首先是由節點組成,而除根節點的每個節點一定只有一個父節點,所以可以利用每個節點只有一個父節點的特性,使用父節點來構造樹。

public class TreeNode1{
    private int data;
    private int parent;
    
    public int getData(){
        return date;
    }
    public void setData(int data){
        this.data = data;
    }
    
    public int getParent(){
        return parent;
    }
    public void setParent(int parent){
        this.parent = parent;
    }
}

這個節點有兩個屬性,一個是data,也就是這個節點的值(這個是必須有的),另一個是parent,也就是節點的父節點。

下一篇更新二叉樹,敬請期待
碼字不易,如對您有幫助,歡迎點贊收藏打賞^_^

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

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

相關文章

  • 前端該如何準備數據結構算法

    摘要:很多前端同學在看到數據結構和算法后會有一定的抵觸心理,或者嘗試去練習,但是被難倒,從而放棄。本文選擇的數據結構和算法的類別均是出現頻率最高,以及應用最廣的類別。面試這是非常現實的一點,也是很多前端學習數據結構和算法的原因。 一、導讀 據我了解,前端程序員有相當一部分對數據結構和算法的基礎概念都不是很清晰,這直接導致很多人在看到有關這部分的內容就會望而卻步。 實際上,當你了解了數據結構和...

    simon_chen 評論0 收藏0

發表評論

0條評論

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