數(shù)據(jù)結(jié)構(gòu)之(隊(duì)、棧、二叉樹)

（隊(duì)、棧、二叉樹）數(shù)據(jù)（Data）數(shù)據(jù)是信息的載體。它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理，是計(jì)算機(jī)程序加工的'原料”。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的范疇包括：整數(shù)、實(shí)數(shù)、字符串、圖像和聲音等。數(shù)據(jù)元素（DataElement）數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也可稱為字段、域、屬性）組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)結(jié)構(gòu)（DataStructure）指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括以下三方面內(nèi)容：數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）；數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（StorageStructure）；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱為映象），它依賴于計(jì)算機(jī)語言。對(duì)機(jī)器語言而言，存儲(chǔ)結(jié)構(gòu)是具體的。一般，只在高級(jí)語言的層次上討論存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作。數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。最常用的檢索、插入、刪除、更新、排序等運(yùn)算實(shí)際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。（1） 邏輯結(jié)構(gòu)表中的每一行是一個(gè)數(shù)據(jù)元素（或記錄、結(jié)點(diǎn)）它由學(xué)號(hào)、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對(duì)表中任一個(gè)結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)（亦稱為直接前趨（ImmediatePredecessor））最多只有一個(gè)；與表中任一結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)（亦稱為直接后繼（ImmediateSuccessor））也最多只有一個(gè)。表中只有第一個(gè)結(jié)點(diǎn)沒有直接前趨，故稱為開始結(jié)點(diǎn)；也只有最后一個(gè)結(jié)點(diǎn)沒有直接后繼。故稱之為終端結(jié)點(diǎn)。例如，表中”馬二”所在結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)分別是”丁一”和”張三”所在的結(jié)點(diǎn)，上述結(jié)點(diǎn)間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。（2） 存儲(chǔ)結(jié)構(gòu)該表的存儲(chǔ)結(jié)構(gòu)是指用計(jì)算機(jī)語言如何表示結(jié)點(diǎn)之間的這種關(guān)系，即表中的結(jié)點(diǎn)是順序鄰接地存儲(chǔ)在一片連續(xù)的單元之中，還是用指針將這些結(jié)點(diǎn)鏈接在一起？（3） 數(shù)據(jù)的運(yùn)算在上面的學(xué)生成績表中，可能要經(jīng)常查看某一學(xué)生的成績；當(dāng)學(xué)生退學(xué)時(shí)要?jiǎng)h除相應(yīng)的結(jié)點(diǎn)；進(jìn)來新學(xué)生時(shí)要增加結(jié)點(diǎn)。究竟如何進(jìn)行查找、刪除、插入，這就是數(shù)據(jù)的運(yùn)算問題。搞清楚了上述三個(gè)問題，也就弄清了學(xué)生成績表這個(gè)數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：（1）線性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。(2)非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。隊(duì)隊(duì)列的基礎(chǔ)知識(shí)到醫(yī)院看病排隊(duì)掛號(hào)排隊(duì)、在學(xué)校食堂就餐排隊(duì)買飯、到銀行辦理存款或取款業(yè)務(wù)排隊(duì)、共同的特征，嚴(yán)格遵守先來后到原則，不存在插隊(duì)現(xiàn)象隊(duì)列(Queue)是一種特殊的線性表。它是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭(front),允許插入的一端稱為隊(duì)尾(rear)。因此隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡稱FIFO表?xiàng)；仡櫨€性表的特性：除了首尾結(jié)點(diǎn)，所有的結(jié)點(diǎn)都有前驅(qū)和后繼；首結(jié)點(diǎn)只有后繼沒有前驅(qū)，尾結(jié)點(diǎn)只有前驅(qū)沒有后繼；線性表的任何位置都可以進(jìn)行插入、刪除等操作?，F(xiàn)在我們對(duì)線性表的操作做一點(diǎn)限制，規(guī)定所有的插入或刪除操作只能在線性表的一端進(jìn)行，這樣的線性表稱為棧(stack)。棧是一種特殊的線性表，對(duì)它的插入和刪除都限制在表的同一端進(jìn)行。一、棧的概念和特性把可以操作的一端稱為棧頂，不允許操作的一端稱為棧底。在棧頂插入一個(gè)元素，稱為進(jìn)棧，在棧頂刪除一個(gè)元素稱為出棧。棧中元素的進(jìn)出是按后進(jìn)先出的原則進(jìn)行，這是棧結(jié)構(gòu)的重要特征。(LIFO:LastInFirstOut)用一個(gè)變量記錄棧頂?shù)奈恢?，通常稱這個(gè)變量為棧指針。中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式從左向右掃描表達(dá)式、運(yùn)算數(shù)送到輸出隊(duì)列、運(yùn)算符進(jìn)棧、如果運(yùn)算優(yōu)先級(jí)大于棧頂元素直接進(jìn)棧，如果運(yùn)算優(yōu)先級(jí)小于或等于棧頂元素，則先彈出棧頂元素，再進(jìn)棧、左括號(hào)直接進(jìn)棧、右括號(hào)則依次彈出棧中的元素，直到遇到第一個(gè)左括號(hào)為止。賽前知識(shí)點(diǎn)梳理二

