| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
免费IT实战开发视频教程合集分享千里之行 始于足下
共有 569 人关注过本帖
标题:打印树,求大神指点
只看楼主 加入收藏
lisen10
Rank: 1
来 自:广东
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-5-6
结帖率:100%
  已结贴   问题点数:20  回复次数:5   
打印树,求大神指点
就是把二叉树,按树形结构打印出来,我想了一整天了,还是实现不了,思绪好乱。。。。。代码就不贴了
求大神搭救🙏
2017-11-04 16:20
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:20 
https://bbs.bccn.net/thread-482093-1-1.html

这个给小白参考的~可以看看~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-11-05 10:15
lisen10
Rank: 1
来 自:广东
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-5-6
  得分:0 
回复 2楼 九转星河
没我想要的实现

前方是未知的,下一步需要找准方向与个性的配合。
2017-11-05 17:49
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:0 
回复 3楼 lisen10
https://bbs.bccn.net/viewthread.php?tid=481617&highlight=%2Bxzlxzlxzl

啊,不好意思没弄清楚题意~
应该是这个才对~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-11-06 13:54
lisen10
Rank: 1
来 自:广东
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-5-6
  得分:0 
让我消化一下先,在下先万分感激你啦

前方是未知的,下一步需要找准方向与个性的配合。
2017-11-07 21:45
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:0 
还有这个是我们老师提供的,不用感谢我,要就感谢我的老师~

程序代码:


//二叉树的创建及其遍历程序:字符型结点数据

/*   二叉树的建立与遍历  */
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define    MAX_NODE    50
# define    MaxLine        100

typedef char Etype;
typedef struct BiTNode{  /* 树结点结构 */
    Etype data;
    struct BiTNode *lch,*rch;
}BiTNode;

/********************************************************/
/*                    函数原形声明                      */
/********************************************************/


//二叉树的创建函数
BiTNode *creat_bt0();            //创建一颗固定的二叉树(实验用,避免多次输入)
BiTNode *creat_bt1();            //按完全二叉树编号创建
BiTNode *creat_bt2();            //按先序遍历创建
BiTNode *creat_NewNode(Etype e);//创建二叉树的一个结点

//二叉树的模拟输出
void LevelDSP(BiTNode *p);                 //层次遍历法显示二叉树
void visitPNode(BiTNode *p, int level);  //设置结点所在层的字符串(输出用)

//遍历二叉树函数原型申明
void DLR(BiTNode *p);        //先序遍历
void LDR(BiTNode *p);        //中序遍历
void LRD(BiTNode *p);        //后序遍历
void Level(BiTNode *p);     //层次遍历

//结点统计函数原型申明
void NodeNumDLR(BiTNode *p);        //前序统计结点数
void NodeNumLDR(BiTNode *p);        //中序统计结点数
void NodeNumLRD(BiTNode *p);        //后序统计结点数
void NodeNumLevel(BiTNode *p);      //层次遍历

//计算二叉树的深度
int  CNTdepth( BiTNode  *p);        //计算二叉树的深度

//二叉树的结点访问:输出结点、统计结点
void visitC(Etype dataC);
void visitCT(BiTNode *p);  //输出结点,统计结点类型n0,n1,n2

//定义全程变量,各种结点数
int n=0,n0=0,n1=0,n2=0;            //统计结点用
char Line1[MaxLine],Line2[MaxLine],Line3[MaxLine]; //二叉树模拟输出用
BiTNode *t;


