午伊人久久,久久久久9999资源,婷婷久久网

9.1基本概念

結(jié)點(diǎn)的度——結(jié)點(diǎn)掛接的子樹數(shù)；
樹的度——所有結(jié)點(diǎn)度中的最大值；
樹的深度——指所有結(jié)點(diǎn)中最大的層數(shù)；

注意區(qū)分完全二叉樹與滿二叉樹。
完全二叉樹：只有最后一層葉子不滿，且全部集中在左邊。

9.2二叉樹性質(zhì)

二叉樹的第i層上至多有2^i-1個(gè)結(jié)點(diǎn)。
深度為k的二叉樹至多有2ⁱ-1個(gè)結(jié)點(diǎn)，至少有k個(gè)結(jié)點(diǎn)。
具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為 $\lfloor logx \rfloor$ +1。
對于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)n0必定為n2＋1 （即n0=n2+1）。
例題：一棵完全二叉樹有5000個(gè)結(jié)點(diǎn)，可以計(jì)算出其葉結(jié)點(diǎn)的個(gè)數(shù)是（）
解題過程：完全二叉樹有5000個(gè)結(jié)點(diǎn)，則最后一個(gè)結(jié)點(diǎn)序號是5000，根據(jù)完全二叉樹結(jié)點(diǎn)i和左右孩子關(guān)系知，左結(jié)點(diǎn)為2i必為偶數(shù)，右節(jié)點(diǎn)為2i+1必為奇數(shù)，所以本題中最后結(jié)點(diǎn)為左結(jié)點(diǎn)，其雙親結(jié)點(diǎn)為2500，且2500是最后一個(gè)非葉子結(jié)點(diǎn)，則二叉樹度為2的結(jié)點(diǎn)有n2=2500-1個(gè)，葉子結(jié)點(diǎn)數(shù)n0=n2+1=2500個(gè)。故本題答案為2500。

9.3二叉樹的存儲

二叉樹可以用順序、鏈?zhǔn)絻煞N存儲方式，順序存儲浪費(fèi)空間，適于存滿二叉樹和完全二叉樹。方法為：現(xiàn)將二叉樹轉(zhuǎn)化為完全二叉樹，再從根節(jié)點(diǎn)開始，按照層次依次將樹中節(jié)點(diǎn)存儲到數(shù)組即可。

一般二叉樹建議用鏈?zhǔn)酱鎯ΑＬ匦裕涸趎個(gè)結(jié)點(diǎn)的二叉鏈表中，必有2n個(gè)鏈域，有n+1個(gè)空指針域。

typedef struct BiNode{ //二叉鏈表
   TElemType   data;
   struct  BiNode   *lchild,*rchild; //左右孩子指針
}BiNode,*BiTree;

9.4先序生成二叉樹

int Create_BiTree(BTree &T){
    char ch;
    cin>>ch;
    if(ch=='#'){
        T=NULL;
        return -1; 
    }else{
        T=new BTNode;
        T->data=ch;
        Create_BiTree(T->lchild);
        Create_BiTree(T->rchild);
    }
    return 0;
}

9.5遍歷二叉樹

三種遍歷方式：
DLR—先序遍歷，即先根再左再右
LDR—中序遍歷，即先左再根再右
LRD—后序遍歷，即先左再右再根

二叉樹的遍歷

int PreTrav(BTree T){    //先序遍歷舉例
    if(T) {
        cout<<T->data<<' ';
        PreTrav(T->lchild);
        PreTrav(T->rchild);
    }
    return 0;
}

性質(zhì)：由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。
例題：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG 和 DECBHGFA，請畫出這棵二叉樹。
分析：
①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（A）；
②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹子孫（BDCE），其右部必全部是右子樹子孫（FHG）；
③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。

9.6計(jì)算葉子結(jié)點(diǎn)個(gè)數(shù)

思路：二叉樹的拓?fù)浣Y(jié)構(gòu)，涉及三種形式的結(jié)點(diǎn)（空點(diǎn)（樹），葉子結(jié)點(diǎn)，中間結(jié)點(diǎn)）處理，算法還通常運(yùn)用樹左右孩子的遞歸，要考慮上述要素在不同場景中的運(yùn)算邏輯。
如果將二叉樹看成如下形式：