(樹、二叉樹)樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，很象自然界中的樹那樣，從樹根到大分枝、小分枝、直到葉子把數(shù)據(jù)聯(lián)系起來，這種數(shù)據(jù)結(jié)構(gòu)就叫做樹結(jié)構(gòu)，簡稱樹。樹中每個(gè)分叉點(diǎn)稱為結(jié)點(diǎn)，起始結(jié)點(diǎn)稱為根結(jié)點(diǎn)，任意兩個(gè)結(jié)點(diǎn)間的連接關(guān)系稱為樹枝，結(jié)點(diǎn)下面不再有分枝稱為樹葉。結(jié)點(diǎn)的前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的”雙親”，結(jié)點(diǎn)的后趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的”子女”或”孩子"，同一結(jié)點(diǎn)的”子女”之間互稱”兄弟”。樹結(jié)構(gòu)的特點(diǎn)是：它的每一個(gè)結(jié)點(diǎn)都可以有不止一個(gè)直接后繼，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨。樹的基本術(shù)語結(jié)點(diǎn)的度和樹的寬度一個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)稱為是該結(jié)點(diǎn)的度，樹的所有結(jié)點(diǎn)中的最大度為該樹的寬度分支結(jié)點(diǎn)和葉結(jié)點(diǎn)度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或端結(jié)點(diǎn)、度大于0的結(jié)點(diǎn)稱作分支結(jié)點(diǎn)(根結(jié)點(diǎn)除外)樹的基本術(shù)語2樹的深度在樹的結(jié)構(gòu)中，結(jié)點(diǎn)的層數(shù)從樹根開始定義，根結(jié)點(diǎn)在第一層，其子結(jié)點(diǎn)在第二層，以此類推。樹中結(jié)點(diǎn)最大的層號(hào)為樹的深度。有序樹和無序樹若結(jié)點(diǎn)的子樹有次序排列，且先后次序不能互換，這樣的樹稱為有序樹，反之為無序樹。森林森林是若干棵互不相交的樹構(gòu)成的集合。二叉樹的定義 xOPQQ如果樹中每個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)小于或等于2,并且各 / \/\子樹的次序不能互換，有左、右子樹之分，這樣的 |. °、 | °.°樹稱為二叉樹。二叉樹是一種度為2的有序樹。d「c'c二叉樹共有5種不同的基本形態(tài)。a,空二叉樹；b.只有一個(gè)根結(jié)點(diǎn)的二叉樹；c.右子樹為空的二叉樹；d.左子樹為空的二叉樹;.左、右子樹非空的二叉樹。N個(gè)結(jié)點(diǎn)的二叉樹有C(N,2N)/(N+1)二叉樹的性質(zhì)性質(zhì)1：二叉樹第i(i>=1)層的結(jié)點(diǎn)總數(shù)不超過2i-1；性質(zhì)2：深度為k的二叉樹的結(jié)點(diǎn)總數(shù)不超過2k-1(k>=1)。第1層1個(gè)結(jié)點(diǎn)，20、第2層2個(gè)結(jié)點(diǎn)，21、第3層4個(gè)結(jié)點(diǎn)，22第i層2i-1個(gè)結(jié)點(diǎn)；對(duì)于深度為k的二叉樹所具有的結(jié)點(diǎn)總數(shù)為：2人0+2人1+2人2+……+2A(k-1)=2Ak-1特殊的二叉樹滿二叉樹：如果一個(gè)深度為K的二叉樹，具有2k-1個(gè)結(jié)點(diǎn)，則稱該二叉樹為滿二叉樹。滿二叉樹最底一層的各個(gè)結(jié)點(diǎn)的度數(shù)為0，而其余的結(jié)點(diǎn)的度數(shù)均為2。對(duì)于給定深度，滿二叉樹的結(jié)點(diǎn)數(shù)最多。完全二叉樹：如果一棵深度為K二叉樹，1至k-1層的結(jié)點(diǎn)都是滿的，即滿足2i-1，只有最下面的一層的結(jié)點(diǎn)數(shù)小于2i-1，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置，則此二叉樹稱為完全二叉樹。二叉樹性質(zhì)3在任意二叉樹中，如果其葉結(jié)點(diǎn)的個(gè)數(shù)為N0，其度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2,則有：N0=N2+1設(shè)有一棵k叉樹，其中只有度為0和k兩種結(jié)點(diǎn)，設(shè)n0，nk，分別表示度為0和度為k的結(jié)點(diǎn)個(gè)數(shù)，試求出n0和nk之間的關(guān)系(n0=數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含nk、k和數(shù)字)。n0和nk之間的關(guān)系為：n0=(k-1)nk+1二叉樹的性質(zhì)對(duì)于完全二叉樹，結(jié)點(diǎn)的位置與結(jié)點(diǎn)編號(hào)的關(guān)系：如果i=1，則i為根，無父結(jié)點(diǎn)；如果i<>1，則父結(jié)點(diǎn)為［i/2］。如果2*i<=N，則i的左兒子的編號(hào)為2*i。如果2*i+1<=N，則i的右兒子的編號(hào)為2*i+1。二叉樹的遍歷二叉樹的遍歷不外乎這么四種：①先根(先序)遍歷；②中根(中序)遍歷；③后根(后序)遍歷；④寬度優(yōu)先(按層)遍歷。先根遍歷的順序是先訪問根結(jié)點(diǎn)，然后是左子樹，最后是右子樹；中根遍歷的順序是先訪問左子樹，然后是根結(jié)點(diǎn)，最后是右子樹；后根遍歷的訪問順序是先訪問左子樹，然后是右子樹，最后是根結(jié)點(diǎn)；寬度優(yōu)先遍歷是先根結(jié)點(diǎn)，然后自上而下、從左到右按層訪問，直到樹中每個(gè)結(jié)點(diǎn)都被訪問完為止。考試題一般不正面考，也就是說，不可能給你畫好一棵二叉樹，讓你寫出它的遍歷序列，而是給出它的某兩個(gè)遍歷序列，或是其他條件，讓你自己畫出可能的二叉樹，從而推出相應(yīng)的遍歷序列。常見的題型有如下幾種：由中根序列和后根序列來確定二叉樹的結(jié)構(gòu)，從而判斷先根遍歷序列及其它。例如：(NOIP2001提高組試題)已知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母，其中序與后序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA則該二叉樹的先序遍歷的順序?yàn)椋航馕觯阂阎行蛐蛄袨镃BGEAFHDI(1) 后序序列為CGEBHFJIDA。(2)TOC\o"1-5"\h\z由(2)知：根結(jié)點(diǎn)為A 蘭由(1)知：A的左子樹中序序列為CBGE(3) ?.：A的右子樹中序序列為FHDIJ(4)由(2)知：A的左子樹后序序列為CGEB(5) 威壘，A的右子樹后序序列為HFJID(6) '-由(5)(6)知：A的左子樹根結(jié)點(diǎn)為B，A的右子樹根結(jié)點(diǎn)為D由(3)(4)知：B的左子樹為C，右子樹中序序列為GED的左子樹中序序列為FH，右子樹中序序列為IJ由(5)(6)知：B的右子樹后序序列為GE，即根結(jié)點(diǎn)為ED的左子樹后序序列為HF，即根結(jié)點(diǎn)為FD的右子樹后序序列為JI，即根結(jié)點(diǎn)為I綜上可推出二叉樹的結(jié)構(gòu)如圖所示故該二叉樹的先序遍歷序列為：ABCEGDFHIJ由前序序列和中序序列來確定一棵二叉樹，從而判斷后序序列及其它。例如：(NOIP2004提高組試題)二叉樹T，已知其前序遍歷序列為1243576，中序遍歷序列為4215736,則其后序遍歷序列為(B )。A.4257631B.4275631C.4275361D.4723561E.452637l由先根序列和后根序列來推斷二叉樹的結(jié)構(gòu)，從而判斷中根遍歷序列以及其他。例如：(NOIP2007提高組第14題)已知7個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是1245637f數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同)，后根遍歷是4652731，則該二叉樹的可能的中根遍歷是()。A.4265173B.4256137C.4231547D.4256173解析：先根遍歷序列是1245637(1)后根遍歷序列是4652731(2)

