二叉树前序、中序、后序遍历相互求法

1.访问根节点
2.前序遍历左子树
3.前序遍历右子树

1.中序遍历左子树
2.访问根节点
3.中序遍历右子树

1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

``` 1 #include <iostream>
2 #include <fstream>
3 #include <string>
4
5 struct TreeNode
6 {
7   struct TreeNode* left;
8   struct TreeNode* right;
9   char  elem;
10 };
11
12 void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
13 {
14   if(length == 0)
15     {
16       //cout<<"invalid length";
17       return;
18     }
19   TreeNode* node = new TreeNode;//Noice that [new] should be written out.
20   node->elem = *preorder;
21   int rootIndex = 0;
22   for(;rootIndex < length; rootIndex++)
23     {
24       if(inorder[rootIndex] == *preorder)
25       break;
26     }
27   //Left
28   BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
29   //Right
30   BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
31   cout<<node->elem<<endl;
32   return;
33 }
34
35
36 int main(int argc, char* argv[])
37 {
38     printf("Hello World!\n");
39     char* pr="GDAFEMHZ";
41
42     BinaryTreeFromOrderings(in, pr, 8);
43
44     printf("\n");
45     return 0;
46 }```

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

```#include <iostream>
#include <fstream>
#include <string>

struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
char  elem;
};

TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)
{
if(length == 0)
{
return NULL;
}
TreeNode* node = new TreeNode;//Noice that [new] should be written out.
node->elem = *(aftorder+length-1);
std::cout<<node->elem<<std::endl;
int rootIndex = 0;
for(;rootIndex < length; rootIndex++)//a variation of the loop
{
if(inorder[rootIndex] ==  *(aftorder+length-1))
break;
}
node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);
node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1));

return node;
}

int main(int argc, char** argv)
{
char* af="AEFDHZMG";
BinaryTreeFromOrderings(in, af, 8);
printf("\n");
return 0;
}```

已知二叉树前、中序遍历，求后序 / 已知二叉树中、后序遍历，求前序

void solve(int start,int end,int root) { // 前序和中序 -> 后序 // 每次调用solve()函数,传入pre-order的start,end,root if (start > end) // 递归边界 return; int i = start; while (i < end && in.at(i) != pre.at(root)) // 找到左右子树的分割点 i++; solve(start, i - 1, root +