數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)要點(diǎn)-文庫(kù)吧資料
2025-06-28 17:05本頁(yè)面
【正文】 bt==NULL) return。它是最基本的運(yùn)算,是二叉樹(shù)中所有其他運(yùn)算的基礎(chǔ)。定義指針變量，用來(lái)存放根結(jié)點(diǎn)地址，通常用該指針標(biāo)識(shí)一個(gè)二叉樹(shù)：BiTree t。*rchild。二叉鏈表存儲(chǔ)表示可描述為：typedefstructbitnode{ datatype data。樹(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ǔ)表示。二叉樹(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ǔ)單元的先后次序。如圖所示，(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ù)。；若2i≤n，則有編號(hào)為2i的左孩子，否則沒(méi)有左孩子；若2i+1≤n，則有編號(hào)為2i+1的右孩子，否則沒(méi)有右孩子。性質(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。log2nlog2n+1249。性質(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。由此，二叉樹(shù)可以有五種基本形態(tài)性質(zhì)1 二叉樹(shù)第i(i≥1)層上至多有2i1個(gè)結(jié)點(diǎn)。這個(gè)遞歸定義表明二叉樹(shù)或?yàn)榭?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)組成的。二叉樹(shù)(Binary Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。1. 先根遍歷先根遍歷過(guò)程為： (1)訪問(wèn)根結(jié)點(diǎn)； (2)按照從左到右的次序先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。樹(shù)的遍歷運(yù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ù)的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的m次樹(shù)的最小高度為233。性質(zhì)2 度為m的樹(shù)中第i層上至多有mi1個(gè)結(jié)點(diǎn),這里應(yīng)有i≥1。反之,只要給n棵獨(dú)立的樹(shù)加上一個(gè)結(jié)點(diǎn),并把這n棵樹(shù)作為該結(jié)點(diǎn)的子樹(shù),則森林就變成了樹(shù)。：n(n＞0)個(gè)互不相交的樹(shù)的集合稱為森林。樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的高度(或樹(shù)的深度)。進(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)都處在一定的層次上。相應(yīng)地,該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)(或父母結(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。度為零的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)。樹(shù)中各結(jié)點(diǎn)的度的最大值稱為樹(shù)的度,通常將度為m的樹(shù)稱為m次樹(shù)。將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊,除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)中并用逗號(hào)間隔來(lái)描述樹(shù)結(jié)構(gòu)。使用線段的伸縮描述樹(shù)結(jié)構(gòu)。使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。第六章樹(shù)和二叉樹(shù)（1）樹(shù)形表示法。但在利用鏈表存儲(chǔ)串值時(shí)，每個(gè)結(jié)點(diǎn)既可以存放一個(gè)字符，也可以存放多個(gè)字符，即存在一個(gè)“結(jié)點(diǎn)大小”的問(wèn)題。（1）串賦值StrAssign(t，chars)（2）串聯(lián)接StrConcat(t，s1，s2)（3）求子串SubString(t, s, pos, len)（4）插入函數(shù)StrInsert(s, pos, t)（5）刪除函數(shù)StrDelete (s, pos, t)順序串上的插入和刪除操作運(yùn)算需要移動(dòng)大量的字符。（11）置換運(yùn)算StrReplace（s，pos，len,t）：用t串置換s串中第pos字符開(kāi)始的連續(xù)的len個(gè)字符。（9）刪除運(yùn)算StrDel（s，pos，len）：將串s中從第pos字符起始的長(zhǎng)度為len的子串刪除。（6）串比較StrCom（s，t）（7）求子串SubStr（t，s，pos，len）：返回s串的第pos個(gè)字符起始的長(zhǎng)度為len的子串。（4）StrConcat（t，s1，s2）：串聯(lián)接。（2）StrAssign（s，ch）：串賦值。根據(jù)隊(duì)列的操作特點(diǎn)，進(jìn)隊(duì)和退隊(duì)分別在表的兩端進(jìn)行，具體表現(xiàn)為“先進(jìn)先出”。 }elseout=queue[++f]。 }}出隊(duì)算法:出隊(duì)首先要判斷隊(duì)列中是否有元素，即R是否等于F，R=F可能出現(xiàn)在初態(tài)，也可能出現(xiàn)在出隊(duì)、進(jìn)隊(duì)的動(dòng)態(tài)變化中。 }else { r++。進(jìn)隊(duì)算法:根據(jù)隊(duì)列的結(jié)構(gòu)，若隊(duì)尾指針不在隊(duì)的最大長(zhǎng)度上，則首先隊(duì)尾指針加１，元素進(jìn)隊(duì)，否則就是隊(duì)滿，無(wú)法進(jìn)隊(duì)。對(duì)該操作應(yīng)設(shè)置一個(gè)參數(shù)，即在參數(shù)中指定一個(gè)鏈棧。假設(shè)指定的鏈棧top，入棧元素x其類型為ElemType，入棧操作取名為push，則該操作可表示為：viod Push(Lsnode *top，ElemType x)操作的功能為在由top指向的鏈棧中插入元素x，使x成為棧頂元素。2．入棧操作鏈棧入棧操作的含義是：將一個(gè)元素推入指定的鏈棧中。 2棧的相關(guān)術(shù)語(yǔ)1．初始化空棧voidIniStack(Lsnode *top){ topnext=NULL。 } Lsnode。 typedefstructLsnode{ ElemType data。}Stack。int capacity。棧的基本運(yùn)算如下：（1）判?？誌sEmpty(S). 若棧為空則返回“真“，否則返回”假“；（2）入棧操作（壓棧）Push(S
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1