以A為根結(jié)點(diǎn)，左右孩子分別是B、F兩棵子樹。本例空點(diǎn)（樹）返回0，葉結(jié)點(diǎn)返回1（計(jì)數(shù)為1），中間結(jié)點(diǎn)為做子樹葉結(jié)點(diǎn)數(shù)+右子樹葉結(jié)點(diǎn)數(shù)。

int CountBTLeafNode(BTree T){
    int num;
    if (!T){
        return 0;
    }else if(T->lchild==NULL && T->rchild==NULL){
        return 1;
    }else{
        num=CountBTLeafNode(T->lchild)+CountBTLeafNode(T->rchild);
    }
    return num;
}

9.7求二叉樹的深度

思路：同9.6的思想，空點(diǎn)返回0，葉結(jié)點(diǎn)返回1（深度為1），中間結(jié)點(diǎn)為左子樹深度和右子樹深度較大的那個(gè)。

int CountBTDepth(BTree T){
    int mnum;
    if(!T){return 0;
    }else{
        if(CountBTDepth(T->lchild)>CountBTDepth(T->rchild)){
            mnum=CountBTDepth(T->lchild)+1;
        }else{
            mnum=CountBTDepth(T->rchild)+1;
        }
    }
    return mnum;
}

二叉樹深度算法是根據(jù)二叉樹的拓?fù)浣Y(jié)構(gòu)結(jié)合遞歸而來。

9.8求二叉樹的寬度

思路：二叉樹的寬度是指二叉樹各層結(jié)點(diǎn)個(gè)數(shù)的最大值。因?yàn)槭墙y(tǒng)計(jì)各層，所以這里用到一種新的思路——層級遍歷，并結(jié)合隊(duì)列實(shí)現(xiàn)。隊(duì)列暫存樹父子結(jié)點(diǎn)，width記憶父節(jié)點(diǎn)的數(shù)量（也就是各層寬度）。初始化是根結(jié)點(diǎn)入隊(duì)，隨后就是不斷出隊(duì)直到隊(duì)列為空，但是每次出隊(duì)width都會減一，并將該結(jié)點(diǎn)的左右孩子入隊(duì)，width減到0說明一個(gè)層級已遍歷好，此時(shí)隊(duì)列長度就是下一層的結(jié)點(diǎn)數(shù)（也就是寬度），更新width為隊(duì)列長度，并進(jìn)行下輪循環(huán)（直到隊(duì)列為空）。maxwidth用來記憶最大的層級。
過程：
（1）初始根結(jié)點(diǎn)A層級為i=1，A入隊(duì)，隊(duì)列寬度width=1，maxwidth=1；
（2）出隊(duì)A，width--，同時(shí)將A的左右孩子B和C入隊(duì)，判斷width=0，更新width為隊(duì)列長度width=2，i（層級）自加為2，判斷新width和maxwidth大小取大；
（3）出隊(duì)B，width--，同時(shí)將B的左右孩子D和E入隊(duì)，判斷width=1不為零，繼續(xù)出隊(duì)C，width--，同時(shí)將C的左右孩子F入隊(duì)，判讀width=0，更新width為隊(duì)列長度3，i自加為3，判斷maxwidth取大；
（4）依次循環(huán)，直到隊(duì)列為空；

int BTWidth(BTNode *b)
{
    if(b == NULL)   //為空樹，返回寬度為0
        return 0;

    int width, max;
    int i = 1, max_i; //初始化二叉樹層次i，最大寬度所在層次max_i
    BTNode *p;
    SqQueue<BTree> qu;       
    Initial_SqQueue(qu);     //初始化層次遍歷需要借助的隊(duì)列
    Push_SqQueue(qu, b);    //樹不為空，根節(jié)點(diǎn)進(jìn)隊(duì)
    width = 1;         // 寬度置為1
    max = width;       //最大寬度為1
    max_i = i;         //最大寬度所在層次

    while(!IfSqQueue_Empty(qu))   //隊(duì)列為空，表明二叉樹遍歷完畢，退出循環(huán)
    {
        Pop_SqQueue(qu, p);      //節(jié)點(diǎn)出隊(duì)，賦給p
        width --;            //出隊(duì)一次，width減1
        if(p -> lchild != NULL) //出隊(duì)節(jié)點(diǎn)的左孩子進(jìn)隊(duì)
            Push_SqQueue(qu, p -> lchild);
        if(p -> rchild != NULL)
            Push_SqQueue(qu, p -> rchild); //出隊(duì)節(jié)點(diǎn)的右孩子出隊(duì)

        if(width == 0)  //width == 0，表示當(dāng)前層次i所有節(jié)點(diǎn)已遍歷完畢
        {               //此時(shí)隊(duì)列元素個(gè)數(shù)即為下一層次 i + 1 的節(jié)點(diǎn)個(gè)數(shù)
            width = SqQueue_Length(qu);  //更新寬度
            i++;     //層次變?yōu)橄乱粚?i + 1
            if(width > max)  //如果層次 i + 1 寬度 > max
            {
                max = width;  //更新max
                max_i = i;   //并記錄最大寬度所在層次
            }
        }
    }

    printf("二叉樹層次 %d 的寬度最大\n", max_i);
    return max;
}

