ITKeyword,专注技术干货聚合推荐

注册 | 登录

问题 H: 数据结构(C语言版)算法6.1至算法6.4__二叉树遍历

hnust_xiehonghao 分享于 2012-08-22

推荐:数据结构(C语言版)摘录--树和二叉树

第六章 树和二叉树 树(Tree)是n(n>=0)个结点的有限集。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

问题 H: 数据结构(C语言版)算法6.1至算法6.4__二叉树遍历
时间限制: 1 Sec  内存限制: 128 MB
提交: 128  解决: 34
[提交][状态][讨论版]
题目描述

求二叉树的先序、中序及后序遍历序列。结点数<=100。
输入

按先序遍历的顺序建立一个二叉树,为了保证树的唯一性,并在程序中的递归出口是左右子树为空,故输入时,当某结点的左子树或右子树为空值时也要作为先序遍历的有效输入。例如一个树只有3个结点,根结点值为1,其左孩子结点值为2,其右孩子结点值为3,则输入的先序遍历序列依次为1 2 0 0  3 0 0(为空时输入0值)*/
输出

在三行上,依次输出二叉树的先序、中序及后序遍历序列。序列中各数用空格隔开。
样例输入

1 2 0 0 3 0 0

样例输出

1 2 3

2 1 3

2 3 1

提示
一开始狂RE  不知道是不是人品问题   下面是参考了老师给的代码 后 做过的  AC 了
主要 难住我的地方是一开始 不知道如何结束输入   后来知道了就 一组数据 但是仍然不知道如何结束这一组数据的输入
我直接gets 所有的再处理 也不行  用scanf  !=EOF  也是RE    RE代码见最后面
 
这个思路很简单  一直建立树接点   如过遇到0 则不建立相应的接点   直接递归建立即可 很简单

#include<stdio.h>
#include<malloc.h>
typedef struct haha
{
 int num;
 struct haha *left;
 struct haha *right;
}nd;
int a[1000],k;
nd* creat(nd *root)
{
 int x;
 scanf("%d",&x);
 if(x==0)  return NULL;
   root=(nd *)malloc(sizeof(nd));
 root->num=x;
 root->left=creat(root->left);
 root->right=creat(root->right);
 return root;
}
void pre_print(nd *root)
{
 a[k++]=root->num;
 if(root->left!=NULL) pre_print(root->left);
 if(root->right!=NULL) pre_print(root->right);
}
void mid_print(nd *root)
{
 if(root->left!=NULL) mid_print(root->left);
  a[k++]=root->num;
 if(root->right!=NULL) mid_print(root->right);
}
void las_print(nd *root)
{
 if(root->left!=NULL) las_print(root->left);
 if(root->right!=NULL) las_print(root->right);
 a[k++]=root->num;
}
int main()
{
      nd *tree;
   int i;
   tree=NULL;
   tree=creat(tree);
   k=0;
   pre_print(tree);
   for(i=0;i<k-1;i++)
    printf("%d ",a[i]);
   printf("%d\n",a[k-1]);
   k=0;
   mid_print(tree);
  for(i=0;i<k-1;i++)
     printf("%d ",a[i]);
   printf("%d\n",a[k-1]);
   k=0;
   las_print(tree);
      for(i=0;i<k-1;i++)
    printf("%d ",a[i]);
   printf("%d\n",a[k-1]);
      return 0;
}



推荐:数据结构和算法二叉树排序

顾名思义,二叉树排序就是利用二叉搜索树的特点进行排序,前面提到过二叉搜索树的特点是,左子节点比自己小,右子节点比自己大,那么二叉树排序的思想就是先将待

RE版本

#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct haha
{
    struct haha *l_child;
    struct haha *r_child;
    int num;
}node;
int  a[100000];
int ans[100000];
int n,k;
node * make_tree(node *temp)
{
//  node *temp;wentichuxianzai zheli
//  temp=root;caocaocaocao
    //printf("n=%d\n",n);
    if(temp==NULL)
    {
        if(a[n]!=0)
        {
        temp=(node *)malloc(sizeof(node));
        temp->l_child=temp->r_child=NULL;
        temp->num=a[n];
        }
        else return NULL;
    }
         ++n;
         temp->l_child=make_tree(temp->l_child);
         ++n;
         temp->r_child=make_tree(temp->r_child);
    return temp;
}
void print_pre(node *temp)
{
    ans[k++]=temp->num;
    if(temp->l_child!=NULL) print_pre(temp->l_child);
    if(temp->r_child!=NULL) print_pre(temp->r_child);
}
void print_mid(node *temp)
{
    if(temp->l_child!=NULL) print_pre(temp->l_child);
    ans[k++]=temp->num;
    if(temp->r_child!=NULL) print_pre(temp->r_child);
}
void print_las(node *temp)
{
    if(temp->l_child!=NULL) print_pre(temp->l_child);
    if(temp->r_child!=NULL) print_pre(temp->r_child);
    ans[k++]=temp->num;
}
int main()
{
    int i,j,d;
    char s[400000];
    node *root;
    while(gets(s))
    {
          d=strlen(s);
          j=0;
          for(i=0;i<d;i++)
              if('0'<=s[i]&&s[i]<='9')
                  a[j++]=s[i]-'0';
              root=NULL;
              n=0;
          root=make_tree(root);
          k=0;
          print_pre(root);
          for(i=0;i<k-1;i++)
              printf("%d ",ans[i]);
          printf("%d\n",ans[k-1]);
          k=0;
          print_mid(root);
          for(i=0;i<k-1;i++)
              printf("%d ",ans[i]);
          printf("%d\n",ans[k-1]);
          k=0;
          print_las(root);
          for(i=0;i<k-1;i++)
              printf("%d ",ans[i]);
          printf("%d\n",ans[k-1]);
    }
    return 0;
}


推荐:数据结构与算法——二叉树的前序遍历,中序遍历,后序遍历

二叉树的遍历规则主要有三种:前序遍历,中序遍历,后序遍历。它们是根据访问根节点的先后顺序来划分的。 前序遍历: 1.访问根节点 2.前序遍历左子树 3.右序遍历

问题 H: 数据结构(C语言版)算法6.1至算法6.4__二叉树遍历 时间限制: 1 Sec  内存限制: 128 MB 提交: 128  解决: 34 [提交][状态][讨论版] 题目描述 求二叉树的先序、中序及后序遍历序列。结点

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。