數(shù)據(jù)結(jié)構(gòu)單元4引例在傳送電文時，總是希望電文代碼盡可能短，采用哈夫曼編碼構(gòu)造的電文的總長最短。由常識可知，電文中每個字符出現(xiàn)的概率是不同的。假定在一份電文中，A，B，C，D四種字符出現(xiàn)的概率是4/10，1/10，3/10，2/10，若采用不等長編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣就有可能縮短傳送電文的總長度引例描述：哈夫曼編碼構(gòu)造電文素質(zhì)小課堂“中國式現(xiàn)代化的最優(yōu)哈夫曼樹”給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若樹的帶權(quán)路徑長度達到最小，則這棵樹被稱為哈夫曼樹。引例分析與實現(xiàn)創(chuàng)建哈夫曼樹哈夫曼編碼構(gòu)造電文分析數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學(xué)院4.1樹引言Introduction樹（Tree）結(jié)構(gòu)是除了根結(jié)點和葉子結(jié)點之外，樹中任意一個結(jié)點只有一個直接前驅(qū)結(jié)點（父結(jié)點）和多個直接后繼結(jié)點（孩子結(jié)點），根結(jié)點沒有前驅(qū)結(jié)點，葉子結(jié)點沒有后繼結(jié)點。本節(jié)學(xué)習(xí)樹的定義、樹的術(shù)語、樹的表示、樹的抽象數(shù)據(jù)類型、樹的存儲結(jié)構(gòu)。Part01樹的定義樹（Tree）是n（n≥0）個結(jié)點的有限集T，T為空時稱為空樹，T非空時它滿足以下兩個約定條件：①有且僅有一個特定的稱為根（Root）的結(jié)點。②其余的結(jié)點可分為m（m≥0）個互不相交的有限子集Tl，T2，…，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹（SubTree）。樹的概念樹的定義樹是遞歸定義的。結(jié)點是樹的基本單位，若干個結(jié)點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。樹中的每一個結(jié)點都是該樹中某一棵子樹的根。因此，樹是由結(jié)點組成的、結(jié)點之間的具有層次關(guān)系的非線性結(jié)構(gòu)?？諛?、1個結(jié)點、n個結(jié)點的樹如右圖所示。樹的遞歸定義樹的定義Part02樹的術(shù)語1.結(jié)點、父母、孩子與兄弟結(jié)點樹的術(shù)語結(jié)點是樹的基本單位，結(jié)點是包含一個數(shù)據(jù)元素及指向其若干子樹的分支。在樹的圖形表示中為一個圓圈。結(jié)點的前驅(qū)結(jié)點稱為其父母（Parent）結(jié)點，結(jié)點的后繼結(jié)點稱為其孩子（Child）結(jié)點。一棵樹中只有根結(jié)點沒有父母結(jié)點，其他結(jié)點有且僅有一個父母結(jié)點。擁有同一個父母結(jié)點的多個結(jié)點之間稱為兄弟（Sibling）結(jié)點。結(jié)點的祖先(Ancestor)是指其父母結(jié)點以及父母的父母結(jié)點等，直至根結(jié)點。結(jié)點的后代（Descendant，也稱子孫）是指其所有孩子結(jié)點，以及孩子的孩子結(jié)點等。2.度樹的術(shù)語結(jié)點的度（Degree）是結(jié)點所擁有的子樹數(shù)。度為0的結(jié)點稱為葉子結(jié)點（Leaf），又稱為終端結(jié)點；樹中除葉子結(jié)點之外的其他結(jié)點稱為分支結(jié)點，又稱為非終端結(jié)點。樹的度是樹中各結(jié)點的度的最大值。3.結(jié)點層次、樹的高度樹的術(shù)語結(jié)點的層次（Level）反映結(jié)點在樹中的層次位置，約定根結(jié)點的層次為1，其余結(jié)點的層次等于其父母結(jié)點的層次加1。顯然，兄弟結(jié)點層次相同。樹的高度（Height）或深度（Depth）是指樹中各結(jié)點的層次最大值。4.邊、路徑樹的術(shù)語設(shè)樹中X結(jié)點是Y結(jié)點父母結(jié)點，有序?qū)Γ╔，Y）稱為連接這兩個結(jié)點的分支，也稱為邊。設(shè)（X0，X1，…，Xk-1）是樹中結(jié)點組成的序列，且（Xi，Xi+1）（0≦i≦k-1）都是樹中的邊，則稱該序列為X0到Xk-1的一條路徑（Path）。路徑長度（PathLength）為路徑上的邊數(shù)。5.無序樹、有序樹樹的術(shù)語

在樹的定義中，結(jié)點的子樹T0，Tl，T2，…，Tm-1之間沒有次序，可以交換位置，稱為無序樹。