9.9復(fù)制二叉樹

思路：先復(fù)制根結(jié)點(diǎn)，再復(fù)制左右子樹。

int CopyBTree(BTree NT,BTree T){
      if(!T){NT=NULL;return 0;
      }else{
          NT=new BTree;
          NT->data=T->data;
          CopyBTree(NT->lchild,T->lchild);
          CopyBTree(NT->rchild,T->rchild);
      }
}

9.10判斷二叉樹是否相等

思路：空點(diǎn)（樹）只有同時(shí)為空時(shí)才相等，非空結(jié)點(diǎn)（樹）先判斷根結(jié)點(diǎn)data是否相等，然后是左子樹是否相等，再是右子樹是否相等（遞歸），也就是采用先序遍歷的方式。

int IsSame(BTree T1,BTree T2){
    if(T1==NULL&&T2==NULL){
        return 1;
    }else if(T1==NULL||T2==NULL){
        return 0;
    }else if(T1->data ==T2->data){
        if(!IsSame(T1->lchild,T2->lchild)){
            return 0;
        }
        if(!IsSame(T1->rchild,T2->rchild)){
            return 0;
        }
        return 1;
    }else{
        return 0;
    }
}

9.11交換二叉樹每個(gè)結(jié)點(diǎn)的左右孩子

思路：要交換左右孩子（子樹）前提是根結(jié)點(diǎn)要存在，此外對于葉子結(jié)點(diǎn)沒有交換的必要。

int ChangeLR(BTree &T)
{
    BTree temp;
    if(T->lchild==NULL&&T->rchild==NULL)
        return 0;
    else
    {
        temp = T->lchild;
        T->lchild = T->rchild;
        T->rchild = temp;
    }//交換左右孩子
    ChangeLR(T->lchild);  //遞歸交換左子樹
    ChangeLR(T->rchild);  //遞歸交換右子樹
}

9.12輸出二叉樹中從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑

思路：先序遍歷二叉樹，當(dāng)發(fā)現(xiàn)葉子結(jié)點(diǎn)時(shí)輸出路徑序列。先序遍歷一定是先遍歷出最左端的葉子結(jié)點(diǎn)路徑，用數(shù)組v[num]記錄遍歷中各結(jié)點(diǎn)的data，用len記憶遍歷遞歸次數(shù)，當(dāng)達(dá)到最左端葉子結(jié)點(diǎn)時(shí)，先輸出其data，再輸出數(shù)組中的序列。后面的遍歷都是根據(jù)當(dāng)前遞歸層級的len初始，去繼續(xù)修改v[num]數(shù)組，當(dāng)達(dá)到葉子結(jié)點(diǎn)時(shí)輸出序列。

int LeafNodePath(BTree T,char *v,int len){
    if(!T){
        return 0;
    }else if(T->lchild==NULL&&T->rchild==NULL){
        printf("%c",T->data);
        for(int i=len;i>=0;i--){
            printf("%c",v[i-1]);
        }
        printf("\n");
        return 0;
    }else{
        v[len]=T->data;len++;
        LeafNodePath(T->lchild,v,len);
        LeafNodePath(T->rchild,v,len);
    }
    return 0;
}

9.13求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值

思路：9.11我們已經(jīng)實(shí)現(xiàn)各葉子結(jié)點(diǎn)路徑遍歷，只要再增加變量maxpath[num]和maxlen，當(dāng)達(dá)到葉子結(jié)點(diǎn)時(shí)不是執(zhí)行打印，而是比較v和maxpath的數(shù)組長度，若v大則將v數(shù)組復(fù)制到maxpath。

