數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)要點(diǎn)(編輯修改稿)
2025-07-19 17:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。在分支結(jié)點(diǎn)中,每個(gè)結(jié)點(diǎn)的分支數(shù)就是該結(jié)點(diǎn)的度。3. 路徑與路徑長(zhǎng)度：如果一棵樹(shù)中的一串結(jié)點(diǎn)n1,n2,…,nk,有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)(1≤ik) ,就把n1,n2,…,nk稱為一條由n1至nk的路徑，這條路徑的長(zhǎng)度是k1。4. 孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：在一棵樹(shù)中,每個(gè)結(jié)點(diǎn)的后繼,被稱作該結(jié)點(diǎn)的孩子結(jié)點(diǎn)(或子女結(jié)點(diǎn))。相應(yīng)地,該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)(或父母結(jié)點(diǎn))。具有同一雙親的孩子結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。進(jìn)一步推廣這些關(guān)系,可以把每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn),從樹(shù)根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的路徑上經(jīng)過(guò)的所有結(jié)點(diǎn)被稱作該結(jié)點(diǎn)的祖先結(jié)點(diǎn)：樹(shù)中的每個(gè)結(jié)點(diǎn)都處在一定的層次上。結(jié)點(diǎn)的層次從樹(shù)根開(kāi)始定義,根結(jié)點(diǎn)為第1層,它的孩子結(jié)點(diǎn)為第2層,以此類推,一個(gè)結(jié)點(diǎn)所在的層次為其雙親結(jié)點(diǎn)所在的層次加1。樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的高度(或樹(shù)的深度)。：若樹(shù)中各結(jié)點(diǎn)的子樹(shù)是按照一定的次序從左向右安排的,且相對(duì)次序是不能隨意變換的,則稱為有序樹(shù),否則稱為無(wú)序樹(shù)。：n(n＞0)個(gè)互不相交的樹(shù)的集合稱為森林。森林的概念與樹(shù)的概念十分相近,因?yàn)橹灰褬?shù)的根結(jié)點(diǎn)刪去就成了森林。反之,只要給n棵獨(dú)立的樹(shù)加上一個(gè)結(jié)點(diǎn),并把這n棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù),則森林就變成了樹(shù)。性質(zhì)1 樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。性質(zhì)2 度為m的樹(shù)中第i層上至多有mi1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。性質(zhì)3 高度為h的m次樹(shù)至多有個(gè)結(jié)點(diǎn)。性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的m次樹(shù)的最小高度為233。logm(n(m1)+1)249。：①樹(shù)的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。②樹(shù)中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。樹(shù)的運(yùn)算主要分為三大類：第一類,尋找滿足某種特定關(guān)系的結(jié)點(diǎn),如尋找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等；第二類,插入或刪除某個(gè)結(jié)點(diǎn),如在樹(shù)的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等；第三類,遍歷樹(shù)中每個(gè)結(jié)點(diǎn),這里著重介紹。樹(shù)的遍歷運(yùn)算是指按某種方式訪問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。樹(shù)的遍歷運(yùn)算的算法主要有先根遍歷和后根遍歷兩種。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。1. 先根遍歷先根遍歷過(guò)程為： (1)訪問(wèn)根結(jié)點(diǎn)； (2)按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。2. 后根遍歷后根遍歷過(guò)程為： (1) 按照從左到右的次序后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)； (2) 訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)(Binary Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諛?shù)(n＝0)，或?yàn)榉强諛?shù)；對(duì)于非空樹(shù)有：(1) 有一個(gè)特定的稱之為根的結(jié)點(diǎn)； (2) 根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)分別由兩棵互不相交的稱之為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。這個(gè)遞歸定義表明二叉樹(shù)或?yàn)榭?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)組成的。由于左、右子樹(shù)也是二叉樹(shù)，則由二叉樹(shù)的定義，它們也可以為空。由此，二叉樹(shù)可以有五種基本形態(tài)性質(zhì)1 二叉樹(shù)第i(i≥1)層上至多有2i1個(gè)結(jié)點(diǎn)。性質(zhì)2 深度為k(k≥1)的二叉樹(shù)至多有2k－1個(gè)結(jié)點(diǎn)。性質(zhì)3 在任意二叉樹(shù)中，若葉子結(jié)點(diǎn)(即度為零的結(jié)點(diǎn))個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)n1，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，那么n0=n2+1。性質(zhì)4 具有n個(gè)(n＞0)結(jié)點(diǎn)的完全二叉樹(shù)的高度為233。log2n+1249?；?35。log2n+1。性質(zhì)5 若對(duì)有n(1≤i≤n)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)進(jìn)行順序編號(hào)，那么，對(duì)于編號(hào)為i(i≥1)的結(jié)點(diǎn)：當(dāng)i=1時(shí)，該結(jié)點(diǎn)為根，它無(wú)雙親結(jié)點(diǎn)；當(dāng)i＞1時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為235。i/2 ；若2i≤n，則有編號(hào)為2i的左孩子，否則沒(méi)有左孩子；若2i+1≤n，則有編號(hào)為2i+1的右孩子，否則沒(méi)有右孩子。滿二叉樹(shù)：深度為k且含有2k－1個(gè)結(jié)點(diǎn)的二叉樹(shù)為滿二叉樹(shù)，這種樹(shù)的特點(diǎn)是每層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹(shù)稱作滿二叉樹(shù)。如圖所示，(a)圖就是一棵滿二叉樹(shù)，(b)圖則不是滿二叉樹(shù)，因?yàn)?，雖然其所有結(jié)點(diǎn)要么是含有左右子樹(shù)的分支結(jié)點(diǎn)，要么是葉子結(jié)點(diǎn)，但由于其葉子未在同一層上，故不是滿二叉樹(shù)完全二叉樹(shù)：深度為k，含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)與相應(yīng)滿二叉樹(shù)結(jié)點(diǎn)順序號(hào)從1到n相對(duì)應(yīng)時(shí)，則稱此二叉樹(shù)為完全二叉樹(shù)顯然，一棵滿二叉樹(shù)必定是一棵完全二叉樹(shù)，而完全二叉樹(shù)未必是滿二叉樹(shù)。如圖所示(a)為一棵完全二叉樹(shù)，(b)不是完全二叉樹(shù)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的存放次序是：對(duì)該樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào),其編號(hào)從小到大的順序就是結(jié)點(diǎn)存放在連續(xù)存儲(chǔ)單元的先后次序。若把二叉樹(shù)存儲(chǔ)到一維數(shù)組中,則該編號(hào)就是下標(biāo)值加1(注意,C/C++語(yǔ)言中數(shù)組的起始下標(biāo)為0)。樹(shù)中各結(jié)點(diǎn)的編號(hào)與等高度的完全二叉樹(shù)中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同data表示值域,用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域,用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹(shù)的根結(jié)點(diǎn))的存儲(chǔ)位置下圖(a)給出一棵二叉樹(shù)的二叉鏈表存儲(chǔ)表示。二叉鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如圖(b)所示。二叉鏈表存儲(chǔ)表示可描述為：typedefstructbitnode{ datatype data。structbitnode *lchild。*rchild。/*左右孩子指針域*/}BiTNode, *BiTree。定義指針變量，用來(lái)存放根結(jié)點(diǎn)地址，通常用該指針標(biāo)識(shí)一個(gè)二叉樹(shù)：BiTree t。 二叉樹(shù)的遍歷是指按照一定次序訪問(wèn)樹(shù)中所有結(jié)點(diǎn),并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。它是最基本的運(yùn)算,是二叉樹(shù)中所有其他運(yùn)算的基礎(chǔ)。（DLR）先序遍歷二叉樹(shù)的過(guò)程是：(1) 訪問(wèn)根結(jié)點(diǎn)；(2) 先序遍歷左子樹(shù)；(3) 先序遍歷右子樹(shù)。voidPreOrder(BiTreebt) { if (bt==NULL) return。 /*遞歸調(diào)用的結(jié)束條件*/ Visit(bt) 。 /*訪問(wèn)根結(jié)點(diǎn)*/PreOrder(btlchild)。 /*先序遞歸遍歷bt的左子樹(shù)*/PreOrder(btrchild)。/*先序遞歸遍歷bt的右子樹(shù)*/ }（LDR）中序
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1