网站开发安全模块方案/福州今日头条新闻

问题一：如何根据先序序列+中序序列建立二叉树？

输入样例：

第一行输入序列长度n，第二行输入n个字符表示二叉树先序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列

9
ABDGHCEFI
GDHBAECIF

输出样例：

输出二叉树后序遍历的序列。

GHDBEIFCA

思路：

一道非常基础的二叉树问题，而解决这类问题是有模板的。也就是根据遍历顺序来入手，即可解决。在创建左子树和右子树的时候，对边界点会有疑问，我比较推荐自己画一个图，这样可以定位到你要的那个点。（这里数字顺序与遍历无关，只是为了定位到临界点）

ps：题目中的n在实际运用中，可以去掉，通过string.size()来代替即可。

代码：

#include<bits/stdc++.h>
using namespace std;/*9ABDGHCEFIGDHBAECIF结果：GHDBEIFCA
*/struct treeNode
{char data;treeNode* left;			//左孩子treeNode* right;		//右孩子
};
// 前序：中左右
// 中序：左中右
void CreateTree_pre_middle(treeNode* &node, string pre_order, string in_order, int pre1, int pre2, int middle1, int middle2)
{//前提条件if (pre2 >= pre1 && middle2 >= middle1){node = new treeNode();//第一个是根节点node->data = pre_order[pre1];//初始化node->left = node->right = nullptr;//在中序中找到根节点 i 的位置int i;for (i = middle1; i <= middle2; ++i){if (in_order[i] == node->data)break;}//创建左子树和右子树//注意这里是：node->left，node->right，不是nodeCreateTree_pre_middle(node->left, pre_order, in_order, pre1 + 1, pre1 + i - middle1, middle1, i - 1);CreateTree_pre_middle(node->right, pre_order, in_order, pre1 + i - middle1 + 1, pre2, i + 1, middle2);}
}
void post_view(treeNode* node)
{if (node == nullptr)	return;post_view(node->left);post_view(node->right);cout << node->data;
}int main()
{int n;cin >> n;string pre_order, in_order;cin >> pre_order >> in_order;treeNode* root;CreateTree_pre_middle(root, pre_order, in_order, 0, n - 1, 0, n - 1);post_view(root);return 0;
}

问题二：如何根据中序序列+后序序列建立二叉树？

思路：

和问题一同样的道理，很容易通过中序和后序遍历的顺序来建立二叉树，只要记得二叉树三种遍历顺序，其实这类题很容易进行实现。所以一定要对二叉树的遍历顺序非常了解。（就是模板题）

下面给出代码：

#include<bits/stdc++.h>
using namespace std;struct treeNode
{char data;treeNode* left;treeNode* right;
};
//中序：左中右
//后序：左右中
void CreateTree_middle_post(treeNode* &node, string middle_order, string post_order, int middle1, int middle2, int post1, int post2)
{//先决条件if (middle1 <= middle2 && post1 <= post2){node = new treeNode();//根节点赋值node->data = post_order[post2];//初始化node->left = node->right = nullptr;//找根节点 i 的位置int i;for (i = middle1; i <= middle2; ++i){if (middle_order[i] == node->data)break;}//创建左子树和右子树//中序：左中右//后序：左右中CreateTree_middle_post(node->left, middle_order, post_order, middle1, i - 1, post1, post1+i-1 - middle1);CreateTree_middle_post(node->right, middle_order, post_order, i + 1, middle2, post1 + i - middle1, post2 - 1);}
}void view_pre(treeNode* node)
{if (node == nullptr) return;cout << node->data;view_pre(node->left);view_pre(node->right);
}
int main()
{int n;string middle, post;cin >> n;cin >> middle >> post;treeNode* root;CreateTree_middle_post(root, middle, post, 0, n - 1, 0, n - 1);view_pre(root);return 0;
}