數(shù)據(jù)結構主講人：蔣衛(wèi)祥常州信息職業(yè)技術學院4.2二叉樹引言Introduction二叉樹（BinaryTree）是一種重要的樹結構，它的特點是每一個結點最多只能有兩棵子樹。二叉樹的遞歸定義如下：二叉樹或者是一棵空樹，或者是一棵由一個根結點和兩棵互不相交的分別稱為根的左子樹和右子樹的子樹所組成的非空樹。Part01二叉樹定義與分類二叉樹（BinaryTree）是一種重要的樹結構，它的特點是每一個結點最多只能有兩棵子樹。二叉樹的遞歸定義如下：二叉樹或者是一棵空樹，或者是一棵由一個根結點和兩棵互不相交的分別稱為根的左子樹和右子樹的子樹所組成的非空樹。二叉樹遞歸定義二叉樹中每一個結點的孩子只能是0、1、或2個二叉樹定義與分類二叉樹的基本形態(tài)二叉樹定義與分類二叉樹5種基本形態(tài)一棵深度為k且有2k?1個結點的二叉樹稱為滿二叉樹。滿二叉樹具有以下特點：①每一層上的結點數(shù)都達到最大值，即對給定的高度，它是具有最多結點數(shù)的二叉樹；②滿二叉樹中不存在度數(shù)為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層。滿二叉樹二叉樹定義與分類在一棵二叉樹中，除了最后一層，都是滿的，并且最后一層或者是滿的，或者是右邊缺少連續(xù)若干結點，成為完全二叉樹。滿二叉樹具有以下特點：①葉子結點只能在最大的一層或最多只能在層次最大的兩層上出現(xiàn)；②對任一結點，若其右分支下子孫的最大層次為n（n≥1），則其左分支下的子孫最大層次不小于n；③若是滿二叉樹，則必定是完全二叉樹，反之不一定成立。完全二叉樹二叉樹定義與分類Part02二叉樹的性質二叉樹的性質1二叉樹的性質性質1：若規(guī)定根結點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2i-1個結點，其中i≥1。證明：假設樹非空，用數(shù)學歸納法證明。(1)當i=1時，因為第1層上只有一個根結點，而2i?1=20=1，命題成立。(2)設第i?1層上至多有2i?2

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

個結點，命題成立。二叉樹的性質2二叉樹的性質

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

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

interfaceBinaryTTree<T>{

public

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

public

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

public

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

public

voidpreOrder();//先序遍歷

public

voidinOrder();//中序遍歷

public

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

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

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

public

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

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

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

public

voidremoveChild(BinaryNode<T>p,boolean

leftChild);

public

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

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

publicBinaryNode<T>lchild,rchild;

//構造結點，分別指定元素和左右結點

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

this.data=data;

this.lchild=lchild