如果結(jié)點的子樹T0，Tl，T2，…，Tm-1從左到右是有次序的，不能交換位置，則稱為有序樹。6.森林樹的術(shù)語森林（Forest）是m（m≥0）棵互不相交的樹的集合。對樹中的每一個結(jié)點而言，其子樹的集合即為森林，可以通過森林與樹相互遞歸的定義來描述樹。Part03樹的表示1.圖示法樹的表示結(jié)點用圓圈表示，結(jié)點名字寫在圓圈旁或圓圈內(nèi)，子樹與其根之間用無向邊來連接，如右圖是圖示法表示的樹。2.嵌套集合表示法樹的表示用集合的包含關(guān)系描述樹結(jié)構(gòu)，可以使用如右圖是樹的嵌套集合表示。3.凹入表示法樹的表示類似于書的目錄，使用線段的伸縮描述樹結(jié)構(gòu)。右圖是樹的凹入表示法。Part04樹的抽象數(shù)據(jù)類型樹的接口TTree樹的抽象數(shù)據(jù)類型publicinterfaceTTree<T>{

publicbooleanisEmpty();//判斷是否空樹

publicintcount();//返回樹的結(jié)點個數(shù)

publicintheight();//返回樹的高度//返回p結(jié)點的孩子結(jié)點個數(shù)

publicintchildCount(TreeNode<T>p);

publicvoidpreOrder();//先序遍歷樹

publicvoidpostOrder();//后序遍歷樹

publicvoidlevelOrder();//層次遍歷樹

//返回p結(jié)點的第i(i>=0)個孩子結(jié)點

publicTreeNode<T>getChild(TreeNode<T>p,inti);

//返回p結(jié)點的最后一個孩子結(jié)點publicTreeNode<T>getLastChild(TreeNode<T>p); //返回p結(jié)點的最后一個兄弟結(jié)點publicTreeNode<T>getLastSibling(TreeNode<T>p);//返回node的父結(jié)點publicTreeNode<T>getParent(TreeNode<T>node);publicTreeNode<T>search(Tx);//查找并返回元素為x的結(jié)點publicvoidinsertRoot(Tx);//插入元素x作為根結(jié)點//插入x元素作為p結(jié)點的第i個孩子publicTreeNode<T>insertChild(TreeNode<T>p,Tx,inti);

//插入最后一個孩子結(jié)點publicTreeNode<T>insertLastChild(TreeNode<T>p,Tx); //插入最后一個兄弟結(jié)點publicTreeNode<T>insertLastSibling(TreeNode<T>p,Tx);//刪除以P的第i個孩子為根的子樹publicvoidremoveChild(TreeNode<T>p,inti); publicvoidremoveAll();//刪除樹}樹的結(jié)點類樹的抽象數(shù)據(jù)類型publicclassTreeNode<T>{

publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素

publicTreeNode<T>child;//孩子結(jié)點

publicTreeNode<T>sibling;//兄弟結(jié)點

publicTreeNode(Tdata,TreeNode<T>child,TreeNode<T>sibling){

this.data=data;

this.child=child;

this.sibling=sibling; }

publicTreeNode(Tdata){

this(data,null,null);//構(gòu)造指定值的葉子結(jié)點 }

publicTreeNode(){

this(null,null,null);//空樹 }}Part05樹的存儲結(jié)構(gòu)假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中，附設(shè)一個指示器指向其雙親結(jié)點到鏈表中的位置。也就是說每個結(jié)點除了知道自己之外還需要知道它的雙親在哪里。雙親表示法如右圖所示，其中data為結(jié)點本身，parent為其父結(jié)點（雙親）在鏈表中的位置（下標(biāo)）。1.雙親表示法樹的存儲結(jié)構(gòu)1.雙親表示法樹的存儲結(jié)構(gòu)由于根結(jié)點是沒有雙親的，約定根結(jié)點的位置域為-1。根據(jù)結(jié)點的parent指針很容易找到它的雙親結(jié)點。所用時間復(fù)雜度為O(1)，當(dāng)parent為-1時，表示找到了樹的根結(jié)點。缺點：如果要找到孩子結(jié)點，需要遍歷整個結(jié)構(gòu)才行。把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表作為存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表，如果是葉子結(jié)點則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進一個一維數(shù)組中。2.孩子表示法樹的存儲結(jié)構(gòu)孩子兄弟表示法：任意一棵樹，它的結(jié)點的第一個孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，設(shè)置兩個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟。3.孩子兄弟表示法樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學(xué)院4.2二叉樹引言Introduction二叉樹（BinaryTree）是一種重要的樹結(jié)構(gòu)，它的特點是每一個結(jié)點最多只能有兩棵子樹。二叉樹的遞歸定義如下：二叉樹或者是一棵空樹，或者是一棵由一個根結(jié)點和兩棵互不相交的分別稱為根的左子樹和右子樹的子樹所組成的非空樹。Part01二叉樹定義與分類二叉樹（BinaryTree）是一種重要的樹結(jié)構(gòu)，它的特點是每一個結(jié)點最多只能有兩棵子樹。二叉樹的遞歸定義如下：二叉樹或者是一棵空樹，或者是一棵由一個根結(jié)點和兩棵互不相交的分別稱為根的左子樹和右子樹的子樹所組成的非空樹。二叉樹遞歸定義二叉樹中每一個結(jié)點的孩子只能是0、1、或2個二叉樹定義與分類二叉樹的基本形態(tài)二叉樹定義與分類二叉樹5種基本形態(tài)一棵深度為k且有2k?1個結(jié)點的二叉樹稱為滿二叉樹。滿二叉樹具有以下特點：①每一層上的結(jié)點數(shù)都達到最大值，即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹；②滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同的子樹，且樹葉都在最下一層。滿二叉樹二叉樹定義與分類在一棵二叉樹中，除了最后一層，都是滿的，并且最后一層或者是滿的，或者是右邊缺少連續(xù)若干結(jié)點，成為完全二叉樹。滿二叉樹具有以下特點：①葉子結(jié)點只能在最大的一層或最多只能在層次最大的兩層上出現(xiàn)；②對任一結(jié)點，若其右分支下子孫的最大層次為n（n≥1），則其左分支下的子孫最大層次不小于n；③若是滿二叉樹，則必定是完全二叉樹，反之不一定成立。完全二叉樹二叉樹定義與分類Part02二叉樹的性質(zhì)二叉樹的性質(zhì)1二叉樹的性質(zhì)性質(zhì)1：若規(guī)定根結(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2i-1個結(jié)點，其中i≥1。證明：假設(shè)樹非空，用數(shù)學(xué)歸納法證明。(1)當(dāng)i=1時，因為第1層上只有一個根結(jié)點，而2i?1=20=1，命題成立。(2)設(shè)第i?1層上至多有2i?2

個結(jié)點。由于二叉樹的每個結(jié)點至多有兩個孩子，故第i層上的結(jié)點數(shù)至多是第i?1層上的最大結(jié)點數(shù)的2倍。即j=i時，該層上至多有2×2i?2=2i?1

個結(jié)點，命題成立。二叉樹的性質(zhì)2二叉樹的性質(zhì)

二叉樹的性質(zhì)3二叉樹的性質(zhì)性質(zhì)3：對任何一棵非空二叉樹，如果其葉子結(jié)點個數(shù)為n0，度為2的非葉子結(jié)點個數(shù)為n2，則n0=n2+1。證明：假設(shè)該二叉樹總共有n個結(jié)點(n=n0+n1+n2)，則該二叉樹總共會有n-1條邊，度為2的結(jié)點會延伸出兩條邊，同理，度為1的結(jié)點會延伸出一條邊，則可列公式：n-1=2*n2+1*n1，合并兩個式子可得：2*n2+1*n1+1=n0+n1+n2，則計算可知

n0=n2+1。二叉樹的性質(zhì)4二叉樹的性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k為≥?log2n?+1。證明：對于一棵n個結(jié)點高度為h的完全二叉樹，有2h-1-1<n≦2h-1對不等式移項并求對數(shù)，有h-1<log2(n+1)≦h由于二叉樹的高度h只能是整數(shù)，所以取h=?log2n?+1。二叉樹的性質(zhì)5二叉樹的性質(zhì)性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的順序?qū)λ薪Y(jié)點從0開始編號，則對于序號為i的結(jié)點有：（1）如果i>0，則序號為i結(jié)點的雙親結(jié)點的序號為（i-1）/2；如果i=0，則序號i結(jié)點無雙親結(jié)點。（2）如果2i+1>n，則結(jié)點i無左孩子；否則其左孩子的序號為2i+1。（3）如果2i+2>n，則結(jié)點i無右孩子；否則其右孩子的序號為2i+2。Part03二叉樹抽象數(shù)據(jù)類型二叉樹抽象數(shù)據(jù)類型的BinaryTTree接口二叉樹抽象數(shù)據(jù)類型public

interfaceBinaryTTree<T>{

public

booleanisEmpty();//判斷是否為空

public

intcount();//統(tǒng)計二叉樹結(jié)點的個數(shù)

public

intheight();//返回二叉樹的高度

public

voidpreOrder();//先序遍歷

public

voidinOrder();//中序遍歷

public

voidpostOrder();//后序遍歷 //查找并返回首次出現(xiàn)的關(guān)鍵字為key元素結(jié)點

publicBinaryNode<T>search(Tkey);//返回node的父母結(jié)點

publicBinaryNode<T>getParent(BinaryNode<T>node);

public

voidinsertRoot(Tx);//插入元素x作為根結(jié)點

publicBinaryNode<T>insertChild(BinaryNode<T>p,Tx,boolean

leftChild);//插入孩子結(jié)點//刪除p結(jié)點的左或右子樹

public

voidremoveChild(BinaryNode<T>p,boolean

leftChild);

public

voidremoveAll();//刪除二叉樹}Part04二叉樹的存儲結(jié)構(gòu)及其實現(xiàn)1.順序存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及其實現(xiàn)二叉樹的順序存儲結(jié)構(gòu)是指用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素，即將完全二叉樹上編號為i的結(jié)點元素存儲在某個數(shù)組下標(biāo)為i-1的分量中，然后通過一些方法確定結(jié)點在邏輯上的父子和兄弟關(guān)系。完全二叉樹和滿二叉樹采用順序存儲比較合適2.鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及其實現(xiàn)二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一個鏈表來存儲一棵二叉樹，二叉樹中的每個結(jié)點用鏈表的一個鏈結(jié)點來存儲。二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲結(jié)點本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域lchild和rchild，分別指向該結(jié)點的左孩子和右孩子，如右圖所示。2.鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及其實現(xiàn)3.二叉樹的實現(xiàn)二叉樹的存儲結(jié)構(gòu)及其實現(xiàn)publicclassBinaryNode<T>{

publicTdata;//數(shù)據(jù)域，存儲數(shù)據(jù)元素//鏈域，分別指向左右孩子結(jié)點

publicBinaryNode<T>lchild,rchild;

//構(gòu)造結(jié)點，分別指定元素和左右結(jié)點

publicBinaryNode(Tdata,BinaryNode<T>lchild,BinaryNode<T>rchild){

this.data=data;

this.lchild=lchild;

this.rchild=rchild; }

……//構(gòu)造方法

……//set/get屬性方法

}使用二叉樹順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲具有17個元素的完全二叉樹。課堂實踐數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學(xué)院4.3二叉樹的遍歷引言Introduction二叉樹的遍歷是按照一定的規(guī)律來順序遍歷各二叉樹結(jié)點，使得每個結(jié)點都會被訪問且僅訪問一次。通常二叉樹的遍歷根據(jù)根結(jié)點的遍歷次序分為：先序遍歷、中序遍歷、后序遍歷。Part01先序遍歷算法思想先序遍歷若二叉樹為空，則退出，否則進行下面操作：訪問根結(jié)點先序遍歷左子樹先序遍歷右子樹算法實現(xiàn)先序遍歷publicvoidpreOrder(BinaryNode<T>p){

if

(p!=null){

System.out.print(p.data.toString()+"");

preOrder(p.lchild);

preOrder(p.rchild);

}}先序遍歷【示例8】按照先序遍歷的方式，遍歷下面的二叉樹。訪問順序為：A、B、D、H、I、E、J、C、F、G。Part02中序遍歷算法思想中序遍歷若二叉樹為空，則退出，否則進行下面操作：中序遍歷左子樹訪問根結(jié)點中序遍歷右子樹算法實現(xiàn)中序遍歷publicvoidinOrder(BinaryNode<T>p){

if

(p!=null){

inOrder(p.lchild);

System.out.print(p.data.toString()+"");

inOrder(p.rchild);

}}中序遍歷【示例9】按照中序遍歷的方式，遍歷下面的二叉樹。訪問順序為：H、D、I、B、J、E、A、F、C、G。Part03后序遍歷算法思想后序遍歷若二叉樹為空，則退出，否則進行下面操作：后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點算法實現(xiàn)后序遍歷publicvoidpostOrder(BinaryNode<T>p){

if

(p!=null){

postOrder(p.lchild);

postOrder(p.rchild);

System.out.print(p.data.toString()+"");

}}后序遍歷【示例10】按照中序遍歷的方式，遍歷下面的二叉樹。訪問順序為：H、I、D、J、E、B、F、G、C、A

。Part04二叉樹的操作二叉樹的操作二叉樹的操作二叉樹的操作有：創(chuàng)建二叉樹、求結(jié)點個數(shù)、求高度、查找、求父母結(jié)點、添加結(jié)點、清空等。二叉樹的創(chuàng)建創(chuàng)建二叉樹，一般有兩種情況：初始化一個根結(jié)點或者初始化一棵空二叉樹。代碼如下：publicclassBinaryTree<T>implementsBinaryTTree<T>{

publicBinaryNode<T>root;

publicBinaryTree(){

this.root=null;

}

publicBinaryTree(BinaryNode<T>root){

this.root=root; }

publicBinaryNode<T>getRoot(){

returnroot;

}

publicvoidsetRoot(BinaryNode<T>root){

this.root=root;

}}判斷二叉樹是否為空判斷二叉樹是否為空只需判斷根結(jié)點是否存在即可，代碼如下：publicbooleanisEmpty(){ returnthis.root==null;}求二叉樹的高度算法思想二叉樹的操作求二叉樹高度首先需要一種獲取以某個結(jié)點為子樹的高度方法，使用遞歸實現(xiàn)。如果一個結(jié)點為空，那么這個結(jié)點肯定是一顆空樹，高度為0；如果不為空，則遍歷地比較它的左右子樹高度，高的一個為這顆子樹的最大高度，然后加上自身的高度即可。求二叉樹的高度算法實現(xiàn)二叉樹的操作publicintheight(){

returnheight(this.root);}publicintheight(BinaryNode<T>p){

if

(p==null){

return

0;

}

intlh=height(p.lchild);

intlr=height(p.rchild);

return

(lh>lr)?lh+1:lr+1;}求二叉樹的結(jié)點數(shù)算法思想二叉樹的操作獲取二叉樹結(jié)點數(shù)，需要獲取以某個結(jié)點為根的子樹的結(jié)點數(shù)實現(xiàn)。如果結(jié)點為空，則個數(shù)肯定為0；如果不為空，則算上這個結(jié)點之后，繼續(xù)遞歸計算所有子樹的結(jié)點數(shù)，全部相加即可。求二叉樹的結(jié)點數(shù)算法實現(xiàn)二叉樹的操作publicintcount(){

returncount(this.root);}publicintcount(BinaryNode<T>p){

if(p==null){

return

0; }

return1+count(p.lchild)+count(p.rchild);}返回某結(jié)點的父親結(jié)點使用遞歸來獲取某個結(jié)點在某個子樹中的父結(jié)點，以現(xiàn)有的這種二叉樹的形式，沒有辦法直接獲取一個結(jié)點的父結(jié)點，只能通過從根結(jié)點遍歷來比較獲取。publicBinaryNode<T>getParent(BinaryNode<T>node){

if

(root==null||node==null||node==root){

returnnull;}

return

getParent(this.root,node);}publicBinaryNode<T>getParent(BinaryNode<T>p,BinaryNode<T>node){

if

(p==null||node==null){

returnnull;}

if

(p.lchild==node||p.rchild==node){

returnp;}

BinaryNode<T>find

=getParent(p.lchild,node);

if

(find==null){

return

getParent(p.rchild,node);}

returnfind;}返回左右子樹這個操作很簡單，直接用結(jié)點的方法來獲取即可。publicBinaryNodegetleftTree(BinaryNodenode){returnnode.getLchild();}

publicBinaryNodegetrightTree(BinaryNodenode){returnnode.getRchild();}二叉樹的插入算法思想二叉樹的操作二叉樹的插入結(jié)點分兩種情況：(1)插入某個結(jié)點的左子結(jié)點；(2)插入某個結(jié)點的右子結(jié)點。當(dāng)這個結(jié)點本身有子結(jié)點時，這樣的插入也會覆蓋原來在這個位置上的結(jié)點。另外，雖然插入的是子結(jié)點，但是子結(jié)點也可以代表一顆子樹。因為單從這個結(jié)點來看并不知道這個結(jié)點是否有左右子樹存在，所以雖然插入的是一個結(jié)點，但有可能插入可很多結(jié)點（插入的是一顆子樹）。二叉樹的插入算法實現(xiàn)二叉樹的操作//插入根結(jié)點publicvoidinsertRoot(Tx){

root=newBinaryNode<T>(x,root,null);}//插入子結(jié)點publicBinaryNode<T>insertChild(BinaryNode<T>p,Tx,BooleanlchildChild){

if

(p==null||x==null){

returnnull;

}

if

(lchildChild){

p.lchild

=newBinaryNode<T>(x,p.lchild,null);

returnp.lchild;

}

p.rchild

=newBinaryNode<T>(x,p.rchild,null);

returnp.rchild;}刪除子節(jié)點刪除子結(jié)點首先判斷左孩子是否為空，若不為空，設(shè)置左孩子為null，否則設(shè)置右孩子為null。publicvoidremoveChild(BinaryNode<T>p,booleanleftChild){

if(p!=null){

if(leftChild){

p.lchild=null; }else{

p.rchild=null; } } }查找算法思想二叉樹的操作在一棵二叉樹中查找關(guān)鍵字為key元素，返回首次出現(xiàn)的關(guān)鍵字為key元素的結(jié)點，若未找到，則返回null。該方法使用先序遍歷二叉樹進行查找，若一棵二叉樹存在多個關(guān)鍵字為key元素，返回首次出現(xiàn)元素結(jié)點，此時首次出現(xiàn)的次序由二叉樹遍歷次序決定。查找算法實現(xiàn)二叉樹的操作publicBinaryNode<T>search(Tkey){

return

search(this.root,key);}publicBinaryNode<T>search(BinaryNode<T>p,Tkey){

if

(p==null||key==null){

returnnull;

} if

(p.data.equals(key)){

returnp;

}

BinaryNode<T>find

=search(p.lchild,key);

if

(find==null){

find

=search(p.rchild,key);}

returnfind;}二叉樹的清空對于二叉樹的清空，首先提供一個清空某個結(jié)點為根結(jié)點的子樹的方法，即遞歸的刪除每個結(jié)點；接著提供刪除一個刪除樹的方法。publicvoid

