數(shù)據(jù)結(jié)構(gòu)教程第二十一課樹(shù)、二叉樹(shù)定義及術(shù)語(yǔ)

教學(xué)目的： 掌握樹(shù)、二叉樹(shù)的基本概念和術(shù)語(yǔ)，二叉樹(shù)的性質(zhì)
    教學(xué)重點(diǎn)： 二叉樹(shù)的定義、二叉樹(shù)的性質(zhì)
    教學(xué)難點(diǎn)： 二叉樹(shù)的性質(zhì)
    授課內(nèi)容：
    一、樹(shù)的定義：
    樹(shù)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中：
    (1)有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；
    (2)當(dāng)n>1時(shí),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,...Tm,其中每一個(gè)集合本身又是一棵樹(shù),并且稱(chēng)為根的子樹(shù).
    二、樹(shù)的基本概念：
    樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。三、二叉樹(shù)的定義
    二叉樹(shù)是另一種樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)),并且,二叉樹(shù)的子樹(shù)有左右之分,其次序不能任意顛倒。
    一棵深度為k且有2(k)-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿二叉樹(shù)，如圖(a)，按圖示給每個(gè)結(jié)點(diǎn)編號(hào)，如果有深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(shù)。
    二叉樹(shù)的定義如下：
    ADT BinaryTree{
    數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。
    數(shù)據(jù)關(guān)系R:
    基本操作P:
    InitBiTree(&T);
    DestroyBiTree(&T);
    CreateBiTree(&T,definition);
    ClearBiTree(&T);
    BiTreeEmpty(T);
    BiTreeDepth(T);
    Root(T);
    Value(T,e);
    Assign(T,&e,value);
    Parent(T,e);
    LeftChild(T,e);
    RightChild(T,e);
    LeftSibling(T,e);
    RightSibling(T,e);
    InsertChild(T,p,LR,c);
    DeleteChild(T,p,LR);
    PreOrderTraverse(T,visit());
    InOrderTraverse(T,visit());
    PostOrderTraverse(T,visit());
    LevelOrderTraverse(T,Visit());
    }ADT BinaryTree
    三、二叉樹(shù)的性質(zhì)
    性質(zhì)１： 在二叉樹(shù)的第i層上至多有2的i-1次方個(gè)結(jié)點(diǎn)(i>=1)。
    性質(zhì)２： 深度為k的二叉樹(shù)至多有2的k次方減1個(gè)結(jié)點(diǎn)(k>=1)。
    性質(zhì)３： 對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。
    性質(zhì)４： 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為|log2n|+1
    性質(zhì)５： 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1=    (1)如果i=1,則結(jié)點(diǎn)i是二叉樹(shù)的根,無(wú)雙親;如果i>1,則雙親PARENT(i)是結(jié)點(diǎn)i/2
    (2)如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子LCHILD(i)是結(jié)點(diǎn)2i
    (3)如果2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子;否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+1
    結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為結(jié)點(diǎn)的度。
    度為0的結(jié)點(diǎn)稱(chēng)為葉子或終端結(jié)點(diǎn)。
    度不為0的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。
    樹(shù)的度是樹(shù)內(nèi)各結(jié)點(diǎn)的度的大值。
    結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子，相應(yīng)地，該結(jié)點(diǎn)稱(chēng)為孩子的雙親。
    同一個(gè)雙親的孩子之間互稱(chēng)兄弟。
    結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。
    以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的子孫。
    結(jié)點(diǎn)的層次從根開(kāi)始定義起，根為第一層，根的孩子為第二層。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹(shù)中結(jié)點(diǎn)的大層次稱(chēng)為樹(shù)的深度，或高度。
    如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的，則稱(chēng)該樹(shù)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。
    森林是m(m>=0)棵互不相交的樹(shù)的集合。