返回顶部

收藏

二叉树前序和中序序列构造该二叉树

更多

编一C程序,它能根据输入的二叉树前序和中序序列来构造该二叉树,并能输出该二叉树的后序序列和该二叉树叶的结点的个数以及该二叉树高度。(输入次序是:表示前序序列的字符串、表示中序序列的字符串)

#include<stdio.h>
#include<malloc.h>
#include<string.h>
void exit(int);
#define MAX 100
typedef struct node{
    char d;
    struct node *lchild,*rchild;
}Tnode;

void MK(char in[],char is,char ie,char pre[],char pres,char pree,Tnode **r)
{
    int i;
    if(is>ie||pres>pree)
        *r=NULL;
    else{
        *r=malloc(sizeof(Tnode));
        (*r)->d=pre[pres];
        for(i=is;i<=ie;i++){
            if(in[i]==pre[pres]){
            MK(in,is,i-1,pre,pres+1,pres+i-is,&(*r)->lchild);
            MK(in,i+1,ie,pre,pres+i-is+1,pree,&(*r)->rchild);
            break;
            }
            if(i>ie){
                printf("输入错误!\n");
                exit(1);
            }
        }
    }
}
void postorder(Tnode *r)
{
    if(r){
        postorder(r->lchild);
        postorder(r->rchild);
        printf("%c",r->d);
    }
}
int leaf(Tnode *r)
{
    if(r==NULL)
        return 0;
    else
        if(r->lchild==NULL&&r->rchild==NULL)
            return 1;
        else
            return leaf(r->lchild)+leaf(r->rchild);
}
int height(Tnode *r)
{
    int h1,h2;
    if(r==NULL)
        return 0;
    else{
        h1=height(r->lchild);
        h2=height(r->rchild);
        return 1+(h1>h2?h1:h2);
    }
}
void main()
{
    Tnode *r=NULL;
    char in[MAX],pre[MAX];
    printf("请输入前序序列:\n");
    gets(pre);
    printf("请输入中序序列:\n");
    gets(in);
    MK(in,0,strlen(in)-1,pre,0,strlen(pre)-1,&r);
    printf("\n后序遍历序列为:\n");
    postorder(r);
    printf("\n叶结点的个数为:%d\n",leaf(r));
    printf("\n高度为:%d\n",height(r));
}

标签:c++,二叉树

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. Qiang 发表 2012-06-06 11:26:53 程序如何找自己
  2. Scott Meyers 发表 2011-04-01 05:32:02 Appearing and Disappearing consts in C++
  3. Herb Sutter 发表 2012-04-30 21:59:18 World’s youngest C++ programmer?
  4. Herb Sutter 发表 2012-09-12 19:00:39 VC++ 2012 Desktop Express (Free)
  5. Herb Sutter 发表 2013-01-16 00:08:30 Java vulnerabilities
  6. Andy Rich 发表 2013-03-04 23:04:00 Connecting to Live with the C++ REST SDK
  7. bystander 发表 2013-04-11 10:50:25 模板栈以及中缀表达式求值(C++实现)
  8. 博主 发表 2009-10-18 16:00:00 配置 Vim 作为 C++ 开发环境初步
  9. Sana Mithani 发表 2013-06-04 18:11:00 C++ REST SDK 1.0.0 is now available
  10. admin 发表 2012-07-28 06:44:59 STL库的for each支持
  11. ideawu 发表 2013-08-09 16:28:15 WebRTC C/C++ API 示例代码 – 播放和录音
  12. coder4 发表 2013-09-23 06:00:08 C++中,解析UTF-8字符的位置。

发表评论