/********************************************************/
/*                    主函数main                        */
/********************************************************/
main(){

    char ch; int k;

    do {
        printf("\n");
        printf("\n     0. 结束程序运行\n");

        printf("\n     1. 建立二叉树方法1(性质5:完全二叉树编号) ");
        printf("\n     2. 建立二叉树方法2(先序递归)\n");

        printf("\n     3. 先序DLR递归遍历二叉树");
        printf("\n     4. 中序LDR递归遍历二叉树");
        printf("\n     5. 后序LRD递归遍历二叉树");
        printf("\n     6. 层次Level遍历二叉树\n");

        printf("\n     7. 先序递归统计树中N0、N1、N2结点个数");
        printf("\n     8. 中序递归统计树中N0、N1、N2结点个数");
        printf("\n     9. 后序递归统计树中N0、N1、N2结点个数");
        printf("\n     10. 后序递归统计树中N0、N1、N2结点个数\n");

        printf("\n     11. 计算二叉树的深度\n");

        printf("\n     12. 创建固定二叉树");
        printf("\n     13. 输出二叉树\n");
        
        printf("\n==================================================");
        printf("\n     请输入您的选择 (0,1,2,3,4,5,6,7,8,9,10,11,12,13)");  
        
        scanf("%d",&k);
      
        switch(k){
        
            case 1:t=creat_bt1( );break; /*  调用性质5建立二叉树算法 */
            case 2:t=creat_bt2( );break; /*  调用递归建立二叉树算法   */
            case 3: {
                        printf("\n%2d 先序遍历结果是:",k);
                        DLR(t);                /*  调用先序遍历     */
                        }   break;
            case 4: {
                        printf("\n%2d 中序遍历结果是:",k);
                        LDR(t);                /*  调用中序遍历     */
                        }   break;
            case 5: {
                        printf("\n%2d 后序遍历结果是:",k);
                        LRD(t);                /*  调用后序遍历     */
                        }   break;
            case 6: {
                        printf("\n%2d 层次遍历结果是:",k);
                        Level(t);                /*  调用后序遍历     */
                        }   break;
            case 7:  {
                        n=0;n0=0 ; n1=0; n2=0;  /* 全局变量置0 */
                        printf("\n   %d:先序结果:",k);
                        NodeNumDLR(t);
                        printf("\n   二叉树结点数 n=%d, n0=%d, n1=%d, n2=%d",n,n0,n1,n2);     
                    } break;
            case 8:  {
                        printf("\n   %d:中序结果:",k);
                        n=0;n0=0 ; n1=0; n2=0;  /* 全局变量置0 */
                        NodeNumLDR(t);
                        printf("\n   二叉树结点数 n=%d, n0=%d, n1=%d, n2=%d",n,n0,n1,n2);     
                    } break;
            case 9:  {
                        printf("\n   %d:后序结果:",k);
                        n=0;n0=0 ; n1=0; n2=0;  /* 全局变量置0 */
                        NodeNumLRD(t);
                        printf("\n   二叉树结点数 n=%d, n0=%d, n1=%d, n2=%d",n,n0,n1,n2);     
                    } break;
            case 10:  {
                        printf("\n   %d:层次结果:",k);
                        n=0;n0=0 ; n1=0; n2=0;  /* 全局变量置0 */
                        NodeNumLevel(t);
                        printf("\n   二叉树结点数 n=%d, n0=%d, n1=%d, n2=%d",n,n0,n1,n2);     
                    } break;
            case 11:  {
                        printf( "\n   二叉树的深度(层数)是:%d",CNTdepth(t) );     
                    } break;
            case 12:    t=creat_bt0( );break; //建立固定二叉树
            case 13:    LevelDSP(t); break; //输出二叉树

            case 0: exit(0);
        } /*  switch  */
    }while(k>=0 && k<=13);

    printf("\n               再见!");
    printf("\n      打回车键,返回。"); ch=getchar();

} /* main */  



/********************************************************/
/*                 二叉树的创建相关函数                 */
/********************************************************/


// 创建一个固定结构的二叉树,用于实验,避免多次输入
BiTNode *creat_bt0(){
    BiTNode *t,*p,*q;

    t=(BiTNode *)malloc(sizeof(BiTNode));
    t->data='A';                   //根结点              A   
        p=creat_NewNode('B');//                         / \   
        t->lch=p;  // 左孩子                           B   C   
            q=creat_NewNode('D');//                   / \  /   
            p->lch=q;  // 左孩子                     D  E  F   
                                          
//            \   
            q=creat_NewNode('E');   //                    G  
            p->rch=q;  /* 左孩子  */
                p=creat_NewNode('G');
                q->rch=p;  /* 左孩子  */

        p=creat_NewNode('C');
        t->rch=p;  /* 右孩子  */
            q=creat_NewNode('F');
            p->lch=q;  /* 左孩子  */

    //LevelDSP(t); //输出二叉树

    return(t);
 
} // creat_bt0



