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

二叉树的遍历

liu200909 发布于 2009-12-26 16:03, 1817 次点击
请高手指点下:
    已知二叉树的前序遍历是:GFKDAIEBCHJ;后序遍历是:DIAEKFCJHBG  怎样写出中序遍历的顺序?
希望高手能给出一个解题方法、思路,本人不甚感激!!!!谢谢!
10 回复
#2
佳嘉2009-12-26 17:12
你自己看看吧
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
#define max 30      /*二叉树中做多的结点数*/
typedef struct btnode  /*定义二叉树的结点类型*/
{
    char data;  /*结点的数据为字符型数据*/
    struct btnode *lchild,*rchild; /*左右指针*/
}bttree;
bttree *cre_tree(char *str,int i,int m)  /*将字符串中的第i个字符到第m个字符作为数据生成对应的满二叉树*/
{
    bttree *p;
    if(i>=m)    /*无效结点*/
        return NULL;
    else
    {
    p=(bttree *)malloc(sizeof(bttree));
    p->data=str[i];
    p->lchild=cre_tree(str,2*i+1,m);   /*创建新结点的左子树*/
    p->rchild=cre_tree(str,2*i+2,m);   /*创建结点的右子树*/
    return p;
    }
}
void preorder(bttree *t)  /*先序遍历二叉树*/
{
    if(t!=NULL)
    {
        printf("%c",t->data);
        if(t->lchild)
        {
            printf("->");
            preorder(t->lchild);
        }
        if(t->rchild)
        {
            printf("->");
            preorder(t->rchild);
        }
    }
}
void inorder(bttree *t)  /*中序遍历二叉树*/
{
     if(t!=NULL)
     {
         inorder(t->lchild);
         printf("%c",t->data);
         printf("->");
         inorder(t->rchild);
     }
}
void postorder(bttree *t) /*后续遍历二叉树*/
{
    if(t!=NULL)
    {
        postorder(t->lchild);
        printf("%c",t->data);
        printf("->");
        inorder(t->rchild);
    }
}

   
void main()
{
    int i,n;
    char str[max];  
    bttree *root;  /* *root为指向根结点的指针*/
    printf("please input a bbtree node num:\n");
    scanf("%d",&n);
    getchar(); /*输入数字*/
    printf("please input a string which length is %d:",n);
    for(i=0;i<n;i++)  /*输入字符串*/
        str[i]=getchar();
    printf("\n");
    root=cre_tree(str,0,n);  /*生成二叉树*/
    printf("the tree is already created\n");

    printf("\n");
    printf("the result sfter preorder processing :");  /*先序遍历后输出结果*/
    preorder(root);
    printf("\n");
    printf("the result sfter inorder processing :"); /*中序遍历后输出结果*/
    inorder(root);
    printf("\n");
    printf("the result sfter postorder processing :");/*后续遍历后输出结果*/
    postorder(root);
    getch();
}
#3
wufei19891212009-12-26 19:08
自己在草纸上看能不能画出二叉树的图    用程序实现不知道
#4
liu2009092009-12-26 21:02
回复 3楼 wufei1989121
自己做过了,就是画不出该二叉树的左子树,右子树已经画出来了,而且我能保证百分之百正确!

因为我实在不知道怎么画,所以我就来找各位大侠来帮忙!!!
#5
liu2009092009-12-26 21:11
回复 2楼 佳嘉
不用程序实现呢????画图。。。。分析。。。。。。
谢谢!!!!!!
#6
faust2009-12-27 10:52
感谢2楼!!
#7
TIC2009-12-28 16:20
看下题目抄错没?
#8
TIC2009-12-28 16:21
类似于这样的题。
#9
TIC2009-12-28 16:22
先确定根节点,左右子树,结合给出的顺序,有规律,多多做下这样的题,就会很熟的。
#10
liu2009092009-12-28 20:35
回复 7楼 TIC
题目绝对没有错!我肯定!
还有就是,如果题目给的是:先序遍历、中序遍历,或者是后序遍历与中序遍历,
要求画出这样的二叉树等,这样的题目我会很熟练地做出来,
但是一涉及到先序遍历与后序遍历要求画出二叉树什么的,我就不会了,
其实这关键的问题在于我没有找到这个解题思路,正因为这样,所以我就希望各位
能帮忙解决下做题的思路,谢谢!!!
#11
itican2009-12-28 21:06
这道题你做不出来也是应该的。如果你知道二叉树的前序序列和后序序列,是不能唯一确定一刻二叉树的。像你这个问题,就无法确定,A,I,E的确切位置。你再仔细看看。
1