1.6 樹與二叉樹(學吧學吧獨家稿件)
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數(shù)據(jù)結構中,所有數(shù)據(jù)元素之間的關系具有明顯的層次特性。
在樹結構中,每一個結點只有一個前件,稱為父結點。沒有前件的結點只有一個,稱為樹的根結點,簡稱樹的根。每一個結點可以有多個后件,稱為該結點的子結點。沒有后件的結點稱為葉子結點。
在樹結構中,一個結點所擁有的后件的個數(shù)稱為該結點的度,所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
(1)什么是二叉樹
二叉樹是一種很有用的非線性結構,它具有以下兩個特點:1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。
*:根據(jù)二叉樹的概念可知,二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。
(2)二叉樹的基本性質(學吧學吧獨家稿件)
性質1 在二叉樹的第k層上,最多有2k-1(k≥1)
性質2 深度為m的二叉樹最多有個2m-1個結點。
性質3 在任意一棵二叉樹中,度數(shù)為0的結點(即葉子結點)總比度為2的結點多一個。
性質4 具有n個結點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分。
3、滿二叉樹與完全二叉樹
滿二叉樹:除最后一層外,每一層上的所有結點都有兩個子結點。
完全二叉樹:除最后一層外,每一層上的結點數(shù)均達到最大值;在最后一層上只缺少右邊的若干結點。
*:根據(jù)完全二叉樹的定義可得出:度為1的結點的個數(shù)為0或1。
下圖a表示的是滿二叉樹,下圖b表示的是完全二叉樹:
完全二叉樹還具有如下兩個特性:
性質5 具有n個結點的完全二叉樹深度為[log2n]+1。
性質6 設完全二叉樹共有n個結點,如果從根結點開始,按層序(每一層從左到右)用自然數(shù)1,2,…,n給結點進行編號,則對于編號為k(k=1,2,…,n)的結點有以下結論:
、偃鬹=1,則該結點為根結點,它沒有父結點;若k>1,則該結點的父結點的編號為INT(k/2)。
、谌2k≤n,則編號為k的左子結點編號為2k;否則該結點無左子結點(顯然也沒有右子結點)。
③若2k+1≤n,則編號為k的右子結點編號為2k+1;否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中,二叉樹通常采用鏈式存儲結構。
與線性鏈表類似,用于存儲二叉樹中各元素的存儲結點也由兩部分組成:數(shù)據(jù)域和指針域。但在二叉樹中,由于每一個元素可以有兩個后件(即兩個子結點),因此,用于存儲二叉樹的存儲結點的指針域有兩個:一個用于指向該結點的左子結點的存儲地址,稱為左指針域;另一個用于指向該結點的右子結點的存儲地址,稱為右指針域。
*:一般二叉樹通常采用鏈式存儲結構,對于滿二叉樹與完全二叉樹來說,可以按層序進行順序存儲[注釋1] 。
5、二叉樹的遍歷(學吧學吧獨家稿件)
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種:
(1)前序遍歷(DLR):若二叉樹為空,則結束返回。否則:首先訪問根結點,然后遍歷左子樹,最后遍歷右子樹;并且,在遍歷左右子樹時,仍然先訪問根結點,然后遍歷左子樹,最后遍歷右子樹。
(2)中序遍歷(LDR):若二叉樹為空,則結束返回。否則:首先遍歷左子樹,然后訪問根結點,最后遍歷右子樹;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪問根結點,最后遍歷右子樹。
(3)后序遍歷(LRD):若二叉樹為空,則結束返回。否則:首先遍歷左子樹,然后遍歷右子樹,最后訪問根結點,并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后遍歷右子樹,最后訪問根結點。
注釋1:這樣,不僅節(jié)省了存儲空間,又能方便地確定每一個結點的父結點與左右子結點的位置,但順序存儲結構對于一般的二叉樹不適用。
相關推薦:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內蒙古 |