// 利用二叉树性质5(编号i),借助一维数组V 建立二叉树
BiTNode *creat_bt1(){
    BiTNode *t,*p,*v[20]; int i,j; Etype e;

    /* 输入结点的序号i 、结点的数据e  */
    printf("\n结点数据(格式0?结束)i,char=?"); scanf("%d%c",&i,&e);
   
    while(i!=0 && (e!='?' || e!='/')){              /* 当 i ,e都为0时,结束循环  */
         p=(BiTNode *)malloc(sizeof(BiTNode));
         p->data=e; p->lch=NULL; p->rch=NULL;
         v[i]=p;
         if (i==1) t=p;                      /* 序号为1的结点是根 */
         else{
             j=i/2;
             if(i%2==0) v[j]->lch=p; /* 序号为偶数,做左孩子*/
             else       v[j]->rch=p;  /* 序号为奇数,做右孩子*/
         }
         printf("\n结点数据(格式0?结束)i,char=?"); scanf("%d%c",&i,&e);
    }
   
    return(t);
 
} // creat_bt1




// 模仿先序递归遍历方法,建立二叉树
BiTNode *creat_bt2(){
    BiTNode *t; Etype e;

    scanf("%c",&e);    //过滤前面菜单选择留下的回车键
    printf("\n如连续输入以空格间隔,/结束分支 char=");     scanf("%c",&e);
   
    if(e=='/' || e=='?') t=NULL;                  /* 对于0值,不分配新结点 */
    else {
        t=(BiTNode *)malloc(sizeof(BiTNode));
        t->data=e;
        t->lch=creat_bt2();  /* 左孩子获得新指针值  */
        t->rch=creat_bt2();  /* 右孩子获得新指针值  */
    }
   
    return(t);
 
} // creat_bt2




// 创建一个新结点,用于建立二叉树,供creat_bt0()调用
BiTNode *creat_NewNode(Etype e){
    BiTNode *t;
   
    if(e=='/' || e=='?') t=NULL;                  /* 对于0值,不分配新结点 */
    else {
        t=(BiTNode *)malloc(sizeof(BiTNode));
        t->data=e;
        t->lch=NULL;  /* 左孩子为空指针值  */
        t->rch=NULL;  /* 右孩子为空指针值  */
    }
   
    return(t);
 
} // creat_NewNode




/********************************************************/
/*                 二叉树的遍历相关函数                 */
/********************************************************/

// 先序递归遍历二叉树  
void DLR(BiTNode *p){

    if (p) {  
        visitC(p->data);    //访问根节点
        DLR(p->lch);    //先序遍历左子树
        DLR(p->rch);    //先序遍历右子树
    }

} //DLR



// 中序递归遍历二叉树  
void LDR(BiTNode *p){

    if (p) {  
        LDR(p->lch);    //中序遍历左子树
        visitC(p->data);    //访问根节点
        LDR(p->rch);    //中序遍历右子树
    }

} //LDR



// 后序递归遍历二叉树  
void LRD(BiTNode *p){

    if (p) {  
        LRD(p->lch);    //后序遍历左子树
        LRD(p->rch);    //后序遍历右子树
        visitC(p->data);    //访问根节点
    }

} //LRD



//层次遍历二叉树
void Level(BiTNode *p){      //层次遍历

    BiTNode  *Queue[MAX_NODE];
    int  front=0 , rear=0 ;
    if  (p!=NULL){
        Queue[++rear]=p;    /*   根结点入队  */
        while (front<rear) { //队列不为空执行循环
            p=Queue[++front];  visitC( p->data );
            if (p->lch != NULL)
                Queue[++rear]=p->lch;    /*   左结点入队  */
            if (p->rch != NULL)
                Queue[++rear]=p->rch;    /*   右结点入队  */
        }
    }

}   //Level



/********************************************************/
/*                 二叉树的节点统计相关函数             */
/********************************************************/

/* 利用前序递归遍历二叉树的方法,计算树中结点个数 */
void NodeNumDLR(BiTNode *p){

    if (p) {
   
        visitCT( p );   //在visit的基础上,增加了统计n,n1,n2功能
        NodeNumDLR(p->lch); //前序统计左子树的根结点属于n0,n1,n2
        NodeNumDLR(p->rch); //前序统计右子树的根结点属于n0,n1,n2
    }
 } /* NodeNumDLR  */



