最近重新回顧了數(shù)據(jù)結(jié)構(gòu)中的樹,樹是一種非線性數(shù)據(jù)結(jié)構(gòu)程拭，其概念也不少。大家在初次接觸樹的時(shí)候棍潘，可能覺得它很難恃鞋；之所產(chǎn)生這種感覺主要是由于樹有一大堆陌生的概念、性質(zhì)等內(nèi)容亦歉。而當(dāng)我真正的實(shí)現(xiàn)了二叉樹再回過(guò)頭來(lái)看它的相關(guān)概念和性質(zhì)的時(shí)候恤浪，覺得原來(lái)它是如此的簡(jiǎn)單！

因此肴楷，建議在學(xué)習(xí)二叉樹的時(shí)候：先對(duì)二叉樹基本的概念水由、性質(zhì)有個(gè)基本了解，遇到難懂的知識(shí)點(diǎn)赛蔫，可以畫圖來(lái)幫助理解砂客；在有個(gè)基本的概念之后直秆，再親自動(dòng)手實(shí)現(xiàn)二叉查找樹(這一點(diǎn)至關(guān)重要!)；最后再回過(guò)頭來(lái)總結(jié)一下二叉樹的理論知識(shí)時(shí)鞭盟，你會(huì)發(fā)現(xiàn)其實(shí)一點(diǎn)不難圾结！

而這一篇文章主要講各種樹的性質(zhì)和定義.

一:樹的介紹

1:樹的定義

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合齿诉，把它叫做“樹”是因?yàn)樗雌饋?lái)像一棵倒掛的樹筝野，也就是說(shuō)它是根朝上，而葉朝下的粤剧。它具有以下的特點(diǎn)：

1:每個(gè)節(jié)點(diǎn)有零個(gè)或者多個(gè)子節(jié)點(diǎn)

2:沒有父節(jié)點(diǎn)的節(jié)稱為根節(jié)點(diǎn)

3:每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)

4:除了根節(jié)點(diǎn)之外,每一個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹

2:樹的基本術(shù)語(yǔ)

若一個(gè)結(jié)點(diǎn)有子樹歇竟，那么該結(jié)點(diǎn)稱為子樹根的"雙親"，子樹的根是該結(jié)點(diǎn)的"孩子"抵恋。有相同雙親的結(jié)點(diǎn)互為"兄弟"焕议。一個(gè)結(jié)點(diǎn)的所有子樹上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先弧关，以下圖為例：

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹的數(shù)目盅安，圖中結(jié)點(diǎn)c的度為2。 葉子：度為零的結(jié)點(diǎn)世囊，圖中D别瞭、E、F都是葉子結(jié)點(diǎn) 樹的度：樹中結(jié)點(diǎn)的最大的度株憾，圖中結(jié)點(diǎn)c的度最大為2蝙寨，因此樹的度為2。

層次：根結(jié)點(diǎn)的層次為1嗤瞎，其余結(jié)點(diǎn)的層次等于該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的層次加1墙歪。 樹的高度：樹中結(jié)點(diǎn)的最大層次，圖中樹的高度為3贝奇。 無(wú)序樹：如果樹中結(jié)點(diǎn)的各子樹之間的次序是不重要的虹菲，可以交換位置。 有序樹：如果樹中結(jié)點(diǎn)的各子樹之間的次序是重要的, 不可以交換位置弃秆。 森林：0個(gè)或多個(gè)不相交的樹組成届惋。對(duì)森林加上一個(gè)根，森林即成為樹菠赚；刪去根，樹即成為森林郑藏。

二:二叉樹的介紹

1:二叉樹的定義

二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)衡查。它有五種基本形態(tài)：二叉樹可以是空集；根可以有空的左子樹或右子樹必盖；或者左拌牲、右子樹皆為空俱饿。

2:二叉樹性質(zhì)

①性質(zhì)1：二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2{i-1}(i≥1)。

證明：下面用"數(shù)學(xué)歸納法"進(jìn)行證明塌忽。 (01) 當(dāng)i=1時(shí)拍埠，第i層的節(jié)點(diǎn)數(shù)目為2{i-1}=2{0}=1，命題成立土居。

