簡單了解二叉樹,Java高級開發技術

隔壁的老郭 2021-09-18 07:02:55 阅读数:562

了解 二叉 java

1.一棵二叉樹是結點的一個有限集合,該集合或者為空,或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉

樹組成。

2.二叉樹的特點:

2.1. 每個結點最多有兩棵子樹,即二叉樹不存在度大於 2 的結點。

2.2. 二叉樹的子樹有左右之分,其子樹的次序不能顛倒,因此二叉樹是有序樹。

3.1二叉樹的形式

而所有的二叉樹都離不開這幾種基本形態

簡單了解二叉樹,Java高級開發技術_Java

3.2兩種特殊的二叉樹——滿二叉樹和完全二叉樹

注:滿二叉樹是完全二叉樹的一種特殊形式

  1. 滿二叉樹: 一個二叉樹,如果每一個層的結點數都達到最大值,則這個二叉樹就是滿二叉樹。也就是說,如果一個二叉樹的層數為K,且結點總數是 ,則它就是滿二叉樹。

    如圖:

    簡單了解二叉樹,Java高級開發技術_後端_02

  2. 完全二叉樹: 完全二叉樹是效率很高的數據結構,完全二叉樹是由滿二叉樹而引出來的。對於深度為K的,有n個結點的二叉樹,當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹

    如圖:

簡單了解二叉樹,Java高級開發技術_後端_03

但是下面幾種情况是二叉樹但不是完全二叉樹(列舉兩例)

簡單了解二叉樹,Java高級開發技術_程序員_04

2.簡單了解二叉樹,Java高級開發技術_程序員_05

4.二叉樹的性質(重點)

  1. 若規定根節點的層數為1,則一棵非空二叉樹的第i層上最多有2^(i-1) (i>0)個結點

  2. 若規定只有根節點的二叉樹的深度為1,則深度為K的二叉樹的最大結點數是2^k-1 (k>=0)

  3. 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n0,則有n0=n1+1

  4. 具有n個結點的完全二叉樹的深度k為 上取整

  5. 對於具有n個結點的完全二叉樹,如果按照從上至下從左至右的順序對所有節點從0開始編號,則對於序號為i的結點有:

    5.1若i>0,雙親序號:(i-1)/2;i=0,i為根節點編號,無雙親節點

    5.2若2i+1<n,左孩子序號:2i+1,否則無左孩子

    5.3若2i+2<n,右孩子序號:2i+2,否則無右孩子

    下圖有具體說明

    簡單了解二叉樹,Java高級開發技術_後端_06

    舉例說明

總結

大型分布式系統猶如一個生命,系統中各個服務猶如骨骼,其中的數據猶如血液,而Kafka猶如經絡,串聯整個系統。這份Kafka源碼筆記通過大量的設計圖展示、代碼分析、示例分享,把Kafka的實現脈絡展示在讀者面前,幫助讀者更好地研讀Kafka代碼。

 CodeChina開源項目:【一線大廠Java面試題解析+核心總結學習筆記+最新講解視頻】

麻煩幫忙轉發一下這篇文章+關注我

簡單了解二叉樹,Java高級開發技術_後端_07

版权声明:本文为[隔壁的老郭]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210918070254646Z.html