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

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