/* 利用中序递归遍历二叉树的方法,计算树中结点个数 */
void NodeNumLDR(BiTNode *p){

    if (p) {
   
        NodeNumLDR(p->lch); //中序统计左子树的根结点属于n0,n1,n2
              
        visitCT( p );   //在visit的基础上,增加了统计n,n1,n2功能
        
        NodeNumLDR(p->rch); //中序统计右子树的根结点属于n0,n1,n2
    }
 } /* NodeNumLDR  */




/* 利用后序递归遍历二叉树的方法,计算树中结点个数 */
void NodeNumLRD(BiTNode *p){

    if (p) {
   
        NodeNumLRD(p->lch); //后序统计左子树的根结点属于n0,n1,n2
        
        NodeNumLRD(p->rch); //后序统计右子树的根结点属于n0,n1,n2

        visitCT( p );   //在visit的基础上,增加了统计n,n1,n2功能

    }
 } /* NodeNumLRD  */



//利用层次遍历二叉树的方法,计算树中结点个数
void NodeNumLevel(BiTNode *p){      //层次遍历

    BiTNode  *Queue[MAX_NODE];
    int  front=0 , rear=0 ;

    if  (p!=NULL){
        Queue[++rear]=p;    /*   根结点入队  */
        while (front<rear) { //队列不为空执行循环
            p=Queue[++front];  

            visitCT( p );
            
            if (p->lch != NULL)
                Queue[++rear]=p->lch;    /*   左结点入队  */
            if (p->rch != NULL)
                Queue[++rear]=p->rch;    /*   右结点入队  */
        }
    }

}   /* 层次遍历二叉树算法,统计结果 */




/********************************************************/
/*                 计算二叉树的深度函数                 */
/********************************************************/
//求二叉树的深度(利用层次遍历算法)
int  CNTdepth( BiTNode  *p){

    BiTNode  *Queue[MAX_NODE+1];
    int  front=0 , rear=0, depth=0, level ;

    /*  level总是指向访问层的最后一个结点在队列的位置  */
    if  (p==NULL)  return(0);
    Queue[++rear]=p;    /*   根结点入队,rear=1  */
    level=rear ;    /*  根是第1层的最后一个节点  */
    while (front<rear){ //队列不为空
        p=Queue[++front]; //出队
        if (p->lch!=NULL)
            Queue[++rear]=p->lch;  /* 左结点入队  */
        if (p->rch!=NULL)
            Queue[++rear]=p->rch;  /* 右结点入队  */
        if (front==level){            /*  正访问的是当前层的最后一个结点  */
            depth++ ;  level=rear ;  
        }//累计树的深度
    }

    return(depth);

}


/********************************************************/
/*             二叉树的结点访问相关函数                 */
/********************************************************/

//输出结点
void visitC(Etype dataC){

    printf("%c ",dataC);

}


//输出结点并统计结点数
void visitCT(BiTNode *p){  //输出结点,统计结点类型n0,n1,n2

    visitC( p->data );

    //增加了三类结点统计
    n++;
    if(p->lch==NULL && p->rch==NULL) n0++;        //叶子结点
    if((p->lch==NULL && p->rch!=NULL) || (p->lch!=NULL && p->rch==NULL)) n1++;    //度为1是结点
    if(p->lch!=NULL && p->rch!=NULL) n2++;        //度为2的结点

}


/*********************************************************/
/*             层次遍历法显示二叉树                      */
/*********************************************************/

