如何通过后序遍历序列和中序遍历序列来确定一棵二叉树??

  • 根据后序遍历序列最后一个结点确定根结点;
  • 根据根结点在中序遍历序列中分割出左右两个子序列;
  • 对左子树和右子树分别递归使用相同的方式继续分解;
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4
  5 struct node
  6 {
  7     char data;
  8     struct node *lt, *rt;
  9 };
 10
 11 // 用先序序列和中序序列建立二叉树
 12 struct node *create_by_pre_and_mid(int n, char *pre, char *mid)
 13 {
 14     struct node *root;
 15     int i;
 16
 17     if(n==0)
 18         return NULL;
 19
 20     root=(struct node *)malloc(sizeof(struct node));
 21     root->data=pre[0];
 22
 23     for(i=0;i<n;i++) // 寻找左右子树的元素
 24         if(pre[0]==mid[i])
 25             break;
 26
 27     root->lt = create_by_pre_and_mid(i, pre+1, mid); // 建立左子树
 28     root->rt = create_by_pre_and_mid(n-i-1, pre+i+1, mid+i+1); // 建立右子树
 29
 30     return root;
 31 }
 32
 33 // 用后序序列和中序序列建立二叉树
 34 struct node *create_by_post_and_mid(int n, char *post, char *mid)
 35 {
 36     struct node *root;
 37     int i;
 38
 39     if(n==0)
 40         return NULL;
 41
 42     root=(struct node *)malloc(sizeof(struct node));
 43     root->data=post[n-1];
 44
 45     for(i=0;i<n;i++) // 寻找左右子树的元素
 46         if(post[n-1]==mid[i])
 47             break;
 48
 49     root->lt = create_by_post_and_mid(i, post, mid); // 建立左子树
 50     root->rt = create_by_post_and_mid(n-i-1, post+i, mid+i+1); // 建立右子树
 51
 52     return root;
 53 }
 54
 55 // 后序遍历
 56 void postorder(struct node *root)
 57 {
 58     if(root)
 59     {
 60         postorder(root->lt);
 61         postorder(root->rt);
 62         printf("%c", root->data);
 63     }
 64 }
 65
 66 // 前序遍历
 67 void preorder(struct node *root)
 68 {
 69     if(root)
 70     {
 71         printf("%c", root->data);
 72         preorder(root->lt);
 73         preorder(root->rt);
 74     }
 75 }
 76
 77 // 中序遍历
 78 void midorder(struct node *root)
 79 {
 80     if(root)
 81     {
 82         midorder(root->lt);
 83         printf("%c", root->data);
 84         midorder(root->rt);
 85     }
 86 }
 87
 88
 89 int main( void )
 90 {
 91     struct node *root=NULL;
 92     int len;
 93     char *post = "DFEBGIHCA";
 94     char *pre = "ABDEFCGHI";
 95     char *mid = "DBFEAGCHI";
 96
 97     len=strlen(post);
 98
 99     //root=create_by_pre_and_mid(len, pre, mid);
100     root = create_by_post_and_mid(len, post, mid);
101
102     printf("\r\npreorder:\r\n");
103     preorder(root);
104
105     printf("\r\nmidorder:\r\n");
106     midorder(root);
107
108     printf("\r\npostorder:\r\n");
109     postorder(root);
110
111     printf("\r\n");
112
113
114     system("pause");
115     return 0;
116 }
12-14 20:29
查看更多