由（1）和（2）知：根結(jié)點(diǎn)為l,1的左子樹根結(jié)點(diǎn)是2,右子樹根結(jié)點(diǎn)是3,結(jié)點(diǎn)4是結(jié)點(diǎn)2的左子樹，可以判斷結(jié)點(diǎn)5是結(jié)點(diǎn)2的右子樹的根結(jié)點(diǎn)，但結(jié)點(diǎn)6可能是結(jié)點(diǎn)5的左子樹，也可能是它的右子樹，同樣結(jié)點(diǎn)7可能是結(jié)點(diǎn)3的左子樹，也可能是它的右子樹。對(duì)應(yīng)的二叉樹的結(jié)構(gòu)可能是如下四種:圖③的圖③的中序遍歷序列是：4265137，：：：圖④的中序遍歷序列是：425613可 故此題的答案應(yīng)選ABD（四）通過二叉樹的寬度優(yōu)先遍歷和樹中結(jié)點(diǎn)的最大深度及結(jié)點(diǎn)之間的關(guān)系來判斷樹的結(jié)構(gòu)，從而解決有關(guān)問題。例如：（NOIP2005提高組試題）二叉樹T的寬度優(yōu)先遍歷序列為ABCDEFGHI，已知A是C的父結(jié)點(diǎn)，D是G的父結(jié)點(diǎn)，F(xiàn)是I的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3（根結(jié)點(diǎn)深度設(shè)為0），可知E的父結(jié)點(diǎn)可能是（）。A.AB.BC. CD. DE.F解析：二叉樹的寬度優(yōu)先遍歷就是按層遍歷，從根結(jié)點(diǎn)自上而下，自左向右訪問樹中的每個(gè)結(jié)點(diǎn)。由題目可知A是根結(jié)點(diǎn)，又知A是C的父結(jié)點(diǎn)，可以推知B是A的左子樹的根結(jié)點(diǎn)，C是A的右子樹的根結(jié)點(diǎn)。又知D是G的父結(jié)點(diǎn)，F(xiàn)是I的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3,故E結(jié)點(diǎn)可能是B結(jié)點(diǎn)的右子樹，也可能是G結(jié)點(diǎn)的左子樹。二叉樹的部分結(jié)構(gòu)圖為下圖①②所示：故E的父結(jié)點(diǎn)可能是B，也可能是C。（五）二叉樹的應(yīng)用。有些題目要求寫