void LevelDSP(BiTNode *p){     //层次遍历法显示二叉树

    BiTNode  *Queue[MAX_NODE+1];
    int  front=0 , rear=0, depth=0, level ;
    /*  level总是指向访问层的最后一个结点在队列的位置  */
   
    if  (p==NULL) { printf("该树为空树\n"); return; }

    Queue[++rear]=p;    /*   根结点入队,rear=1  */
    level=rear ;    /*  根是第1层的最后一个节点  */

    //为第一层初始化(根结点)
//    strcpy(Line1,"A23456789012345678  ");    //结点行
    strcpy(Line1,"                    ");    //结点行
//    strcpy(Line2,"B234567890123456  ");        //左右分支线行
    strcpy(Line2,"                  ");        //左右分支线行
    strcpy(Line3,"");                        //用于初始化Line1无左或右结点的下一结点行

    while (front<rear){ //队列不为空
        p=Queue[++front]; //出队
        visitPNode( p ,depth);

        if (p->lch!=NULL)
            Queue[++rear]=p->lch;  /* 左结点入队  */
        if (p->rch!=NULL)
            Queue[++rear]=p->rch;  /* 右结点入队  */

        if (front==level){            /*  正访问的是当前层的最后一个结点  */
            printf("%s\n",Line1);        //print Node
            printf("%s\n",Line2);        //print Line

            depth++ ;  level=rear ;
            switch(depth){  //为下一层初始化字符串,最多允许4层树
                case 0:{    //本情况其实无效,在前面已经初始化
//                    strcpy(Line1,"123456789012345678  ");
                    strcpy(Line1,"                    ");
//                    strcpy(Line2,"1234567890123456  ");
                    strcpy(Line2,"                  ");
                }break;
                case 1:{    //第2行
//                    strcpy(Line1,"12345678901234  ");
                    strcpy(Line1,"                ");
//                    strcpy(Line2,"123456789012  ");
                    strcpy(Line2,"              ");
                }break;
                case 2:{    //第3行
//                    strcpy(Line1,"12345678901  ");
                    strcpy(Line1,"             ");
//                    strcpy(Line2,"1234567890  ");
                    strcpy(Line2,"            ");
                }break;
                case 3:{    //第4行
//                    strcpy(Line1,"123456789  ");
                    strcpy(Line1,"           ");
//                    strcpy(Line2,"12345678  ");
                    strcpy(Line2,"          ");
                }break;
            }//end switch
            strcat(Line1,Line3);
            strcpy(Line3,"");
        }//累计树的深度
        else{
            //用于初始化Line1无左或右结点的下一结点行
//            if(! p->lch )    strcat(Line3,"+  ");
//            if(! p->rch )    strcat(Line3,"-   ");
            if(! p->lch )    strcat(Line3,"   ");
            if(! p->rch )    strcat(Line3,"    ");
        }
    }

}    //LevelDSP

//123456789012345678901234567  _A_   
//1234567890123456789012345  _/_+_\_  
//12345678901234567890123  _B_+++++_C_
//1234567890123456789012  /__\++++++/_\
//12345678901234567890  _D_++_E_++_F_+_G_   
//1234567890123456789  _/_\++/_\__/_\++/_\_
//123456789012345678  _H_++I_J__K_L__M_N_+_O_
//

//Line1="12345678901234567890",20个空格初始化
//Line2="12345678901234567890",20个空格初始化



//初始化一个结点的显示格式,被LevelDSP调用
void visitPNode(BiTNode *p,int level){  //设置结点所在层的字符串
   
//参数Level=depth=实际层次-1

    char Tmp[2];
    //    visitC( p->data );

    Tmp[0]=p->data;Tmp[1]='\0';        //将字符型的结点值转化成字符串型
    strcat(Line1,Tmp);   

    switch(level){
    case 0: { //第一层

                if(p->lch)    strcat(Line2,"/   ");    //存在左子树,输出/
                else        strcat(Line2,"    ");   //无左子树,输出空格

                if(p->rch)    strcat(Line2,"\\");        //存在右子树,输出\  
                else        strcat(Line2," ");        //无右子树,输出空格
            }break;
    case 1: {  //第二层
                strcat(Line1,"       ");

                if(p->lch)    strcat(Line2,"/  ");    //存在左子树,输出/
                else        strcat(Line2,"   ");   //无左子树,输出空格

                if(p->rch)    strcat(Line2,"\\      ");        //存在右子树,输出\  
                else        strcat(Line2,"       ");        //无右子树,输出空格
            }break;
    case 2: {  //第三层
                strcat(Line1,"    ");

                if(p->lch)    strcat(Line2,"/ ");    //存在左子树,输出/
                else        strcat(Line2,"  ");   //无左子树,输出空格

                if(p->rch)    strcat(Line2,"\\  ");        //存在右子树,输出\  
                else        strcat(Line2,"   ");        //无右子树,输出空格
            }break;
    case 3: {  //第四层
                strcat(Line1,"   ");

                //第四层之后暂时不做处理
                /*
                if(p->lch)    strcat(Line2,"/0");    //存在左子树,输出/
                else        strcat(Line2,"=0");   //无左子树,输出空格

                if(p->rch)    strcat(Line2,"\\00");        //存在右子树,输出\  
                else        strcat(Line2,"=00");        //无右子树,输出空格
               
*/
            }break;
    }

}


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-11-07 23:23







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.061041 second(s), 9 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved