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