给定二叉树的先序遍历和中序遍历,输出它的后

给定二叉树的先序遍历和中序遍历,输出它的后序遍历序列。

这里没再用到先申请大Node数组的方法了,想练练写动态内存分配和释放的,一次OK了,也没怎么出错啊,开心~

方法二 - Code:

//给出一个二叉树的先序遍历和中序遍历,输出它的后序遍历
//直接构造的方法白书已给出。这里是先递归构造二叉树,然后进行后序遍历。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 1000

typedef struct node
{
 char data;
 struct node *left,*right;       
}Node;

void postorder(Node *root);
Node* build(int n,char *s1,char *s2);
Node* newNode();
void remove_tree(Node* root);

char s1[MAXN],s2[MAXN];

int main()
{
 while(scanf("%s%s",s1,s2)==2)
 {
  int n=strlen(s1);
  Node *root=build(n,s1,s2);
  postorder(root);   
  printf("\n");                       
  remove_tree(root);
 } 
}

void postorder(Node *root)
{
 if(root==NULL) return;
 postorder(root->left);
 postorder(root->right);
 printf("%c",root->data);
}

Node* build(int n,char *s1,char *s2)
{
 if(n<=0) return NULL;
 Node *r=newNode();
 r->data=s1[0];
 int p=strchr(s2,s1[0])-s2;
 r->left=build(p,s1+1,s2);
 r->right=build(n-1-p,s1+1+p,s2+p+1);
 return r;   
}

Node* newNode()
{
 Node* u=(Node*)malloc(sizeof(Node));
 if(u!=NULL)
 {
  u->data=0;
  u->left=u->right=NULL;         
 }   
 return u;
}

void remove_tree(Node* root)
{
 if(root!=NULL)
 {
  remove_tree(root->left);
  remove_tree(root->right);
  free(root);           
 }   
}

方法一 - Code:

#include<stdio.h>
#include<string.h>
#define MAXN 256

void build(int n,char *s1,char *s2,char *s);

int main()
{
 char s1[MAXN],s2[MAXN],ans[MAXN];
 while(scanf("%s%s",s1,s2)==2)
 {
  int n=strlen(s1);
  build(n,s1,s2,ans);           
  ans[n]='\0';
  printf("%s\n",ans);               
 } 
 return 0;
}

void build(int n,char *s1,char *s2,char *s)
{
 if(n<=0) return;
 int p=strchr(s2,s1[0])-s2;
 build(p,s1+1,s2,s);
 build(n-p-1,s1+p+1,s2+p+1,s+p);
 s[n-1]=s1[0];   
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

Java中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/469df30bbb0af6b8c323b4339923d23a.html