Tree Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> #include <stdio.h> #include <string.h> #include <string> using namespace std; // A utility function to search x in arr[] of size n int search(char arr[], char x, int n) { for (int i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } // Prints postorder traversal from given inorder and preorder traversals void printPostOrder(char in[], char pre[], int n) { // The first element in pre[] is always root, search it // in in[] to find left and right subtrees int root = search(in, pre[0], n); // If left subtree is not empty, print left subtree if (root != 0) printPostOrder(in,pre+1,root); // If right subtree is not empty, print right subtree if (root != n-1) printPostOrder(in+root+1,pre+root+1,n-root-1); // Print root cout << pre[0]; } // Driver program to test above functions int main() { char in[28]; char pre[28]; while(scanf("%s %s",pre,in) == 2) { int n = strlen(in); //printf("%d\n",search(in, pre[0], n)); //cout<<n<<"\n"; //cout << "Postorder traversal " << endl; printPostOrder(in, pre, n); cout<<"\n"; } return 0; } |