數(shù)據(jù)結(jié)構(gòu)+二叉樹及遍歷+課件

目標在本章中，你將學(xué)習(xí)：在樹中存儲數(shù)據(jù)實現(xiàn)二叉樹實現(xiàn)二叉搜索樹.在樹中存儲數(shù)據(jù)假設(shè)你被要求呈現(xiàn)操作系統(tǒng)的目錄結(jié)構(gòu)。目錄結(jié)構(gòu)含有不同的文件夾和文件。一個文件夾可能含有更多的子文件夾和文件。在這種情況下，要用線型結(jié)構(gòu)來表示這種結(jié)構(gòu)幾乎是不可能的，因為所有的項目之間都有層級關(guān)系。要表示這樣的結(jié)構(gòu)，就需要一種非線型的數(shù)據(jù)存儲機制。.一個樹結(jié)構(gòu)就是以非線型結(jié)構(gòu)來表示不同數(shù)據(jù)元素之間的層級關(guān)系的數(shù)據(jù)結(jié)構(gòu)。ABCDIJHKGLMFE定義樹結(jié)構(gòu)樹被應(yīng)用于數(shù)據(jù)元素之間的關(guān)系以層級關(guān)系來表示的應(yīng)用程序中。.每個樹結(jié)構(gòu)中的數(shù)據(jù)元素都被稱為一個節(jié)點。最頂層的節(jié)點被稱為根（root）。root定義樹結(jié)構(gòu)（續(xù)）nodeABCDIJHKGLMFE.樹中的每一個節(jié)點在其層級下可能有子樹。root定義樹結(jié)構(gòu)（續(xù)）nodeABCDIJHKGLMFE.樹結(jié)構(gòu)術(shù)語葉子節(jié)點：指沒有子節(jié)點的節(jié)點。節(jié)點E,F,G,H,I,J,L,和M是葉子節(jié)點。ABCDIJHKGLMFE讓我們來討論樹結(jié)構(gòu)常用的一些術(shù)語。.子樹：是樹結(jié)構(gòu)的一部分，但它本身也可被看作一個樹結(jié)構(gòu)，這就是子樹。

子樹也可以含有葉子節(jié)點。子節(jié)點：一個樹結(jié)構(gòu)中子樹的根節(jié)點被稱為子節(jié)點。

樹結(jié)構(gòu)術(shù)語（續(xù)）有根B的樹結(jié)構(gòu)包含節(jié)點E、F、G和H，此樹是節(jié)點A的子樹。

E,F,G和H是B節(jié)點的子節(jié)點。B是這些節(jié)點的父節(jié)點。ABCDIJHKGLMFE.節(jié)點的度：它指樹結(jié)構(gòu)中一個節(jié)點的子樹的數(shù)量。樹結(jié)構(gòu)術(shù)語（續(xù)）C節(jié)點的度為1D節(jié)點的度為2A節(jié)點的度為3B節(jié)點的度為4ABCDIJHKGLMFE邊：從父節(jié)點到子節(jié)點的連接被稱為一個邊。Edge.B、C和D節(jié)點互為兄弟節(jié)點。E、F、G和H互為兄弟節(jié)點。兄弟：它指同一個節(jié)點的子節(jié)點。樹結(jié)構(gòu)術(shù)語（續(xù)）ABCDIJHKGLMFE.節(jié)點的層級：它指一個節(jié)點與根節(jié)點之間的距離（按節(jié)點數(shù)目計算）。根節(jié)點永遠位于0級。當你將樹移至低處，層級增加1。樹結(jié)構(gòu)術(shù)語（續(xù)）內(nèi)部節(jié)點：它指根節(jié)點與葉子節(jié)點之間的中間節(jié)點。節(jié)點B,C,D和K是內(nèi)部節(jié)點。Level

0Level

1Level

2Level

3ABCDIJHKGLMFE.樹結(jié)構(gòu)術(shù)語（續(xù)）樹結(jié)構(gòu)的深度：指一個樹結(jié)構(gòu)的最大層級。下面的樹結(jié)構(gòu)的深度是4。Level

0Level

1Level

2Level

3ABCDIJHKGLMFE.查看下列樹結(jié)構(gòu)并回答問題：該樹的深度為多少？節(jié)點B的子節(jié)點是那個？F節(jié)點的父節(jié)點是那個？E節(jié)點的層級為多少？H節(jié)點的兄弟節(jié)點是那個？D節(jié)點的兄弟節(jié)點是那個？那些節(jié)點是葉子節(jié)點？課間思考ABFGCEDHIroot.課間思考（續(xù)）答案：4D和EC2H沒有兄弟節(jié)點D節(jié)點的兄弟節(jié)點是EF,G,H和I.定義二叉樹一個二叉樹就是每個節(jié)點只能最多擁有2個子節(jié)點的樹結(jié)構(gòu)。這些子節(jié)點一般被視為左子節(jié)點和右子節(jié)點。

二叉樹有各種類型：嚴格二叉樹二叉樹的每一個節(jié)點（葉節(jié)點除外）都有非空的左子節(jié)點和右子節(jié)點。滿二叉樹完整二叉樹.滿二叉樹深度d的二叉樹擁有剛好2d–1個節(jié)點。ABCDEFG

深度=3

