宁德做网站的公司,兰州市规划建设局网站,网站分类目录源码,专业网站建设怎么样P1827 [USACO3.4] 美国血统 American Heritage#xff08;前序 中序 生成后序#xff09;
一、前言
二叉树入门题。涉及到树的基本知识、树的结构、树的生成。 本文从会从结构#xff0c;到完成到#xff0c;优化。
二、基础知识
Ⅰ、二叉树的遍历
前序遍历#xff…P1827 [USACO3.4] 美国血统 American Heritage前序 中序 生成后序
一、前言
二叉树入门题。涉及到树的基本知识、树的结构、树的生成。 本文从会从结构到完成到优化。
二、基础知识
Ⅰ、二叉树的遍历
前序遍历 根左右中序遍历 左根右后序遍历 左右根 通过上面的观察可得根在那就是什么方式的遍历 Ⅱ、二叉树的结构
二叉树的结构节点值 左节点指针 右节点指针
// c的结构体写法
struct node {char val;node *left;node *right;node() : val(0), left(nullptr), right(nullptr){}node(int val) : val(val), left(nullptr), right(nullptr){}node(int val, node *left, node *right) : val(val), left(left), right(right){}
};
// c语言结构体写法
struct node {char val;struct node *left;struct node *right;node() : val(0), left(NULL), right(NULL){}node(int val){val val;left NULL;right NULL;{node(int val, struct node *left, struct node *right) {val val;left left;right right;}
};三、直接思路
通过 前序 中序 直接生成 树。然后再前序遍历可以过 现在的问题就变成了。怎么生成树了。 估计大家在学习数据结构二叉树这一章节中。老师肯定讲过手写这个题通过前序或后序找到根节点然后把中序分成两部分左子树右子树。但是现在怎么把他变成代码呢
#include iostream
using namespace std;struct node {char val;node *left;node *right;node() : val(0), left(nullptr), right(nullptr){}node(char x) : val(x), left(nullptr), right(nullptr){}node(char x, node *left, node *right) : val(x), left(left), right(right){}
};
/*
s1 中序
[inorderBegin inorderEnd
s2 前序
[preorderBegin preorderEnd
上述就是现在树的范围
再分割子树的范围就可以了
明白范围左端点可取右端点不可取
*/
node *traversal(string s1, int inorderBegin, int inorderEnd, string s2, int preorderBegin, int preorderEnd) {if (preorderEnd preorderBegin) return nullptr;char val s2[preorderBegin];node *root new node(val);if (preorderEnd - preorderBegin 1) return root;int delimiterIndex; // 左右子树的分割点for (delimiterIndex inorderBegin; delimiterIndex inorderEnd; delimiterIndex) {if (s1[delimiterIndex] val) break;}// 左子树// 中序int leftInorderBegin inorderBegin;int leftInorderEnd delimiterIndex;// 前序int leftPreorderBegin preorderBegin 1;int leftPreorderEnd preorderBegin 1 delimiterIndex - inorderBegin;// 右子树int rightInorderBegin delimiterIndex 1;int rightInorderEnd inorderEnd;int rightPreorderBegin preorderBegin delimiterIndex - inorderBegin 1;int rightPreorderEnd preorderEnd;root-left traversal(s1, leftInorderBegin, leftInorderEnd, s2, leftPreorderBegin, leftPreorderEnd);root-right traversal(s1, rightInorderBegin, rightInorderEnd, s2, rightPreorderBegin, rightPreorderEnd);return root;
}void dfs(node *root) {if (!root) return ;dfs(root-left);dfs(root-right);cout root-val;
}int main() {node *tree;string s1, s2;cin s1 s2;tree traversal(s1, 0, s1.size(), s2, 0, s2.size());dfs(tree);return 0;
} 四、优化
通过上面可以发现他在生成树的过程中就是经行的后续遍历。所以不用直接生成树。
#include iostream
using namespace std;void traversal(string s1, int inorderBegin, int inorderEnd, string s2, int preorderBegin, int preorderEnd) {if (preorderEnd preorderBegin) return;char val s2[preorderBegin];int delimiterIndex; // 左右子树的分割点for (delimiterIndex inorderBegin; delimiterIndex inorderEnd; delimiterIndex) {if (s1[delimiterIndex] val) break;}// 左子树// 中序int leftInorderBegin inorderBegin;int leftInorderEnd delimiterIndex;// 前序int leftPreorderBegin preorderBegin 1;int leftPreorderEnd preorderBegin 1 delimiterIndex - inorderBegin;// 右子树int rightInorderBegin delimiterIndex 1;int rightInorderEnd inorderEnd;int rightPreorderBegin preorderBegin delimiterIndex - inorderBegin 1;int rightPreorderEnd preorderEnd;traversal(s1, leftInorderBegin, leftInorderEnd, s2, leftPreorderBegin, leftPreorderEnd);traversal(s1, rightInorderBegin, rightInorderEnd, s2, rightPreorderBegin, rightPreorderEnd);cout val;
}int main() {string s1, s2;cin s1 s2;traversal(s1, 0, s1.size(), s2, 0, s2.size());return 0;
}
五、相关题目
LeetCode 105. 从前序与中序遍历序列构造二叉树LeetCode 106. 从中序与后序遍历序列构造二叉树
六、最后
创作不易留个赞鼓励一下把
