已知树的前序和中序遍历，求后序遍历；后序和中序，求前序

时间：2021-04-29 12:38:52

首先需要说明的是，网上不知道为什么很多误传，说给定前序、中序和后序中的两个，可以唯一确定另一个，显然这是错误的。给定前序和后序，是无法确定中序的，一个简单的例子就是只有两个节点的树，前序和后序给定，中序无法确定。

代码如下：

已知树的前序和中序遍历，求后序遍历；后序和中序，求前序已知树的前序和中序遍历，求后序遍历；后序和中序，求前序
  1 /*
  2 * Copyright (c) 2014
  3 * All Rights Reserved.
  4 * author: laohaizi
  5 */
  6 
  7 #include <iostream>
  8 #include <string>
  9 #include <string.h>
 10 #include <stdio.h>
 11 using namespace std;
 12 
 13 typedef struct _NODE
 14 {
 15     char name;
 16     struct _NODE *left,*right;
 17 }NODE;
 18 
 19 char *preorder="abcdefg";
 20 char *inorder="cbedagf";
 21 //char *inorder="abcdefg";
 22 char *postorder="cedbgfa";
 23 const int preorder_len = strlen(preorder);
 24 const int inorder_len = strlen(inorder);
 25 const int postorder_len = strlen(postorder);
 26 
 27 NODE * PostOrder(char *preorder, int prebeg, int preend, char *inorder, int inbeg, int inend)
 28 {
 29     if (prebeg > preend || inbeg > inend || prebeg >= preorder_len || inbeg >= inorder_len || preend < 0 || inend < 0)
 30     {
 31         return NULL;
 32     }
 33     NODE *p = new NODE;
 34     p->name = preorder[prebeg];
 35     int k = 0;
 36     int cnt = 0;
 37     for (k = inbeg; k <= inend; ++k)
 38     {
 39         cnt ++;
 40         if (inorder[k] == preorder[prebeg])
 41         {
 42             break;
 43         }
 44     }
 45     p->left = PostOrder(preorder,prebeg+1,prebeg+cnt-1,inorder,inbeg,k-1);
 46     p->right = PostOrder(preorder,prebeg+cnt,preend,inorder,k+1,inend);
 47     return p;
 48 }
 49 
 50 NODE * PreOrder(char *postorder, int postbeg, int postend, char *inorder, int inbeg, int inend)
 51 {
 52     if (postbeg > postend || inbeg > inend || postbeg >= postorder_len || inbeg >= inorder_len || postend < 0 || inend < 0)
 53     {
 54         return NULL;
 55     }
 56     NODE *p = new NODE;
 57     p->name = postorder[postend];
 58     int k = 0;
 59     int cnt = 0;
 60     for (k = inbeg; k <= inend; ++k)
 61     {
 62         cnt ++;
 63         if (inorder[k] == postorder[postend])
 64         {
 65             break;
 66         }
 67     }
 68     p->left = PreOrder(postorder,postbeg,postbeg+cnt-2,inorder,inbeg,k-1);
 69     p->right = PreOrder(postorder,postbeg+cnt-1,postend-1,inorder,k+1,inend);
 70     return p;
 71 }
 72 
 73 int NodeNum(NODE *p)
 74 {
 75     if (p == NULL)
 76         return 0;
 77     return NodeNum(p->left)+NodeNum(p->right)+1;
 78 }
 79 
 80 void PostorderTraverse(NODE *p)
 81 {
 82     if(p != NULL)
 83     {
 84         PostorderTraverse(p->left);
 85         PostorderTraverse(p->right);
 86         cout<<p->name;
 87     }
 88 }
 89 
 90 void PreorderTraverse(NODE *p)
 91 {
 92     if(p != NULL)
 93     {
 94         cout<<p->name;
 95         PreorderTraverse(p->left);
 96         PreorderTraverse(p->right);
 97     }
 98 }
 99 
100 int main()
101 {    
102     //get postorder
103     NODE *root = PostOrder(preorder,0,preorder_len-1,inorder,0,inorder_len-1);
104     
105     int nodenum = NodeNum(root);
106     if (nodenum != preorder_len)
107     {
108         cout<<"post order not exist."<<endl;
109         return 0;
110     }
111 
112     cout<<"post order: ";
113     PostorderTraverse(root);
114     cout<<endl;
115 
116     //get preorder
117     root = PreOrder(postorder,0,postorder_len-1,inorder,0,inorder_len-1);
118     
119     nodenum = NodeNum(root);
120     if (nodenum != postorder_len)
121     {
122         cout<<"pre order not exist."<<endl;
123         //return 0;
124     }
125 
126     cout<<"pre order: ";
127     PreorderTraverse(root);
128     cout<<endl;
129     return 0;
130 }
View Code

 

标签：

相关文章