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