第13章樹（含逆波蘭表達(dá)式）知識點梳理高考信息技術(shù)二輪復(fù)習(xí)知識點梳理

第十三章樹1.樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)用它能很好的描述有分支和層次特性的數(shù)據(jù)集合2.樹可以描述為由n(n>=0)個節(jié)點（Node）構(gòu)成的一個有限集合以及在該集合上定義的一種節(jié)點關(guān)系。3.集合中的元素稱為樹的節(jié)點，n=0的樹稱為空樹；樹中某個節(jié)點下面的所有節(jié)點所構(gòu)成的樹稱為該節(jié)點的子樹。4.樹的兩個節(jié)點之間如果有一條邊連接，那么稱為這兩個節(jié)點之間存在一條邊；對于一顆具有n個節(jié)點的樹，它由n1條邊。5.如下圖：下圖中的樹中共有13個節(jié)點、12條邊、節(jié)點B、G、H構(gòu)成節(jié)點A的一顆子樹圖1.16.樹的一個節(jié)點所擁有的子樹個數(shù)稱為該節(jié)點的度，最大的節(jié)點的度稱為樹的度。如圖4.1，節(jié)點A的度為5，節(jié)點B的度為2，節(jié)點I的度為3，因此此樹的度為5。7.在樹形結(jié)構(gòu)中，沒有前驅(qū)的節(jié)點稱為根節(jié)點，又稱為開始節(jié)點（圖1.1的A節(jié)點）。8.度為0的節(jié)點稱為葉子節(jié)點，又稱為終端節(jié)點（圖1.1的G、H、C、D、K、L、M、J、F）9.樹中度不為0的節(jié)點稱為分支節(jié)點或非終端節(jié)點，除根節(jié)點外的分支節(jié)點統(tǒng)稱為內(nèi)部節(jié)點（圖1.1的B、E、I節(jié)點）10.在樹形結(jié)構(gòu)中，對于兩個以邊直接連接的節(jié)點，上端節(jié)點稱為下端節(jié)點的父節(jié)點或雙親節(jié)點。相應(yīng)的下端節(jié)點稱為上端節(jié)點的孩子節(jié)點。如圖4.1所示，節(jié)點K、L、M都是節(jié)點I的孩子節(jié)點。反過來，節(jié)點I是節(jié)點K、L、M的父節(jié)點，節(jié)點K、L、M是兄弟節(jié)點11.樹中節(jié)點的層數(shù)從根開始計算，根的層數(shù)為1，其余節(jié)點的層數(shù)等于其父節(jié)點的層數(shù)加112.樹中節(jié)點的最大層數(shù)稱為樹的高度或深度13.二叉樹是一個具有n(n>=0)個節(jié)點的有限集合；當(dāng)n=0時，二叉樹是一顆空樹；當(dāng)n!=0是，則是一顆由根節(jié)點和兩顆互不相交的分別稱為這個根節(jié)點的左子樹和右子樹組成的二叉樹，由于左、右子樹也是二叉樹，因此子樹也可以是空樹。14二叉樹的分類如下圖：從左到右分別是為1.空二叉樹、2.只有根節(jié)點的單點樹、3.只有根節(jié)點和左子樹、4.只有根節(jié)點和右節(jié)點、5.有根節(jié)點和左右子樹圖1.214.完全二叉樹:這一類二叉樹至多只有最下面兩層中的節(jié)點度數(shù)小于2，且最下面一層的葉子節(jié)點都依次排列在該層的最左邊位置。如下圖：圖1.315.二叉樹的性質(zhì)如下：（1）二叉樹的第k層上最多有2k–1（k≥1）個節(jié)點。（2）深度為k的二叉樹最多有2k–1（k≥1）個節(jié)點。（3）在任意一棵二叉樹中，若度為2的節(jié)點數(shù)量為n2，葉子節(jié)點（度為0的節(jié)點）數(shù)為n0，則n0=n2+1。16.二叉樹的遍歷：二叉樹的遍歷根據(jù)根節(jié)點的訪問順序，可以分為前序遍歷、中序遍歷、后序遍歷。17.前序遍歷規(guī)則：先訪問根節(jié)點，再訪問左子樹，最后訪問右子樹。如下圖1.4：最后訪問順序為：ABDHECFIGJK18.中序遍歷規(guī)則：先訪問左子樹，再訪問根節(jié)點，最后訪問右子樹。如下圖1.5：最后訪問順序為：DHBEAIFCJGK19.后序遍歷規(guī)則：先訪問左子樹，再訪問右子樹，最后訪問根節(jié)點。如下圖1.6：最后訪問順序為：HDEBIFJKGCA圖1.4圖1.5圖1.6逆波蘭表達(dá)式：逆波蘭式是一種將待計算量寫在前,把運算符寫在后（通常是兩數(shù)之后）的計算式，比如：中序表達(dá)式逆波蘭表達(dá)式A+BAB+A*BAB*A+B*CABC*+A*(B+C)ABC+*表1.1逆波蘭表達(dá)式可以通過棧、叉樹等數(shù)據(jù)結(jié)構(gòu)存儲，其中二叉樹用的較多，通過二叉樹存儲通過前序、中序、后序遍歷中的其中一種方法，可以遍歷出一個