• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 100,  comments - 15,  trackbacks - 0
            輸入二叉樹先序,建樹,然后中序線索化,遍歷輸出
              1#include<iostream>
              2using namespace std;
              3
              4enum PointerTag
              5
              6    Link,Thread        //枚舉值Link和Thread分別為0,1
              7}

              8
              9struct BiThrNode    //線索二叉樹的結點類型
             10{
             11    char data;
             12    PointerTag LTag;    //左標志
             13    PointerTag RTag;    //右標志
             14    BiThrNode *lchild;    //左孩子指針
             15    BiThrNode *rchild;    //右孩子指針
             16}
            ;
             17
             18typedef BiThrNode* BiThrTree;
             19BiThrNode *pre=NULL; //全局量
             20
             21void InOrderThreading(BiThrTree & Thrt,BiThrTree T);//線索化
             22void InThreading(BiThrTree p);//中序遍歷線索化
             23bool PreOrderCreatBiTree(BiThrTree &T);//先序建立樹
             24void InOrderTraverse_Thr(BiThrTree T);//中序遍歷線索樹
             25
             26int main()
             27{
             28    BiThrTree T,Thrt;
             29    printf("輸入先序序列('#'表示空節點)建立二叉樹:\n");
             30    PreOrderCreatBiTree(T);//先序建立樹
             31    InOrderThreading(Thrt,T);//中序線索化
             32    printf("中序線索化,中序遍歷得中綴式:\n");
             33    InOrderTraverse_Thr(Thrt);//中序遍歷線索樹
             34    printf("\n");
             35    return 0;
             36}

             37
             38void InOrderThreading(BiThrTree & Thrt,BiThrTree T)
             39{
             40    Thrt=new BiThrNode;
             41    Thrt->LTag=Link;
             42    Thrt->RTag=Thread;
             43    Thrt->rchild=Thrt;
             44    if(!T) Thrt->lchild=Thrt;
             45    else{
             46        Thrt->lchild=T;
             47        pre=Thrt;
             48        InThreading(T);
             49        pre->rchild=Thrt;
             50        pre->RTag=Thread;
             51        Thrt->rchild=pre;
             52    }

             53}

             54
             55void InThreading(BiThrTree p)
             56{
             57    if(p)
             58    {
             59        InThreading(p->lchild);
             60        if(!p->lchild){ p->LTag=Thread; p->lchild=pre;}
             61        if(!pre->rchild){ pre->RTag=Thread; pre->rchild=p; }
             62        pre=p;
             63        InThreading(p->rchild);
             64    }

             65}

             66
             67bool PreOrderCreatBiTree(BiThrTree &T)
             68{//該節點非空返回true,雙親節點對應標志Link,空時返回false,雙親節點對應標志應為Thread
             69    char ch;
             70    scanf("%c",&ch);
             71    if(ch=='#')
             72    {
             73        T=NULL;
             74        return false;
             75    }
            else {
             76        T=new BiThrNode;
             77        T->data=ch;
             78        if(PreOrderCreatBiTree(T->lchild)) T->LTag=Link;    //左孩子存在則左標志為Link
             79        else T->LTag=Thread;
             80        if(PreOrderCreatBiTree(T->rchild)) T->RTag=Link;    //右孩子存在則右標志為Link
             81        else T->RTag=Thread;
             82    }

             83    return true;
             84}

             85
             86
             87void InOrderTraverse_Thr(BiThrTree T)
             88{
             89    BiThrNode *p;
             90    p=T->lchild;
             91    while(p!=T)
             92    {
             93        while(p->LTag==Link) p=p->lchild;
             94        printf("%c",p->data);
             95        while(p->RTag==Thread && p->rchild!=T) //if(p->RTag==Thread && p->rchild!=T)
             96        {
             97            p=p->rchild;
             98            printf("%c",p->data);
             99        }

            100        p=p->rchild;
            101    }

            102}
            posted on 2009-05-13 17:00 wyiu 閱讀(626) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構
            久久免费视频网站| 国产麻豆精品久久一二三| 欧美激情精品久久久久久久| 久久伊人五月天论坛| 无码国内精品久久人妻| 久久99免费视频| 久久婷婷国产剧情内射白浆| 99国产欧美久久久精品蜜芽 | 亚洲欧美国产日韩综合久久| 亚洲AV无码一区东京热久久 | 日韩精品久久久肉伦网站| 亚洲精品高清久久| 亚洲精品乱码久久久久久按摩| 99久久综合狠狠综合久久| 人人狠狠综合久久88成人| 久久有码中文字幕| 中文字幕亚洲综合久久2| 人妻无码αv中文字幕久久琪琪布| 欧美午夜精品久久久久久浪潮| 成人久久精品一区二区三区| 久久婷婷五月综合成人D啪| 久久精品成人影院| 久久夜色精品国产亚洲| 麻豆AV一区二区三区久久| 久久亚洲精品无码aⅴ大香| 久久精品无码一区二区三区日韩 | 九九久久精品国产| 精品国产福利久久久| 久久精品www人人爽人人| 无码精品久久久天天影视| 四虎国产精品成人免费久久| 久久最新免费视频| 中文字幕精品久久久久人妻| 一级做a爰片久久毛片免费陪| 欧美成a人片免费看久久| 免费一级欧美大片久久网| 亚州日韩精品专区久久久| 亚洲国产成人精品久久久国产成人一区二区三区综 | 亚洲人成无码久久电影网站| 伊人 久久 精品| 精品熟女少妇av免费久久|