来源于沈钰S同学(舒姐)
来源于沈钰S同学(舒姐)
abyssfall的博客_CSDN博客-计科学子的头发账本,代码存档领域博主
问题描述 :
目的:现有两个结点序列,分别是对同一个二叉树进行前序遍历和中序遍历(或中序和后序)的结果。要求设计一个算法,重构该二叉树,并输出该二叉树按照后序(前序)遍历时的结点序列。假定二叉树所有的结点的数据域的值都不相同。二叉树的存储结构的建立参见二叉树应用1。
一、已知前序和中序的结果,进行二叉树的重构:
提示:preOrder按照先根再左再右的顺序递归遍历,inOrder按照先左再根再右的顺序递归遍历。
举例说明:preOrder的输入pre={A,B,D,G,H,C,E,I,F},inOrder的输入in={G,D,H,B,A,E,I,C,F}。首先按preOrder遍历的顺序依次访问各结点。访问过程中,通过in得知各子树内inOrder遍历的顺序,从而重建以当前访问结点c为根的左子树与右子树。即:设preOrder遍历的当前结点为c,c在in中的位置为m,m左侧就是c的左子树,右侧就是c的右子树。同理递归。
(2)
参考函数原型:
(1)//重建二叉树的存储结构 (外壳)
template
BinaryTreeNode
(2)//重建二叉树的存储结构 (递归)
template
BinaryTreeNode
二、已知中序和后序的结果,进行二叉树的重构:
可参考一的思路。
参考函数原型:
(1)//重建二叉树的存储结构 (外壳)
template
BinaryTreeNode
(2)//重建二叉树的存储结构 (递归)
template
BinaryTreeNode
输入说明 :
第一行:重构选择(0:前序中序重构 1:中序后序重构)
0:
第二行:按前序遍历的结点序列,相邻结点用空格隔开
第三行:按中序遍历的结点序列,相邻结点用空格隔开
1:
第二行:按中序遍历的结点序列,相邻结点用空格隔开
第三行:按后序遍历的结点序列,相邻结点用空格隔开
输出说明 :
0:
第一行:按后序遍历的结点序列,相邻结点用","隔开
1:
第一行:按前序遍历的结点序列,相邻结点用","隔开
-----------
0
A B C D E
B D C E A
----------------
D,E,C,B,A
- #include
- using namespace std;
-
- template <class ElemType>
- struct BinaryTreeNode
- {
- ElemType data;
- BinaryTreeNode
*left; - BinaryTreeNode
*right; - };
-
- template <class ElemType>
- void cinin(string str, vector
&a) - {
- int len = str.length();
- string str0 = "";
- for (int i = 0; i < len; i++)
- {
-
- if (str[i] != ' ')
- {
- str0 += str[i];
- }
-
- else
- {
- a.push_back(str0);
- str0 = "";
- }
- }
- a.push_back(str0);
- }
-
- bool f = false;
-
- //前序遍历
- template <class ElemType>
- void visit1(BinaryTreeNode
*head) - {
- if (head)
- {
- if (f == false)
- {
- f = true;
- cout << head->data;
- }
-
- else
- {
- cout << "," << head->data;
- }
- }
- if (head->left)
- visit1(head->left);
- if (head->right)
- visit1(head->right);
- return;
- }
-
- //后序遍历
- template <class ElemType>
- void visit3(BinaryTreeNode
*head) - {
- if (head->left)
- visit3(head->left);
- if (head->right)
- visit3(head->right);
- if (head)
- {
- if (f == false)
- {
- f = true;
- cout << head->data;
- }
- else
- {
- cout << "," << head->data;
- }
- }
- return;
- }
-
- template <class ElemType>
- BinaryTreeNode
*reConstructCore_Pre_In(vector &pre, vector &in) - {
- if (pre.size() == 0)
- {
- return NULL;
- } //先序读完了,不进下一层递归了,没叶子了
-
- vector
left_pre, right_pre, left_in, right_in; //总之分一下,左右子树咔咔一下准备进递归 -
- BinaryTreeNode
*head = new BinaryTreeNode; - head->data = pre[0];
-
- int root = 0;
- int inlen = in.size();
- for (int i = 0; i < inlen; i++)
- {
- if (pre[0] == in[i])
- {
- root = i;
- break;
- }
- else
- continue;
- } //找一下根结点
-
- for (int i = 0; i < root; i++)
- {
- left_in.push_back(in[i]); //中序遍历,根结点之前全是左子树
- left_pre.push_back(pre[i + 1]); //先序遍历,第一个是根节点,往后读取相同数量丢入左子树
- }
-
- for (int i = root + 1; i < inlen; i++)
- {
- right_in.push_back(in[i]); //中序遍历,根节点之后全是右子树
- right_pre.push_back(pre[i]); //先序遍历,往后读取相同数量丢入左子树
- }
-
- head->left = reConstructCore_Pre_In(left_pre, left_in); //新分好的左子树
- head->right = reConstructCore_Pre_In(right_pre, right_in); //新分好的右子树
-
- return head;
- }
-
- template <class ElemType>
- BinaryTreeNode
*reConstructCore_In_Post(vector &in, vector &post) - {
- if (post.size() == 0)
- {
- return NULL;
- } //先序读完了,不进下一层递归了,没叶子了
-
- vector
left_in, right_in, left_post, right_post; //总之分一下,左右子树咔咔一下准备进递归 -
- BinaryTreeNode
*head = new BinaryTreeNode; -
- int postlen = post.size();
- head->data = post[postlen - 1]; //后序遍历末尾为根节点
-
- int root = 0;
- int inlen = in.size();
- for (int i = 0; i < inlen; i++)
- {
- if (post[postlen - 1] == in[i])
- {
- root = i;
- break;
- }
- else
- continue;
- } //找一下根结点在中序遍历的位置,分左右子树
-
- //cout << "root = " << root << "in[root] = " << in[root] << endl;
-
- for (int i = 0; i < root; i++)
- {
- left_in.push_back(in[i]); //中序遍历,根结点之前全是左子树
- left_post.push_back(post[i]); //后序遍历,往后读取相同数量丢入左子树
- }
-
- //for (int i = 0; i < root; i++)
- //{
- // cout << "left_in:" << endl;
- // cout << left_in[i] << " ";
- //}
- ///cout << endl;
-
- //for (int i = 0; i < root; i++)
- //{
- // cout << "left_post:" << endl;
- // cout << left_post[i] << " ";
- //}
- //cout << endl;
-
- for (int i = root + 1; i < inlen; i++)
- {
- right_in.push_back(in[i]); //中序遍历,根节点之后全是右子树
- right_post.push_back(post[i - 1]); //后序遍历,挨着上个循环结尾往后读取相同数量丢入左子树
- }
-
- //for (int i = 0; i < right_in.size(); i++)
- //{
- // cout << "right_in:" << endl;
- // cout << right_in[i] << " ";
- //}
- //cout << endl;
-
- //for (int i = 0; i < right_post.size(); i++)
- //{
- // cout << "right_post:" << endl;
- // cout << right_post[i] << " ";
- //}
- //cout << endl;
-
- head->left = reConstructCore_In_Post(left_in, left_post);
- head->right = reConstructCore_In_Post(right_in, right_post);
-
- return head;
- }
-
- int main()
- {
- char flag;
- cin >> flag;
- getchar();
-
- if (flag == '0')
- {
- string linepre;
- vector
pre; - getline(cin, linepre);
-
- cinin(linepre, pre);
-
- vector
in; - string linein;
- getline(cin, linein);
-
- cinin(linein, in);
-
- BinaryTreeNode
*root = new BinaryTreeNode; - root = reConstructCore_Pre_In(pre, in);
- visit3(root);
- }
-
- else if (flag == '1')
- {
- string linein;
- vector
in; - getline(cin, linein);
-
- cinin(linein, in);
-
- string linepost;
- vector
post; - getline(cin, linepost);
-
- cinin(linepost, post);
-
- BinaryTreeNode
*root = new BinaryTreeNode; - root = reConstructCore_In_Post(in, post);
- visit1(root);
- }
-
- getchar();
- getchar();
- return 0;
- }
-