int MaxPath(BTree T,char *v,int len,char *maxpath,int &maxlen){
    if(!T){
        return 0;
    }else if(T->lchild==NULL&&T->rchild==NULL){
        v[len]=T->data;
        if(len+1>maxlen){
            maxlen=len+1;
            for(int i=0;i<maxlen;i++){
                maxpath[i]=v[len-i];
            }
        }
        return 0;
    }else{
        v[len]=T->data;len++;
        MaxPath(T->lchild,v,len,maxpath,maxlen);
        MaxPath(T->rchild,v,len,maxpath,maxlen);
    }
    return 0;
}

9.14二叉樹和樹的相互轉(zhuǎn)換

9.14.1樹轉(zhuǎn)換為二叉樹

樹轉(zhuǎn)化為二叉樹用的是孩子兄弟表示法，即二叉樹結(jié)點(diǎn)的左孩子為樹結(jié)點(diǎn)的第一個(gè)孩子，二叉樹結(jié)點(diǎn)右孩子為樹結(jié)點(diǎn)的第一個(gè)兄弟。
結(jié)構(gòu)：

示例：

9.14.2二叉樹轉(zhuǎn)換為樹

示例：

9.14.3森林轉(zhuǎn)換為二叉樹

森林轉(zhuǎn)換為二叉樹的步驟是：
（1）先把每棵樹轉(zhuǎn)換為二叉樹；
（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，用線連接起來。當(dāng)所有的二叉樹連接起來后得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。
示例：

9.15哈夫曼樹

帶權(quán)路徑長度最小的樹。核心思想：使權(quán)大的結(jié)點(diǎn)靠近根。
性質(zhì)：
一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹有2n-1個(gè)結(jié)點(diǎn)。因?yàn)閺墓蚵鼧湫纬蓙砜?，初始結(jié)點(diǎn)最終一定在葉子的位置，上面都是新增的結(jié)點(diǎn)，4個(gè)結(jié)點(diǎn)的哈夫曼樹最終一定新增三個(gè)結(jié)點(diǎn)。
構(gòu)造過程：

哈夫曼結(jié)點(diǎn)和哈夫曼樹定義：

typedef struct HFNode{
    int weight;
    int lchild,rchild,parent;
}HFNode;

typedef struct HFTree{
    HFNode *v;
    int len;
}HFTree;

哈夫曼樹的構(gòu)建：

HFTree Create_HFTree(int V[],int num){//V[]為權(quán)值序列
    HFTree HF;int i;
    HF.len=2*num-1;
    HF.v=new HFNode[HF.len];
    //第一步，構(gòu)造num棵樹，初始化 
    for (i=0;i<num;i++){
        HF.v[i].weight=V[i];
        HF.v[i].lchild=HF.v[i].rchild=HF.v[i].parent=0;
    }
    //第二步，選擇權(quán)值最小兩棵樹，形成新的樹 
    int s1,s2;
    for (i;i<HF.len;i++){
        SelectNode(HF,i,s1,s2);
        HF.v[i].lchild=s1;
        HF.v[i].rchild=s2;
        HF.v[s1].parent=i;
        HF.v[s2].parent=i;
        HF.v[i].weight=HF.v[s1].weight+HF.v[s2].weight;
    }
    return HF;
}

說明1：SelectNode()有兩個(gè)返回值s1和s2，C語言不支持兩個(gè)返回值的寫法s1,s2=SelectNode(HF,i)，只能用示例傳參引用的方式實(shí)現(xiàn)。
說明2：C語言二維數(shù)組定義時(shí)必須指定第二維的大小，當(dāng)函數(shù)形參為二維數(shù)組時(shí)也是如此，傳參和形參在第二維定義同樣大小才能正常傳值。
此外，C語言二維數(shù)組不能像一維數(shù)組那樣返回，較易出錯(cuò)，遇到需要返回盡量避免使用二維數(shù)組。

第二步選擇權(quán)值最小兩棵樹SelectNode()的實(shí)現(xiàn)：

