數(shù)據(jù)結(jié)構(gòu)訓(xùn)練營課件和二叉樹

【本標樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。除根節(jié)點外，其余結(jié)點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<=i<=m)又是一棵結(jié)構(gòu)與樹類似的。每棵的根結(jié)點有且只有一個前驅(qū)，可以節(jié)點的度：一個節(jié)點含有的的個數(shù)稱為該節(jié)點的度；如上圖：A的為葉節(jié)點或終端節(jié)點：度為0B、C、H、I...等節(jié)點為葉節(jié)點非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點；如上圖：D、E、F、G...等節(jié)點為分支節(jié)點雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；如上圖：A是B孩子節(jié)點或子節(jié)點：一個節(jié)點含有的的根節(jié)點稱為該節(jié)點的子節(jié)點；如上圖：B是A的孩子節(jié)B、C是兄弟節(jié)點樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；如上圖：樹的度為6樹的高度或深度：樹點的最大層次；如上圖：樹的高度為4森林：由（m>）棵互不相交的多顆樹的集合稱為森林；（數(shù)據(jù)結(jié)構(gòu)中的學(xué)習(xí)并查集本質(zhì)就是一個森林）樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡單的了解其中最常用的兄弟表示法。structNode{structNode*_firstChild1; //第一個孩子結(jié)點structNode*_pNextBrother; //指向其下一個兄弟結(jié)點DataType_data; //結(jié)點中的數(shù)據(jù)域 樹結(jié)構(gòu)樹和右的二叉樹組成。樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是(2^k)1，則它就是滿二叉樹。完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至的結(jié)點一一對應(yīng)時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結(jié)點若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h-對任何一棵二叉樹,如果度為0n0度為2n2,則有順序結(jié)構(gòu)就是使用數(shù)組來，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順序在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。二叉樹的鏈式結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的地址。鏈式結(jié)構(gòu)又分為二叉鏈和三叉鏈，當前我們學(xué)習(xí)中一般都是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如樹等會用到三叉鏈。structstruct{structBinTreeNode*pLeft;//指向當前節(jié)點左孩子structBinTreeNode*pRight;//指向當前節(jié)點右孩子BTDataType_data;//當前節(jié)點值域}struct{{structBinTreeNode*pParent;//指向當前節(jié)點的雙親structBinTreeNode*pLeft;//指向當前節(jié)點左孩子structBinTreeNode*pRight;//指向當前節(jié)點右孩子BTDataType_data;//當前節(jié)點值域某二叉樹共有某二叉樹共有399個結(jié)點，其中有199個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（2.在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（A 8所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次。結(jié)點所做的操作依賴于具體的應(yīng)用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其NLR：前序遍歷(PreorderTraversal亦稱先序遍歷)——根結(jié)點的操作發(fā)生在遍歷其左右LNR：中序遍歷 （間）LRN：后序遍歷 由于被的結(jié)點必是某的根，所以N(Node）、L(Leftsubtree）和R(Rightsubtree）又可解釋為根、根的左和根的右。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先第一層的樹根節(jié)點，然后從左到右第層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層樹的結(jié)點的過程就是層序遍歷。1.1.某完全二叉樹按層次輸出（同一層從左到右）的序列為