數據結構之(隊、棧、二叉樹)

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

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

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