318二叉树遍历

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct treenode{
 5     char data;
 6     struct treenode *lchild;
 7     struct treenode *rchild;
 8 }treenode,*tree;
 9 
10 tree createTree(char *preorder,char *inorder,int n);
11 void postorderTraverse(tree t);
12 int main()
13 {
14     char preorder[27],inorder[27];
15     gets(preorder);
16     gets(inorder);
17     
18     int n;//the number of the vertex
19     n=strlen(preorder);
20     
21     
22     tree t;
23     t=createTree(preorder,inorder,n);
24     //
25     postorderTraverse(t);
26     return 0;
27 }
28 tree createTree(char *pre,char *in,int n)
29 {
30     int k;
31     char *p;//指针变量p跟习惯用的i/j/k没有区别
32     //if(n<=0) return NULL;
33     
34     treenode *b=(treenode*)malloc(sizeof(treenode));
35     b->data=*pre;
36     for(p=in;p<in+n;p++)
37     {
38         if(*p==*pre) break;
39     }
40     
41     k=p-in;
42     b->lchild=createTree(pre+1,in,k);
43     b->rchild=createTree(pre+k+1,p+1,n-k-1);
44     return b;
45     
46 }
47 void postorderTraverse(tree t)
48 {
49     /*if(!t) printf("EMPTY\n");
50     else
51     {
52         postorderTraverse(t->lchild);
53         postorderTraverse(t->rchild);
54         printf("%d ", t->data);
55     }*/
56     if(t)
57     {
58         postorderTraverse(t->lchild);
59         postorderTraverse(t->rchild);
60         printf("%c", t->data);
61     }
62 }

题目：二叉树遍历

问题描述

给定一棵二叉树的先序遍历和中序遍历序列，求其后序遍历序列。

输入格式

        输入数据有两行，为两个字符串，其长度n均小于等于26。第一行为先序遍历序列，第二行为中序遍历序列。

二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出格式

        在一行上输出后序遍历序列。

样例输入

        ABC

BAC

样例输出

        BCA

这个题核心create函数 

42、43两行 一开始理解不了（看的还原二叉树 - 给定一棵二叉树的先序遍历序列和中序遍历序列，计算该二叉树的高度。_给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。 输入格式-CSDN博客），主要是对递归的理解不到位——递归每一层的变量值都是在变的

这个函数（已知先序和中序创建二叉树）还很常用 只能多写两遍了叭

附上已知前序遍历和中序遍历求二叉树_已知先序遍历和中序遍历求二叉树-CSDN博客，有图文一看就懂的程度