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

再来一道,快疯了我!!

发布于 2010-06-03 20:46， 1049 次点击
根据中序遍历和层次遍历建立树,我用的是递归思路,可是.......哎总找不到那错了.
#include <stdio.h>
#include <malloc.h>
#define maxsize 100
typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *lchild,*rchild;
}BiNode,*BiTree;
typedef struct order
{
    ElemType data[maxsize];
    int nodes;
}order;
order Creat_order()
{
    order a;
    ElemType x;
    a.nodes=0;
    scanf("%c",&x);
    while(x!='#')
    {
        a.data[++a.nodes]=x;
        scanf("%c",&x);
    }
    return a;
}
BiTree CreatBiTree(order inorder,order leorder,int f1,int l1,int f2)
{
    int root;
    BiTree T;
    for(root=f1;inorder.data[root]!=leorder.data[f2];root++);
    T=(BiTree)malloc(sizeof(BiNode));
    T->data=inorder.data[root];
    if(f1==root)
    {
        T->lchild=NULL;
        if(l1==root) T->rchild=NULL;
        else T->rchild=CreatBiTree(inorder,leorder,root+1,l1,f2+1);
    }
    else
    {
        T->lchild=CreatBiTree(inorder,leorder,f1,root-1,f2+1);
        if(l1==root) T->rchild=NULL;
        else T->rchild=CreatBiTree(inorder,leorder,root+1,l1,f2+2);
    }
    return T;
}
int main()
{
    BiTree T;
    int f1,l1,f2;
    order inorder,leorder;
    printf("Input the inorder:");
    inorder=Creat_order();
    printf("Input the leorder:");
    leorder=Creat_order();
    f1=f2=1;
    l1=inorder.nodes;
    T=CreatBiTree(inorder,leorder,f1,l1,f2);
    return 0;
}
8 回复
#2
小依2010-06-14 11:42
我是新手，不好意思，只是问下.
return 返回数据，这个数据可以是结构吗（不用指针的情况下）？
#3
2010-06-15 13:31
可以的。
#4
小依2010-06-15 21:46
它一般不是只能返回单个数据么？
#5
佳嘉2010-06-15 22:35
能运行呀
#6
waterstar2010-06-21 11:05
楼主啊，编程的时候注意加注释，没注释的程序看这太费劲了
#7
aitajiujiage2010-06-28 13:59
大哥 你这个程序小弟实在是看的不太清楚,能否加一个注解啊?
不过我可以发一个经典的例子给你,不过这个程序,没有使用递归调用,这个程序的功能可强大了,希望对你有启发:
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
#include <conio.h>
typedef struct btnode
    {
    char cdata;
    struct btnode *lchild,*rchild;
    }BTNode;
    int count,deep;
    BTNode *Create_BiTree2()
    { BTNode  *t;          char c;
      c=getchar();
      if(c=='.')   return(NULL);
     else{
             t=(BTNode *)malloc(sizeof(BTNode));
             t->cdata=c;
             t->lchild=Create_BiTree2();
             t->rchild=Create_BiTree2();
    }
     return(t);
  }
void Preorder2(BTNode *bt)   
 {
    BTNode * p=bt,*s[MAXSIZE]; int top=-1;
    while(p||top>-1)
      {  if(p)                        
        { printf("%c",p->cdata);      
          ++top ;s[top]=p;        
          p=p->lchild ;   }        
        else                        
          {  p=s[top] ;--top ;   
             p=p->rchild ;     }   
          }
    }
void Inorder2(BTNode *bt)   
  {
    BTNode * p=bt,*s[MAXSIZE]; int top=-1;
    while(p||top>-1)
        {  if(p)                        
           { ++top ;s[top]=p;      
              p=p->lchild ;   }     
           else                        
             {  p=s[top] ;
                printf("%c",p->cdata);      
                --top ;     
               p=p->rchild ;     }   
           }
      }
int Postorder2(BTNode *T)   
{  BTNode *p,s[MAXSIZE];
     int s2[MAXSIZE],top=0,mark;
     p=T;
     do
     { while(p!=NULL)
        { s[top]=*p; s2[top++]=0;  p=p->lchild; }
         if(top>0)
           { mark=s2[--top];  *p=s[top];
             if(mark==0)         
             { s[top]=*p;s2[top++]=1;
                p=p->rchild;
              }
            else
             { printf("%c",p->cdata);   
               p=NULL;  }
          }
     }while(top>0);
    return 1;
}
void Node_Count(BTNode *T)
{
   if(T)
       {
         count++;  
         Node_Count(T->lchild);
         Node_Count(T->rchild);
       }
   }/* Node_Count*/
void Leaf_BiTree(BTNode *T,int j)   
{
  if(T)
   {
     if(T->lchild==NULL && T->rchild==NULL)
       { printf("%c\n",T->cdata);
         count++;
       }
      j++;
      if(deep<j)  deep=j;
      Leaf_BiTree(T->lchild,j);
      Leaf_BiTree(T->rchild,j);
   }
}
void  Exchange(BTNode *bt)
{
    if(bt)
    {   BTNode *p;
         p=bt->lchild;
         bt->lchild=bt->rchild;
         bt->rchild=p;
         Exchange(bt->lchild);
         Exchange(bt->rchild);
          }
}
 main()
  {
     int i=1;
     BTNode *t;
     textcolor(GREEN);
     textbackground(RED);
     clrscr();
  t=Create_BiTree2();
 while(1)
  {
    printf("\n");
    printf("请选择操作:\n");
    printf("1:  二叉树的前序遍历\n");
    printf("2:  二叉树的中序遍历\n");
    printf("3:  二叉树的后序遍历\n");
    printf("4:  求二叉树的结点数\n");
    printf("5:  求二叉树的叶子结点及树的深度\n");
    printf("6:  二叉树左右子树的交换\n");
    printf("7:  返回输入二叉树界面\n");
    printf("0:  退出程序\n");
    scanf("%d",&i);
    switch(i)
     {
      case 0: printf(" 程序退出！\n ");exit(0);
      case 1:clrscr(); printf("前序遍历结果:\n"); Preorder2(t);
      break;
      case 2:clrscr();  printf("中序遍历结果:\n"); Inorder2(t);
      break;
      case 3: clrscr(); printf("后序遍历结果:\n"); Postorder2(t);
           break;
      case 4: clrscr(); count=0;
                Node_Count(t);
                printf("二叉树结点的个数是%d",count,"\n");
               break;
      case 5: clrscr(); printf("叶子结点为:\n");
               deep=count=0;
               Leaf_BiTree(t,count);
               printf("树叶结点数为:%d",count);
               printf("\n树的深度为:%d",deep);
               break;
      case 6: clrscr(); Exchange(t);
         printf("左、右子树已交换成功!:");
         printf("\n前序遍历序列为:");Preorder2(t);
         printf("\n中序遍历序列为:");Inorder2(t);
         printf("\n后序遍历序列为:");Postorder2(t);
         break;
      case 7:return main();break;
      default : printf("\n输入无效，请重新选择操作!\n" );break;
   }
  }
}
#8
2010-06-28 16:56
回复 6楼 waterstar
是挺全的，呵呵。
#9
hao07162010-07-09 20:28
以下是引用小依在2010-6-14 11:42:23的发言：

我是新手，不好意思，只是问下.
return 返回数据，这个数据可以是结构吗（不用指针的情况下）？
不用指针是不可以的
当然如果你定义成struct {char a[4];};这样是可以的...
1
©2025, BC-CN.NET
电脑版