節(jié)點數(shù)=23–1=7定義二叉樹（續(xù)）.完整二叉樹：指有n個節(jié)點且深度為d，且其節(jié)點對應(yīng)深度為k的完整二叉樹中序號從0到n?1的節(jié)點。ABCDEF完整二叉樹ABCDEG不完整二叉樹定義二叉樹（續(xù)）ABCDEF滿二叉樹G0126543012345012345.表示一個二叉樹二叉樹的數(shù)組表示：所有節(jié)點被表示為數(shù)組中的元素。ABCDEFGABCDEGF[0][1][2][3][4][5][6]0123456二叉樹數(shù)組表示如果一個二叉樹有N個節(jié)點，那么對于索引為I的任何節(jié)點，其中0<i<n–1:i的父節(jié)點位于(i–1)/2。i左子節(jié)點位于2i+1：如果2i+1>n–1，那么此節(jié)點沒有左子節(jié)點。i的右子節(jié)點位于2i+2：如果2i+2>n–1，那么此節(jié)點沒有右子節(jié)點。.二叉樹的鏈接表現(xiàn)形式：使用鏈接列表來實現(xiàn)一個二叉樹。鏈接表示中的每個節(jié)點都具有以下信息：數(shù)據(jù)對左子節(jié)點的引用對右子節(jié)點的引用如果一個節(jié)點不含有左子節(jié)點或右子節(jié)點，或一個子節(jié)點都沒有，相應(yīng)的左（右）子節(jié)點字段就指向NULL。DataNode表示一個二叉樹（續(xù)）.5268597224807036........5236682459727080二叉樹鏈接表示rootroot表示一個二叉樹（續(xù)）.你可以在叉樹上執(zhí)行各種操作。在二叉樹上最常見的操作是遍歷。遍歷指的是訪問樹中所有節(jié)點一次的過程。遍歷二叉樹有三種方式：中序遍歷（Inordertraversal）前序遍歷（Preordertraversal）后序遍歷（Postordertraversal）遍歷二叉樹.中序遍歷一個二叉數(shù)所需的步驟如下：1. 遍歷左子樹2. 訪問根節(jié)點3. 遍歷右子樹讓我們考慮一個示例。中序遍歷.中序遍歷（續(xù)）ACEBFGDHIroot節(jié)點A的左子樹不為NULL。因此，移動到B以遍歷A的左子樹。節(jié)點B的左子樹不為NULL。因此，移動到D以遍歷B的左子樹。.中序遍歷（續(xù)）節(jié)點D的左子樹為NULL。因此，訪問節(jié)點D。DACEBFGDHIroot.中序遍歷（續(xù)）D的右子樹不為NULL。因此，移動到D的右子樹。DACEBFGDHIroot.中序遍歷（續(xù)）H的左子樹為空。因此，訪問節(jié)點H。DHACEBFGDHIroot.中序遍歷（續(xù)）H的右子樹為空。因此，移動到節(jié)點B。DHACEBFGDHIroot.中序遍歷（續(xù)）已經(jīng)訪問了B的左子樹。因此，訪問節(jié)點B。DHBACEBFGDHIroot.中序遍歷（續(xù)）B的右子樹不為空。因此，移動到B的右子樹。DHBACEBFGDHIroot.中序遍歷（續(xù)）E的左子樹為空。因此，訪問節(jié)點E。DHEBACEBFGDHIroot.中序遍歷（續(xù)）E的右子樹為空。因此，移動到節(jié)點A。DHEBACEBFGDHIroot.中序遍歷（續(xù)）已經(jīng)訪問過A的左子樹。因此，訪問節(jié)點A.DHEBAACEBFGDHIroot.中序遍歷（續(xù)）A的右子樹不為空。因此，移動到A的右子樹。DHEBAACEBFGDHIroot.中序遍歷（續(xù)）C的左子樹不為空。因此，移動到C的左子樹。DHEBAACEBFGDHIroot.中序遍歷（續(xù)）F的左子樹為空。因此，訪問節(jié)點F。DHEBAFACEBFGDHIroot.中序遍歷（續(xù)）F的右子樹為空。因此，移動到節(jié)點C。DHEBAFACEBFGDHIroot.中序遍歷（續(xù)）已經(jīng)訪問過節(jié)點C的左子樹。因此，訪問節(jié)點C.DHEBAFCACEBFGDHIroot.中序遍歷（續(xù)）C的右子樹不為空。因此，移動到節(jié)點C的右子樹。DHEBAFCACEBFGDHIroot.中序遍歷（續(xù)）G的左子樹不為空。因此，移動到節(jié)點G的左子樹。DHEBAFCACEBFGDHIroot.中序遍歷（續(xù)）I的左子樹為空。因此，訪問I。DHEBAFCIACEBFGDHIroot.中序遍歷（續(xù)）I的右子樹為空。因此，移動到節(jié)點G。DHEBAFCIACEBFGDHIroot.中序遍歷（續(xù)）訪問節(jié)點G。DHEBAFCIGACEBFGDHIroot.中序遍歷（續(xù)）G的右子樹為空。DHEBAFCIG遍歷完成ACEBFGDHIroot.前序遍歷按前序遍歷一個二叉樹的順序如下：1. 訪問根節(jié)點2. 遍歷左子樹3. 遍歷右子樹.前序遍歷（續(xù)）ACEBFGDHI對下面的樹執(zhí)行前序遍歷。ABDHECFGI前序遍歷：.后序遍歷在二叉樹中進行后序遍歷的步驟如下：1.遍歷左子樹2. 遍歷右子樹3. 訪問根節(jié)點.后序遍歷（續(xù)）ACEBFGDHI對下面的樹執(zhí)行后序遍歷。HDEB