二叉树由先序和中序建树

递归

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <iostream>
  3 #include <vector>
  4 #include <algorithm>
  5 #include <string>
  6 using namespace std;
  7 
  8 template <class T>
  9 struct Node {
 10     T data;
 11     Node *left;
 12     Node *right;
 13 
 14     Node() : data(), left(NULL), right(NULL) {}    // data()将使内置类型对象也初始化为0
 15 };
 16 
 17 /*
 18 ** 根据二叉树的先序遍历序列与中序遍历序列建立二叉树。
 19 ** 
 20 ** head:        建立的树的根的地址
 21 ** pre_begin:    先序遍历序列的首位置
 22 ** pre_end:        先序遍历序列的尾位置的下一位置
 23 ** in_begin:    中序遍历序列的首位置
 24 */
 25 template <class T, class Iter>
 26 void creat_tree(Node<T> *&head,
 27     const Iter pre_begin, const Iter pre_end, const Iter in_begin) {
 28     if (pre_begin == pre_end) {
 29         head = NULL;
 30         return ;
 31     }
 32 
 33     const Iter in_end = in_begin + (pre_end - pre_begin);
 34 
 35     head = new Node<T>();
 36     // 先设置根
 37     head->data = *pre_begin;    
 38     
 39     // 再建左子树
 40     const Iter in_middle = find(in_begin, in_end, *pre_begin);
 41     const Iter left_in_begin = in_begin;
 42     const Iter left_in_end = in_middle;
 43     const Iter left_pre_begin = pre_begin + 1;
 44     const Iter left_pre_end = left_pre_begin + (left_in_end - left_in_begin);
 45     creat_tree(head->left, left_pre_begin, left_pre_end, left_in_begin);
 46 
 47     // 后建右子树
 48     const Iter right_in_begin = in_middle + 1;
 49     const Iter right_in_end = in_end;
 50     const Iter right_pre_begin = left_pre_end;
 51     const Iter right_pre_end = pre_end;
 52     creat_tree(head->right, right_pre_begin, right_pre_end, right_in_begin);
 53 }
 54 
 55 template <class T>
 56 void free_tree(Node<T> *&root) {
 57     if (NULL == root) {
 58         return ;
 59     }
 60 
 61     free_tree(root->left);
 62     free_tree(root->right);
 63     free(root);
 64     root = NULL;
 65 }
 66 
 67 template <class T>
 68 void post_order(Node<T> *root) {
 69     if (NULL == root) {
 70         return ;
 71     }
 72 
 73     post_order(root->left);
 74     post_order(root->right);
 75     cout << root->data << endl;
 76 }
 77 
 78 template <class T>
 79 void input (vector<T> &v, int size) {
 80     T value;
 81     while(size--) {
 82         cin >> value;
 83         v.push_back(value);
 84     }
 85 }
 86 
 87 int main(int argc, char **argv) {
 88     freopen("cin.txt", "r", stdin);
 89 
 90     typedef char T;
 91     vector<T> pre;
 92     vector<T> in;
 93     int size;
 94     cin >> size;
 95     input(pre, size);
 96     input(in, size);
 97 
 98     Node<T> *head = NULL;
 99     creat_tree(head, pre.begin(), pre.end(), in.begin());
100 
101     cout << "Post-order:" << endl;
102     post_order(head);
103 
104     free_tree(head);
105     return 0;
106 }

输入样例：

1 4
2 A B C D
3 B A D C