注册 登录
编程论坛 → 数据结构与算法

二叉树的创建和打印、。。。

营养书 发布于 2011-04-17 20:19， 1032 次点击
创建二叉树，要求是递归算法，输入形式为类似A(B(#,D),C(E,#))，#表示空子树。
打印：按树状打印
下面是我的算法，貌似创建部分有误，不能输出正确结果，求助、、、
#include <stdio.h>
#include <stdlib.h>

typedef struct BitNode
{
 char data;
 int  level;
 struct BitNode *lchild,*rchild;
}BitNode,*BiTree;

int CreateBiTree_GList( BiTree &T)//由广义表形式的输入建立二叉链表
{ char c;
 
  c=getchar();
  if(c=='#') T=NULL; //空子树
  else
  {
    T=(BitNode*)malloc(sizeof(BitNode));
    T->data=c;
    if(getchar()!='(') return 1;
    if(!CreateBiTree_GList(T->lchild)) return 1;
   
    if(getchar()!=',') return 1;
    if(!CreateBiTree_GList(T->rchild)) return 1;
   
    if(getchar()!=')') return 1; //这些语句是为了保证输入符合A(B,C)的格式
  }
  return 0;
}//CreateBiTree_GList

void Inorder(BiTree bt)
{
 int i;
 if(bt!=NULL)//按右根左遍历二叉树
 {
  Inorder(bt->rchild);
  printf("\t_________________\n\t");
  for(i=1;i<=4;i++)
      printf("| %c ",(i==bt->level)?bt->data:' ');
  printf("|\n");
  
  Inorder(bt->lchild);
 }
 
}

int main()
{
 
 int t;
 BiTree b;
 //建立二叉树
 b=(BiTree)malloc(sizeof(BitNode));
 t=CreateBiTree_GList(b);
 
 Inorder(b);//按右根左遍历二叉树
 printf("\t_________________\n\t");
 printf("\n");

 return 0;
}
   
12 回复
#2
寒风中的细雨2011-04-18 09:16
程序代码：
#include <stdio.h>
#include <malloc.h>

typedef struct BitNode
{
    struct BitNode *lchild, *rchild;
    int level;
    char data;
}BitNode, *BiTree;

char s[100];
char *c = s;

void get_str()
{
    int i=0;

    while( (s[i++] = getchar()) != '\n' );
}

int CreateBiTree_GList(BiTree &T)
{   
    if (*c=='#')
    {
        ++c;
        T = NULL;
    }
    else
    {
        T = (BitNode*) malloc (sizeof(BitNode));
        T->data = *c;
        T->lchild = T->rchild = NULL;
      
        c++;//补充一个符号
        if (*c =='(')
        {
            c++;
            if (CreateBiTree_GList(T->lchild))
            {
                printf("\t输入有错误\n");
            }
        }
        if (*c == ',')
        {
            c++;
            if (CreateBiTree_GList(T->rchild))
            {
                printf("\t输入有错误\n");
            }
        }
        if (*c == ')')
        {
            c++;
        }
    }

    return 0;
}

void Inorder(BiTree bt)
{
    if (NULL != bt)
    {
        Inorder(bt->lchild);
        printf("%c ",bt->data);
        Inorder(bt->rchild);
    }
}
/*
void Inorder(BiTree bt)
{
    int i;
   
    if (NULL != bt)
    {
        Inorder(bt->rchild);
        printf("\t_________________\n\t");

        for (i=1; i<=4; ++i)
        {
            printf("| %c ", (i==bt->level)? bt->data: ' ' );
        }
        printf("|\n");
      
        Inorder(bt->lchild);
    }
}
*/
int main(void)
{
    int t;
    BiTree b;
    //建立二叉树
    b=(BiTree)malloc(sizeof(BitNode));
    get_str();
    t=CreateBiTree_GList(b);

    Inorder(b);//按右根左遍历二叉树
    printf("\t_________________\n\t");
    printf("\n");


    return 0;
}
#3
寒风中的细雨2011-04-18 09:17
只有本站会员才能查看附件，请 登录

输出的没有看  自己不会再来吧
#4
寒风中的细雨2011-04-18 09:31
回复 楼主 营养书
忘记说啦  
程序中有个很严重的错误  level的使用

printf("| %c ", (i==bt->level)? bt->data: ' ' );

在建立的时候并没有对其成员level赋值  所以level是不能使用的
#5
营养书2011-04-18 18:40
多谢指教。我再仔细研究一下。
#6
维海2011-04-20 22:45
以下是引用寒风中的细雨在2011-4-18 09:16:16的发言：

#include <stdio.h>
#include <malloc.h>

typedef struct BitNode
{
    struct BitNode *lchild, *rchild;
    int level;
    char data;
}BitNode, *BiTree;

char s[100];
char *c = s;

void get_str()
{
    int i=0;

    while( (s = getchar()) != '\n' );
}

int CreateBiTree_GList(BiTree &T)
{   
    if (*c=='#')
    {
        ++c;
        T = NULL;
    }
    else
    {
        T = (BitNode*) malloc (sizeof(BitNode));
        T->data = *c;
        T->lchild = T->rchild = NULL;
      
        c++;//补充一个符号
        if (*c =='(')
        {
            c++;
            if (CreateBiTree_GList(T->lchild))
            {
                printf("\t输入有错误\n");
            }
        }
        if (*c == ',')
        {
            c++;
            if (CreateBiTree_GList(T->rchild))
            {
                printf("\t输入有错误\n");
            }
        }
        if (*c == ')')
        {
            c++;
        }
    }

    return 0;
}

void Inorder(BiTree bt)
{
    if (NULL != bt)
    {
        Inorder(bt->lchild);
        printf("%c ",bt->data);
        Inorder(bt->rchild);
    }
}
/*
void Inorder(BiTree bt)
{
    int i;
   
    if (NULL != bt)
    {
        Inorder(bt->rchild);
        printf("\t_________________\n\t");

        for (i=1; i<=4; ++i)
        {
            printf("| %c ", (i==bt->level)? bt->data: ' ' );
        }
        printf("|\n");
      
        Inorder(bt->lchild);
    }
}
*/
int main(void)
{
    int t;
    BiTree b;
    //建立二叉树
    b=(BiTree)malloc(sizeof(BitNode));
    get_str();
    t=CreateBiTree_GList(b);

    Inorder(b);//按右根左遍历二叉树
    printf("\t_________________\n\t");
    printf("\n");


    return 0;
}

此贴为本人应用他人，主要是留给自己以后看的
#7
维海2011-04-20 22:45
以下是引用寒风中的细雨在2011-4-18 09:16:16的发言：

#include <stdio.h>
#include <malloc.h>

typedef struct BitNode
{
    struct BitNode *lchild, *rchild;
    int level;
    char data;
}BitNode, *BiTree;

char s[100];
char *c = s;

void get_str()
{
    int i=0;

    while( (s = getchar()) != '\n' );
}

int CreateBiTree_GList(BiTree &T)
{   
    if (*c=='#')
    {
        ++c;
        T = NULL;
    }
    else
    {
        T = (BitNode*) malloc (sizeof(BitNode));
        T->data = *c;
        T->lchild = T->rchild = NULL;
      
        c++;//补充一个符号
        if (*c =='(')
        {
            c++;
            if (CreateBiTree_GList(T->lchild))
            {
                printf("\t输入有错误\n");
            }
        }
        if (*c == ',')
        {
            c++;
            if (CreateBiTree_GList(T->rchild))
            {
                printf("\t输入有错误\n");
            }
        }
        if (*c == ')')
        {
            c++;
        }
    }

    return 0;
}

void Inorder(BiTree bt)
{
    if (NULL != bt)
    {
        Inorder(bt->lchild);
        printf("%c ",bt->data);
        Inorder(bt->rchild);
    }
}
/*
void Inorder(BiTree bt)
{
    int i;
   
    if (NULL != bt)
    {
        Inorder(bt->rchild);
        printf("\t_________________\n\t");

        for (i=1; i<=4; ++i)
        {
            printf("| %c ", (i==bt->level)? bt->data: ' ' );
        }
        printf("|\n");
      
        Inorder(bt->lchild);
    }
}
*/
int main(void)
{
    int t;
    BiTree b;
    //建立二叉树
    b=(BiTree)malloc(sizeof(BitNode));
    get_str();
    t=CreateBiTree_GList(b);

    Inorder(b);//按右根左遍历二叉树
    printf("\t_________________\n\t");
    printf("\n");


    return 0;
}

此贴为本人应用他人，主要是留给自己以后看的
#8
枫亭水榭2011-04-24 23:58
想问一个问题，可以按中序次序建立二叉树吗？
#9
寒风中的细雨2011-04-25 09:19
程序代码：
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *l_child;
    struct node *r_child;
}*BTree;

BTree create(BTree tree)
{
    int temp;
    scanf("%d", &temp);

    if (temp == 0)
    {
        tree = NULL;
    }
    else
    {
        tree = (BTree) malloc (sizeof(struct node));

        tree->l_child = create(tree->l_child);
        scanf("%d", &tree->data);
        tree->r_child = create(tree->r_child);
    }

    return tree;
}

void show(BTree tree)
{
    if (tree != NULL)
    {
        show(tree->l_child);
        printf("%d ", tree->data);
        show(tree->r_child);
    }
}

int main(void)
{
    BTree tree = NULL;

    tree = create(tree);

    show(tree);

    return 0;
}
只有本站会员才能查看附件，请 登录
#10
寒风中的细雨2011-04-25 09:21
上面是中序输入中序输出: 5 4 3 2 1

比较难看的
100 和 0 分别表示生成结点 和 不生成结点
 
#11
寒风中的细雨2011-04-25 09:23
程序代码：
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *l_child;
    struct node *r_child;
}*BTree;