(02) 假設(shè)當(dāng)i>1枣购，第i層的節(jié)點(diǎn)數(shù)目為2{i-1}。這個(gè)是根據(jù)第一步推斷出來(lái)的擦耀！ 下面根據(jù)這個(gè)假設(shè)棉圈，推斷出"第(i+1)層的節(jié)點(diǎn)數(shù)目為2{i}"即可。由于二叉樹的每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子眷蜓，故"第(i+1)層上的結(jié)點(diǎn)數(shù)目" 最多是 "第i層的結(jié)點(diǎn)數(shù)目的2倍"分瘾。即，第(i+1)層上的結(jié)點(diǎn)數(shù)目最大值=2×2{i-1}=2{i}吁系。故假設(shè)成立铆惑，原命題得證纤房！

性質(zhì)2：深度為k的二叉樹至多有2{k}-1個(gè)結(jié)點(diǎn)(k≥1)。

證明：在具有相同深度的二叉樹中，當(dāng)每一層都含有最大結(jié)點(diǎn)數(shù)時(shí)棉饶，結(jié)點(diǎn)數(shù)最多。利用"性質(zhì)1"可知面哼，深度為k的二叉樹的結(jié)點(diǎn)數(shù)至多為：20+21+…+2k-1=2k-1歌殃。故原命題得證！

性質(zhì)3：包含n個(gè)結(jié)點(diǎn)的二叉樹的高度至少為log2(n+1)辞嗡。

證明：根據(jù)"性質(zhì)2"可知捆等，高度為h的二叉樹最多有2{h}–1個(gè)結(jié)點(diǎn)。反之续室，對(duì)于包含n個(gè)節(jié)點(diǎn)的二叉樹的高度至少為log2(n+1)栋烤。

性質(zhì)4：二叉樹中,設(shè)葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2挺狰，則n0=n2+1明郭。

證明：因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度數(shù)均不大于2，所以有等式一丰泊。

n=n0+n1+n2(等式一)

另一方面薯定，0度結(jié)點(diǎn)沒有孩子，1度結(jié)點(diǎn)有一個(gè)孩子瞳购，2度結(jié)點(diǎn)有兩個(gè)孩子话侄，故二叉樹中孩子結(jié)點(diǎn)總數(shù)是：n1+2n2。此外，只有根不是任何結(jié)點(diǎn)的孩子年堆。故二叉樹中的結(jié)點(diǎn)總數(shù)又可表示為等式二吞杭。

n=n1+2n2+1(等式二) 由(等式一)和(等式二)計(jì)算得到：n0=n2+1。原命題得證变丧！

3:不同形態(tài)的二叉樹

1:滿二叉樹

定義：高度為h芽狗，并且由2{h} –1個(gè)結(jié)點(diǎn)的二叉樹，被稱為滿二叉樹痒蓬，其實(shí)不難看出童擎，滿二叉樹的結(jié)點(diǎn)的度要么為0（葉子結(jié)點(diǎn)），要么為2（非葉子結(jié)點(diǎn)）

2:完全二叉樹

定義：一棵二叉樹中谊却，只有最下面兩層結(jié)點(diǎn)的度可以小于2柔昼，并且最下一層的葉結(jié)點(diǎn)集中在靠左的若干位置上。這樣的二叉樹稱為完全二叉樹炎辨。

特點(diǎn)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層捕透，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。顯然碴萧，一棵滿二叉樹必定是一棵完全二叉樹乙嘀，而完全二叉樹未必是滿二叉樹。

3:二叉查找樹

定義：二叉查找樹破喻，又被稱為二叉搜索樹虎谢。其特點(diǎn)如下：設(shè)x為二叉查找樹中的一個(gè)結(jié)點(diǎn)，x節(jié)點(diǎn)包含關(guān)鍵字key曹质，一句話就是左孩子比父節(jié)點(diǎn)小婴噩，右孩子比父節(jié)點(diǎn)大，還有一個(gè)特性就是”中序遍歷“可以讓結(jié)點(diǎn)有序羽德。

綜上所述,在二叉樹中:

1:若任意節(jié)點(diǎn)的左子樹不空几莽，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值

2:任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值宅静；

3:任意節(jié)點(diǎn)的左章蚣、右子樹也分別為二叉查找樹；

4:沒有鍵值相等的節(jié)點(diǎn)姨夹。

由于在實(shí)際應(yīng)用中纤垂，二叉查找樹的使用比較多，后面會(huì)有文章講解二叉查找樹的一些關(guān)鍵操作的代碼實(shí)現(xiàn)磷账。

文章轉(zhuǎn)載自公眾號(hào):碼農(nóng)有道

http://weixin.qq.com/r/w0S6os7EPpNBrYrB9xHR(二維碼自動(dòng)識(shí)別)