二叉樹基本概念講解及創建
時間：2018-08-16 來源：未(wei)知
一、簡介
世界(jie)上的(de)(de)(de)樹有千萬種，我(wo)(wo)們(men)這里來(lai)學(xue)習(xi)我(wo)(wo)們(men)數(shu)據結(jie)(jie)(jie)構(gou)中的(de)(de)(de)樹，它是(shi)(shi)我(wo)(wo)們(men)現(xian)實生活中倒置的(de)(de)(de)樹。之(zhi)前，我(wo)(wo)們(men)學(xue)習(xi)的(de)(de)(de)順序表，鏈表，棧、和(he)隊列。可以說都是(shi)(shi)我(wo)(wo)們(men)的(de)(de)(de)線性結(jie)(jie)(jie)構(gou)，也就是(shi)(shi)我(wo)(wo)們(men)所謂的(de)(de)(de)一對(dui)一的(de)(de)(de)結(jie)(jie)(jie)構(gou)，可是(shi)(shi)現(xian)實生活中，我(wo)(wo)們(men)經常(chang)碰到是(shi)(shi)我(wo)(wo)們(men)一對(dui)多(duo)的(de)(de)(de)情況。今天，我(wo)(wo)們(men)就來(lai)研究一下這種一對(dui)多(duo)的(de)(de)(de)數(shu)據結(jie)(jie)(jie)構(gou)體-----“樹”。那么，什么叫做樹呢？
二(er)、樹的(de)基本(ben)概念簡(jian)介
<1>樹(shu)的定義
專業定義(yi)：(1)有(you)且只有(you)一個稱為根的結點
(2)有若干(gan)不(bu)相(xiang)交的子樹(shu)(shu)，這些(xie)子樹(shu)(shu)本身也(ye)是一顆樹(shu)(shu)。
通俗講解：
(1)樹由結點和邊組成(cheng)
(2)樹中除根節點外，每一個節點都(dou)有(you)一個父結點，但(dan)是 可以用多個子(zi)節點。
(3)根結(jie)點(dian)沒有父結(jie)點(dian)
<2>樹中的專業(ye)術(shu)語
節(jie)(jie)點 ： 父節(jie)(jie)點 子(zi)節(jie)(jie)點(老子(zi)和(he)兒子(zi)) 堂兄(xiong)弟
度(du)： 結點擁有(you)子樹的(de)個(ge)數
葉(xie)子節點：沒有子節點的節點
邊 : 一(yi)個節點到另一(yi)個節點的距離
樹的深度：節點的層(ceng)數， 根節點默(mo)認為第一層(ceng)。
有序 ：樹(shu)的左右(you)位置不(bu)能改變。
<3>樹(shu)的分類
一(yi)般樹 ： 任意一(yi)個結點(dian)的子節點(dian)的個數不(bu)受限制，則(ze)稱為一(yi)般樹。(子節點(dian)可以有(you)多(duo)個)，如下圖：
二叉樹(shu)(重點(dian)(dian))：任(ren)意(yi)一個節(jie)點(dian)(dian)的子節(jie)點(dian)(dian)的個數多有兩個，且(qie)子節(jie)點(dian)(dian)的個數不能(neng)更改。
森林：樹去掉根結點就稱之為森林。
提問：在(zai)下圖中：
<1>A,B,H,I的度分(fen)別是多少(shao)?
A:3 B : 2 H: 1 I: 0
<2>葉子節點(dian)有哪些?
K ,L,F,G,H,I,J
<3>結點(dian)F和I在樹(shu)中的第幾層?
F在第3層。
M在第4層
<4>樹的深度是(shi)多少?
4
三(san)、二叉樹的(de)特性講解
<1>二(er)叉樹的性(xing)質講解
如下(xia)圖是一顆(ke)二(er)叉樹，它有一些特性：
思考：第一層多(duo)有(you)多(duo)少個? 1個
第(di)二(er)層多(duo)有(you)多(duo)少(shao)個? 2 個
第三層多有多少個? 4 ?
規律：第i層結(jie)點后有(you)2的(de)n - 1次方(fang)個(ge)。
性質1:二叉(cha)樹的(de)第i層上的(de)結點多有(you)2的(de)i - 1次方個節點。
思考(kao)：深度為1的二叉樹(遍(bian)歷第一層)一共有(you)多少個節點? 1個
深度為2的二叉樹(遍歷(li)到第二層)一共有多少(shao)個(ge)節點(dian)? 3個(ge)
深度為(wei)3的二叉(cha)樹(遍歷到(dao)第三層(ceng))一共有(you)多少(shao)個(ge)節點? 7個(ge)
規律：深(shen)度為k的(de)而出書，多有2的(de)k次方 - 1個節點。
性質2：深度為k的二(er)叉(cha)樹多有2的k次方-1個結點(dian)。
性(xing)質3：在任意一(yi)棵(ke)二(er)叉樹中，樹葉(xie)的(de)數目比度數為2的(de)結點的(de)數目多1.
(推導過程入下圖所示：)
<2>二(er)叉(cha)樹的分(fen)類(lei)
滿(man)二叉樹(shu)：在一顆(ke)二叉樹(shu)中，如果(guo)所有的分支(zhi)節(jie)點(dian)都存在左子樹(shu)和右子樹(shu)，并且所有的葉子節(jie)點(dian)都在同一層上，這樣的二叉樹(shu)，我們稱之為(wei)滿(man)二叉樹(shu)。
滿二叉(cha)樹的特點：<1>葉子節點只(zhi)會出現(xian)在下面一層(ceng)。
<2>非葉(xie)子節點的(de)節點，擁有子樹的(de)個(ge)數一(yi)定為2.
<3>在同樣深度的二叉(cha)樹中，滿二叉(cha)樹的節點(dian)個數多。
完(wan)全二叉樹：對一顆具有(you)n個結(jie)點的二叉樹按(an)層進行編(bian)(bian)號，如果編(bian)(bian)號為(wei)i
(1 <= i <= n)的結(jie)點與(yu)同樣深(shen)度的滿二叉(cha)樹節點編號為i的結(jie)點
在二叉樹中的位置完(wan)(wan)全相同，則這(zhe)顆樹，我們稱之為(wei)完(wan)(wan)全二叉樹。
如下圖所示。
提問(wen)：下面這些樹(shu)(shu)，是完全二(er)叉樹(shu)(shu)嗎? 不是
總結：滿二叉樹一定(ding)是完(wan)全(quan)(quan)二叉樹，完(wan)全(quan)(quan)二叉樹不一定(ding)是滿二叉樹。
四、二叉樹的存儲(chu)
(1)順序存儲[完全二叉樹]
(順序存儲(chu)的話，若(ruo)不是完全(quan)二叉樹(shu)存儲(chu)沒有意(yi)義。)
假設下面(mian)有一顆(ke)樹，我們如何(he)把它存到(dao)數組中呢?
思路：先把轉換(huan)成完(wan)全二叉樹，然后再編(bian)號。
這樣存儲就(jiu)看(kan)似沒(mei)有什么(me)問題。我們可以(yi)按照(zhao)編號(hao)把數據存儲到數組中(zhong)，我們按照(zhao)編號(hao)(1,2,3,4,5)的(de)順序(xu)存儲就(jiu)可以(yi)了啊!這個時候，我就(jiu)要(yao)問了，假(jia)說說，我們的(de)m的(de)編號(hao)，你(ni)怎么(me)知(zhi)道我們的(de)3好位(wei)置是在(zai)下(xia)面，而不(bu)是在(zai)我們的(de)m編號(hao)的(de)位(wei)置呢?我們的(de)連(lian)續存儲無法(fa)識別(bie)。(這種方(fang)法(fa)，我們無法(fa)推斷樹(shu)的(de)結構)。
因此，我(wo)們順序存儲規定(ding)：
無(wu)論是何種(zhong)樹(shu)，我們(men)都會(hui)轉換成(cheng)完(wan)全(quan)二叉樹(shu)。然后一層一層的從左(zuo)給我們(men)的二叉樹(shu)進行(xing)編號，然后存儲在數組(zu)中。及如(ru)下圖。
那么我們(men)以(yi)上的存儲有什么規律呢?假設某個節點為i的話，我們(men)來觀察(cha)一(yi)下(xia)。
是不是所(suo)有(you)的左(zuo)孩子(zi)(zi)都是偶數(shu)，所(suo)有(you)的右(you)孩子(zi)(zi)都是奇數(shu)啊！
完全二(er)叉樹的特點：
對于編號為i(i>=1)的結點：
(1)左(zuo)孩(hai)子(zi)存在：2 * i <= n(節點(dian)的個數)，左(zuo)孩(hai)子(zi)編號
(2)右孩子存儲：2 * i + 1 <= n,右孩子編(bian)號 2 * i + 1
(2)鏈式存(cun)儲[完全二叉樹]
鏈(lian)式存儲：定義(yi)結點保存左孩子和右孩子的地址。
思考(kao)：上述過程，我們的(de)二叉樹應(ying)該定義什(shen)么樣的(de)數據類(lei)型來保存結點呢？
<4>二(er)叉樹的遍歷
(1)層(ceng)次遍(bian)歷(li):從上到(dao)下一(yi)層(ceng)一(yi)層(ceng)的遍(bian)歷(li)
(2)前序遍歷(li):根 、左(左子樹(shu))、右(右子樹(shu))
(3)中序遍歷:左(zuo)(左(zuo)子(zi)樹) 、根(gen) 、右(右子(zi)樹)
(4)后序遍歷:左(左子樹)、右(you)(右(you)子樹)、根
規則(ze)：遇(yu)到(dao)根(gen)結點則(ze)輸出，否則(ze)遍歷。
層次遍歷：ABCDEFGHI
先(xian)序遍歷：ABDGHCEIF
中序遍歷：GDHBAEICF
后(hou)序遍歷：GHDBIEFCA
完(wan)全二(er)叉樹的(de)遞歸(gui)創建思路：
1.首先(xian)，寫一(yi)個(ge)創建單個(ge)節(jie)點的函數malloc_bnode，左孩(hai)子和右(you)孩(hai)子都為空(kong)并且填充，我們需要的數據(ju)
2.然后寫一個創建二叉樹的(de)函數create_binarytree()函數。調用malloc_bond
函數創(chuang)建節點(dian)，然后判斷結點(dian)有(you)沒有(you)左孩子和右孩子。
2 *num <= n ，左孩子(zi)存在 (num為我(wo)們的結點(dian)編號(hao)，n為我(wo)們的結點(dian)個數)
再次，調用(yong)create_binarytree()創(chuang)建該編號的孩子。
2 *num + 1 <=n,右孩子存儲。
再(zai)次，調(diao)用(yong)create_binarytree()創(chuang)建該(gai)編號的孩(hai)子，后(hou)返回(hui)根節點。
二叉樹相關文章：