BTree create(BTree tree)
{
    int temp;
    scanf("%d", &temp);

    if (temp == 0)
    {
        tree = NULL;
    }
    else
    {
        tree = (BTree) malloc (sizeof(struct node));

        tree->l_child = create(tree->l_child);
        tree->r_child = create(tree->r_child);
    }

    return tree;
}

BTree init(BTree tree)
{
    if ( tree != NULL )
    {
        tree->l_child = init(tree->l_child);
        scanf("%d", &tree->data);
        tree->r_child =    init(tree->r_child);
    }

    return tree;
}

void show(BTree tree)
{
    if (tree != NULL)
    {
        show(tree->l_child);
        printf("%d ", tree->data);
        show(tree->r_child);
    }
}

int main(void)
{
    BTree tree = NULL;

    tree = create(tree);
    printf("\n");

    tree = init(tree);

    show(tree);
    printf("\n");

    return 0;
}

只有本站会员才能查看附件，请 登录
#12
寒风中的细雨2011-04-25 09:25
上面是先生成需要的结点 然后在进行初始化工作 依然是按照中序的步骤进行
#13
寒风中的细雨2011-04-25 09:30
建树的目的只是把树的元素按照树的这种关系建立起来就可以 所以说应该是越简单越好 没有必要搞的那么复杂
1
©2025, BC-CN.NET
电脑版