根据数据结构的内容，我们已知：前+中 / 后+中 / 层+中，均可唯一确定一棵二叉树。
在本文中，将介绍基于前序和中序序列的建立二叉树的方式。
1. 问题描述
已知二叉树的前序序列 和中序序列字符数组，编写算法建立二链表的二叉树。
测试数据： 前序序列{ ABHFDECKG } 中序序列{ HBDFAEKCG }2. 解决方案
假设已知前序序列prestr，中序序列instr。按照以下步骤解决问题：
1. 将prestr的首字母取出，即为当前树的根结点root2. 搜索instr中root的位置pos（从0开始）3. 将prestr中从root向后pos个字符设为prestr1,剩余字符串设为prestr2； 将instr中pos之前的子串设为instr1，将instr中pos之后的子串设为instr24. 分别将prestr1和instr1，prestr2和instr2打包，返回步骤1重复进行上述步骤，直到划分出的子串长度为03. 代码 //字符串建树#include<iostream>#include<cstdio>#include<string>using namespace std;struct Node {char data;Node* lch;Node* rch;Node(char x) :data(x), lch(NULL), rch(NULL) {}};Node* Create(Node* root, string prestr, string instr){if (prestr.size() == 0)return NULL;else{char fir = prestr[0];root = new Node(fir);int pos = instr.find(fir);string prestr1 = prestr.substr(1, pos);string prestr2 = prestr.substr(pos + 1);string instr1 = instr.substr(0, pos);string instr2 = instr.substr(pos + 1);root->lch = Create(root->lch, prestr1, instr1);root->rch = Create(root->rch, prestr2, instr2);}return root;}void preorder(Node* root){if (root == NULL) return;cout << root->data;preorder(root->lch);preorder(root->rch);return;}void inorder(Node* root){if (root == NULL) return;inorder(root->lch);cout << root->data;inorder(root->rch);return;}void postorder(Node* root){if (root == NULL) return;postorder(root->lch);postorder(root->rch);cout << root->data;return;}int main(){string prestrs, instrs;prestrs = "ABHFDECKG";instrs = "HBDFAEKCG";Node* root = NULL;root = Create(root, prestrs, instrs);printf("preoder:");preorder(root);printf("n");printf("inoder:");inorder(root);printf("n");printf("postoder:");postorder(root);printf("n");return 0;}
在上述代码中，我们灵活的使用了string类的方法，包括.find()，.substr()等，可以直接实现我们的设计方案。
4. 拓展：基于层序序列建立二叉树
那么基于层序序列，我们应该如何建立二叉树呢？
假设给定的数据是：
const char *data = "ABCDEG000F00H";其中字母代表根结点存储的数据，字母‘0’代表结点为空。
代码如下：
//字符串建树#include<iostream>#include<cstdio>#include<string>using namespace std;struct Node {char data;Node* lch;Node* rch;Node(char x):data(x),lch(NULL),rch(NULL){}};int i = 1;Node* Create(Node* root,const char *data,int i,int m){if (data[i] == '0'|| i>=m) //注意此处一定要限制i的范围return NULL;else{root = new Node(data[i]);root->lch = Create(root->lch, data,2*i+1,m);root->rch = Create(root->rch, data,2*i+2,m);}return root;}void preorder(Node* root){if (root == NULL) return;cout << root->data;preorder(root->lch);preorder(root->rch);return;}void inorder(Node* root){if (root == NULL) return;inorder(root->lch);cout << root->data;inorder(root->rch);return;}void postorder(Node* root){if (root == NULL) return;postorder(root->lch);postorder(root->rch);cout << root->data;return;}int main(){const char *data = "ABCDEG000F00H";int m = strlen(data);Node* root = NULL;root = Create(root,data,0,m);printf("preoder:");preorder(root);printf("n");printf("inoder:");inorder(root);printf("n");printf("postoder:");postorder(root);printf("n");return 0;}应该注意的点是如何根据当前结点的编号，推导出两个子结点的编号。
5. 总结
目前为止，树这一章节复习结束了。感觉难度适中吧，接下来就到了图的章节了。