clear(BinaryNodenode){if(node!=null){clear(node.getLchild());clear(node.getRchild());node=null;//刪除結(jié)點}}//清空樹publicvoidclear(){clear(root);}Part05確定二叉樹確定二叉樹確定二叉樹二叉樹先序遍歷先訪問根結(jié)點D，其次訪問左子樹L，然后遍歷右子樹R。即在先序遍歷序列中，第一個結(jié)點必為根結(jié)點；而在中序遍歷時，先遍歷左子樹L，然后訪問根結(jié)點D，最后訪問右子樹R，因此中序遍歷序列被根結(jié)點分為兩部分：根結(jié)點之前部分為左子樹結(jié)點中序序列，根結(jié)點之后的為右子樹結(jié)點中序序列。通過這兩部分再到先序序列中找到左右子樹的根結(jié)點，依次類推，便可唯一得到一顆二叉樹。二叉樹的先序序列與中序序列可以唯一確定一棵二叉樹。確定二叉樹【示例11】已知一顆二叉樹的先序序列為EBADCFHG，其中序序列為ABCDEFGH，下圖說明了還原二叉樹的過程。由后序和中序遍歷序列也可以唯一確定一棵二叉樹。其方法與上述方法類似，只不過此時根結(jié)點出現(xiàn)在后序序列的最后面。由先序和后序序列不能唯一確定一棵二叉樹。例如先序序列為AB，后序序列為BA。此時就無法確定二叉樹的結(jié)構(gòu)，因為B既可以是根A的左子樹，也可以是根A的右子樹。數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學(xué)院4.4線索二叉樹引言Introduction在使用二叉鏈表的存儲結(jié)構(gòu)的過程中，會存在大量的空指針域，通過充分利用二叉鏈表中的空指針域，存放結(jié)點在某種遍歷方式下的前驅(qū)和后繼結(jié)點的指針。我們把這種指向前驅(qū)和后繼的指針成為線索，加上線索的二叉鏈表成為線索鏈表，對應(yīng)的二叉樹就成為線索二叉樹(ThreadedBinaryTree)。Part01線索二叉樹定義

通過充分利用二叉鏈表中的空指針域，存放結(jié)點在某種遍歷方式下的前驅(qū)和后繼結(jié)點的指針。我們把這種指向前驅(qū)和后繼的指針成為線索，加上線索的二叉鏈表成為線索鏈表。線索鏈表區(qū)分線索二叉樹與普通二叉樹線索二叉樹定義

為了區(qū)別每條鏈到底是指向孩子結(jié)點還是線索，每一個結(jié)點需要增加兩個線索標(biāo)記ltag和rtag，定義如下：中序線索二叉樹的二叉鏈表結(jié)構(gòu)線索二叉樹定義

H沒有前驅(qū)，H的left域為空，約定ltag=1；G沒有后繼，G的right域為空，約定rtag=1publicclassThreadNode<T>{//T指定結(jié)點的元素類型

publicTdata;//數(shù)據(jù)元素

publicThreadNode<T>left,right;//分別指向左、右孩子結(jié)點

publicintltag,rtag;//左、右線索標(biāo)記

……..//省略構(gòu)造方法

//構(gòu)造指定值結(jié)點

publicThreadNode(Tdata){

this(data,null,0,null,0); }

publicThreadNode(){

this(null,null,0,null,0); }

publicbooleanisLeaf(){//判斷是否葉子結(jié)點

returnthis.ltag==1&&this.rtag==1; }}二叉鏈表結(jié)點類ThreadNode二叉鏈表結(jié)點類聲明Part02中序遍歷線索二叉樹中序線索二叉樹類中序遍歷線索二叉樹在中序線索二叉樹中，不僅能夠直接求得任意一個結(jié)點在中根次序下的前驅(qū)和后繼結(jié)點，還能夠很方便的求得其在先序遍歷下的后繼結(jié)點和后序遍歷下的前驅(qū)結(jié)點，使得二叉樹的先序、中序、后序遍歷算法都是非遞歸的，并且不使用棧。public

classThreadBinaryTree<T>{

publicThreadNode<T>root;

//構(gòu)造空中序線索二叉樹

publicThreadBinaryTree(){

this.root=null;}

//判斷中序線索二叉樹是否空

public

booleanisEmpty(){

return

root==null;}

//以標(biāo)明空子樹的先根序列構(gòu)造二叉樹并進行中序線索化

publicThreadBinaryTree(T[]prelist){

this.root=create(prelist);inorderThread(this.root);}……}

//以標(biāo)明空子樹的先根序列構(gòu)造一棵子二叉樹，子樹的根值是prelist[i]，返回所創(chuàng)建子樹的根結(jié)點

private

int

i=0;

privateThreadNode<T>create(T[]prelist){ThreadNode<T>p=null;

if(i<prelist.length){Telem=prelist[i++];

if(elem!=null){

p=newThreadNode<T>(elem);

p.left=create(prelist);

p.right=create(prelist);}}

return

p;}構(gòu)造一棵子二叉樹中序遍歷線索二叉樹中序線索化以p結(jié)點為根的子樹中序遍歷線索二叉樹

privateThreadNode<T>front=null;

private

voidinorderThread(ThreadNode<T>p){

if(p!=null){inorderThread(p.left);//中序線索化p的左子樹

if(p.left==null){//若p的左子樹為空

p.ltag=1;//設(shè)置左線索標(biāo)記

p.left=front;//設(shè)置p.left為指向前驅(qū)front的線索}

if(p.right==null)//若p的右子樹為空

p.rtag=1;//設(shè)置右線索標(biāo)記

if(front!=null&&front.rtag==1)

front.right=p;//設(shè)置前驅(qū)front.right為指向后繼p的線索

front=p;inorderThread(p.right);//中序線索化p的右子樹}}中根次序遍歷中序線索二叉樹（非遞歸算法）中序遍歷線索二叉樹

publicThreadNode<T>inNext(ThreadNode<T>p){

if(p.rtag==1)//若右子樹為空

p=p.right;//p.right就是指向后繼結(jié)點的線索

else{

p=p.right;//若右子樹非空，進入右子樹

while(p.ltag==0)//找到最左邊的后代結(jié)點

p=p.left;}

return

p;}返回p在中根次序下的后繼結(jié)點中根次序遍歷中序線索二叉樹

public

voidinOrder(){System.out.print("中根次序遍歷中序線索二叉樹：");ThreadNode<T>p=this.root;

//尋找根的最左邊的后代結(jié)點，即第一個訪問結(jié)點

while(p!=null&&p.ltag==0)

p=p.left;

while(p!=null){System.out.print(p.data.toString()+"");

p=this.inNext(p);//返回p在中根次序下的后繼結(jié)點}System.out.println();}先根次序遍歷中序線索二叉樹（非遞歸算法）先根遍歷中序線索二叉樹publicThreadNode<T>preNext(ThreadNode<T>p){

if(p.ltag==0)//若左子樹非空

p=p.left;//左孩子就是p的后繼結(jié)點

else{//后繼是右兄弟或某個中序祖先的右孩子//尋找某個中序祖先

while(p.rtag==1&&p.right!=null)

p=p.right;//后繼是其某個中序祖先的右孩子

p=p.right;//右孩子是p的后繼結(jié)點}

return

p;}返回p在先根次序下的后繼結(jié)點先根次序遍歷中序線索二叉樹

public

voidpreOrder(){System.out.print("先根次序遍歷中序線索二叉樹：");for(ThreadNode<T>p=this.root;p!=null;p=preNext(p))

//返回p在先根次序下的后繼結(jié)點System.out.print(p.data.toString()+"");System.out.println();}線索二叉樹測試中序遍歷線索二叉樹publicclassThreadBinaryTree_ex{publicstaticvoidmain(Stringargs[]){String[]prelist={"A","B","D",null,null,"E","G",null,null,null,"C","F",null,"H",null,null,"K"};//創(chuàng)建中序線索二叉樹 ThreadBinaryTree<String>tbitree=newThreadBinaryTree<String>(prelist);//先根次序遍歷tbitree.preOrder();//中根次序遍歷tbitree.inOrder();}}數(shù)據(jù)結(jié)構(gòu)常州信息職業(yè)技術(shù)學(xué)院感謝您的耐心觀看數(shù)據(jù)結(jié)構(gòu)主講人：蔣衛(wèi)祥常州信息職業(yè)技術(shù)學(xué)院4.5Huffman樹引言IntroductionHuffmanTree，中文名是哈夫曼樹或霍夫曼樹，它是最優(yōu)二叉樹。哈夫曼樹的應(yīng)用很廣，在不同的應(yīng)用中葉子結(jié)點的值可以有不同的解釋。當(dāng)哈夫曼樹應(yīng)用到信息編碼中，權(quán)值可看成是某個符號出現(xiàn)的頻率：當(dāng)應(yīng)用到判定過程中，可看成是某類數(shù)據(jù)出現(xiàn)的頻率；當(dāng)應(yīng)用到排序問題中，可看成是已排好次序而待合并的序列的長度等等。Part01Huffman樹基本概念給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若樹的帶權(quán)路徑長度達到最小，則這棵樹被稱為哈夫曼樹（HuffmanTree）。基本概念

在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。

通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。路徑和路徑長度100和80的路徑長度是1，50和30的路徑長度是2，20和10的路徑長度是3。哈夫曼樹結(jié)點的權(quán)及帶權(quán)路徑長度哈夫曼樹結(jié)點20的路徑長度是3，它的帶權(quán)路徑長度=路徑長度*權(quán)=3*20=60

若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。

結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。樹的帶權(quán)路徑長度哈夫曼樹樹的WPL=1*100+2*50+3*20+3*10=100+100+60+30=290

樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL。比較兩棵二叉樹WPL哈夫曼樹右邊樹的WPL=1*100+2*50+3*20+3*10=290左邊樹的WPL=2*10+2*20+2*50+2*100=360Part02哈夫曼樹的構(gòu)造假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。n個權(quán)值分別設(shè)為w1、w2、…、wn，哈夫曼樹的構(gòu)造規(guī)則為：將w1、w2、…，wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點)；在森林中選出根結(jié)點權(quán)值最小的兩棵樹進行合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；從森林中刪除選取的兩棵樹，并將新樹加入森林；重復(fù)

、

步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。哈夫曼樹的構(gòu)造規(guī)則哈夫曼樹的構(gòu)造以{5,6,7,8,15}為例，來構(gòu)造一棵哈夫曼樹哈夫曼樹的構(gòu)造哈夫曼樹構(gòu)造實例步驟一哈夫曼樹構(gòu)造實例步驟二哈夫曼樹構(gòu)造實例步驟三以{5,6,7,8,15}為例，來構(gòu)造一棵哈夫曼樹哈夫曼樹的構(gòu)造哈夫曼樹構(gòu)造實例步驟四哈夫曼樹構(gòu)造實例步驟五創(chuàng)建哈夫曼樹-算法實現(xiàn)哈夫曼樹的構(gòu)造算法實現(xiàn)//創(chuàng)建哈夫曼樹public

voidcreateTree(){

//創(chuàng)建優(yōu)先隊列Queue<Node>q1=newPriorityQueue<Node>(

newComparator<Node>(){

public

intcompare(Nodeo1,Nodeo2){

return

o1.count-o2.count; }});

//將結(jié)點列表加入到隊列中

q1.addAll(nodes);

//如果隊列不為空

while(!q1.isEmpty()){

//出隊一個結(jié)點 Noden1=q1.poll();

//出隊一個結(jié)點 Noden2=q1.poll();

//通過兩個結(jié)點創(chuàng)建父節(jié)點Nodeparent=newNode(n1,n2,n1.count+n2.count);

//如果隊列為空

if(q1.isEmpty()){

root=parent;

return;}

//將父節(jié)點加入到隊列中

q1.add(parent);}}Part03Huffman樹的應(yīng)用1.優(yōu)化判斷過程Huffman樹的應(yīng)用

將百分制轉(zhuǎn)換成五級制的算法。顯然，此算法很簡單，只需利用if語句描述即可。

如果學(xué)生規(guī)模很大，該算法需反復(fù)多次執(zhí)行，就應(yīng)該考慮算法執(zhí)行的時間問題。在實際應(yīng)用中，學(xué)生的成績呈正態(tài)分布，大部分在70~89分之間，優(yōu)秀和不及格的概率較小。假設(shè)不及格、及格、中、良、優(yōu)的百分比為5％、12%、40%、35%、8%，則上述算法80%以上的成績需要進行三次或三次以上的比較才能得到結(jié)果。1.優(yōu)化判斷過程Huffman樹的應(yīng)用

若以這些百分比值5,12,40,35,8為權(quán)值，使用哈夫曼算法來構(gòu)造一棵判定樹，則得到的判定過程，可使多數(shù)成績經(jīng)過較少的比較即可得到結(jié)果。

未使用哈夫曼樹判定

使用哈夫曼樹判定2.哈夫曼編碼Huffman樹的應(yīng)用

在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進制的字符串，用0，1碼的不同排列來表示字符。需傳送的報文為“AFTER

DATA

EARAREARTAREA”，這里用到的字符集為“A，E，R，T，F(xiàn)，D”，各字母出現(xiàn)的次數(shù)為{8，4，5，3，1，1}，現(xiàn)要求為這些字母設(shè)計編碼。要區(qū)別6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分別用000、001、010、011、100、101對“A，E，R，T，F(xiàn)，D”進行編碼發(fā)送。算法分析在實際應(yīng)用中，各個字符的出現(xiàn)頻度或使用次數(shù)是不相同的，讓使用頻率高的用短碼，使用頻率低的用長碼，以優(yōu)化整個報文編碼。（非等長編碼）設(shè)計時能夠保證任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴，符合此要求的編碼稱為前綴編碼。2.哈夫曼編碼Huffman樹的應(yīng)用public

classTreeNode{ Characterch;//ch存儲當(dāng)前結(jié)點字符

int

val;

//若在構(gòu)建二叉樹的過程中該結(jié)點為左結(jié)點，則val=0,反之，val=1

int

freq;//存儲字符出現(xiàn)的頻次 TreeNodeleft;//左結(jié)點 TreeNoderight;//右結(jié)點

public

TreeNode(){

}

結(jié)點數(shù)據(jù)結(jié)構(gòu)有參數(shù)構(gòu)造方法publicTreeNode(Characterch,int

val,int

freq,TreeNodeleft,TreeNoderight){

this.ch=ch;

this.val=val;

this.freq=freq;

this.left=left;

this.right=right; }}2.哈夫曼編碼Huffman樹的應(yīng)用初始化二叉樹結(jié)點判斷表空

選擇最小頻率的兩個結(jié)點組成一顆二叉樹2.哈夫曼編碼Huffman樹的應(yīng)用選擇最小頻率的兩個結(jié)點組成二叉樹判斷表空哈夫曼編碼最終二叉樹2.哈夫曼編碼Huffman樹的應(yīng)用判斷表空字符哈夫曼編碼表使用哈夫曼編碼的報文的最短傳送長度為：

6

L=WPL=(wklk)=4×2+5×2+8×2+3×3+1×4+1×4=51

k=1若采用等長編碼，報文的傳送長度為：L=8×3+4×3+5×3+3×3+1×3+1×3=662.哈夫曼編碼Huffman樹的應(yīng)用//遍歷dataMap,初始化二叉樹結(jié)點，并將所有初始化后的結(jié)點放到nodeList中，并進行排序LinkedList<TreeNode>nodeList=newLinkedList<TreeNode>();for(Map.Entry<Character,Integer>entry:dataMap.entrySet()){ Characterch=entry.getKey();

int

freq=entry.getValue();

int

val=0; TreeNodetmp=newTreeNode(ch,val,freq,null,null);

odeList.add(tmp);}//對存放結(jié)點的鏈表進行排序，方便后續(xù)進行組合Collections.sort(nodeList,newC