int SelectNode(HFTree HF,int len,int &s1,int &s2){
    int j;
    //把遇到第一個(gè)樹(parent==0)序號設(shè)為s1 
    for(j=0;j<len;j++){
        if(HF.v[j].parent==0){
            s1=j;break;
        }
    }
    //把遇到第二個(gè)樹序號設(shè)為s2
    for(j=j+1;j<len;j++){
        if(HF.v[j].parent==0){
            s2=j;break;//易錯(cuò) 
        }
    }
    //比較s1和s2，把s1置為權(quán)重較小那個(gè) 
    int swap;
    if(HF.v[s1].weight>HF.v[s2].weight){
        swap=s1;
        s1=s2;
        s2=swap;
    } 
    //繼續(xù)遍歷樹，如果權(quán)重小于s1，將s1置于該樹，s2置于s1；
    //如果權(quán)重大于s1小于s2，將s2置于該樹；如果大于s2則繼續(xù)遍歷
    for(j=j+1;j<len;j++){
        if(HF.v[j].parent==0){
            if(HF.v[j].weight<HF.v[s1].weight){
                s2=s1;s1=j;
            }else if(HF.v[j].weight>HF.v[s1].weight&&HF.v[j].weight<HF.v[s2].weight){
                s2=j;
        }
        }
    }
    return 0;
}

哈夫曼樹構(gòu)建好后，哈夫曼編碼同9.12輸出各葉子結(jié)點(diǎn)路徑，但實(shí)現(xiàn)過程中發(fā)現(xiàn)教科書上哈夫曼樹并不是嚴(yán)格按左子樹比右子樹小，或左子樹比右子樹大來的，而我的算法是嚴(yán)格限定的，所以不知道這里有什么問題，對哈夫曼樹的定義也產(chǎn)生疑問。
哈夫曼樹其實(shí)就是實(shí)現(xiàn)下面這張表：

哈夫曼譯碼就是依次讀入文件的二進(jìn)制碼，從根結(jié)點(diǎn)觸發(fā)，若遇0走向左子樹，遇1走向右子樹，若達(dá)到葉子節(jié)點(diǎn)則輸出葉子字符，再從根結(jié)點(diǎn)開始讀入二進(jìn)制碼。

9.16線索化二叉樹

含n個(gè)結(jié)點(diǎn)的二叉鏈表共有2n個(gè)鏈域，其中非空鏈域?yàn)閚-1個(gè)，空鏈域n+1，因此，提出了一種方法，利用原來的空鏈域存放指針（線索），指向樹中其他結(jié)點(diǎn)，這樣二叉樹不用遞歸就可以完成前序、中序、后續(xù)遍歷，快速找到某結(jié)點(diǎn)的前驅(qū)和后繼，方便插入、刪除操作，而且不采用[堆棧]處理，速度較一般二叉樹的遍歷速度更快，且節(jié)約存儲空間。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

九、數(shù)據(jù)結(jié)構(gòu)-非線-樹

九、數(shù)據(jù)結(jié)構(gòu)-非線-樹

9.1基本概念

9.2二叉樹性質(zhì)

9.3二叉樹的存儲

9.4先序生成二叉樹

9.5遍歷二叉樹

9.6計(jì)算葉子結(jié)點(diǎn)個(gè)數(shù)

9.7求二叉樹的深度

9.8求二叉樹的寬度

9.9復(fù)制二叉樹

9.10判斷二叉樹是否相等

9.11交換二叉樹每個(gè)結(jié)點(diǎn)的左右孩子

9.12輸出二叉樹中從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑

9.13求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值

9.14二叉樹和樹的相互轉(zhuǎn)換

9.14.1樹轉(zhuǎn)換為二叉樹

9.14.2二叉樹轉(zhuǎn)換為樹

9.14.3森林轉(zhuǎn)換為二叉樹

9.15哈夫曼樹

9.16線索化二叉樹

9.17二叉樹求解表達(dá)式的值（略）

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

九、數(shù)據(jù)結(jié)構(gòu)-非線-樹

9.1基本概念

9.2二叉樹性質(zhì)

9.3二叉樹的存儲

9.4先序生成二叉樹

9.5遍歷二叉樹

9.6計(jì)算葉子結(jié)點(diǎn)個(gè)數(shù)

9.7求二叉樹的深度

9.8求二叉樹的寬度

9.9復(fù)制二叉樹

9.10判斷二叉樹是否相等

9.11交換二叉樹每個(gè)結(jié)點(diǎn)的左右孩子

9.12輸出二叉樹中從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑

9.13求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值

9.14二叉樹和樹的相互轉(zhuǎn)換

9.14.1樹轉(zhuǎn)換為二叉樹

9.14.2二叉樹轉(zhuǎn)換為樹

9.14.3森林轉(zhuǎn)換為二叉樹

9.15哈夫曼樹

9.16線索化二叉樹

9.17二叉樹求解表達(dá)式的值（略）

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

九、數(shù)據(jù)結(jié)構(gòu)-非線-樹

9.13求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值