我有以下序列：
中序：{4，2，5，1，6，3}前序：{1，2，4，5，3，6}
我想知道如何从这些序列中构造一棵二叉树，以及为什么它可以用中序和前序的组合来构造，而不能用其他的组合来构造。此外，我对如何在C中实现算法来实现这一点很感兴趣。
以下是我的具体问题：
如何从给定的中序和前序序列（如{4，2，5，1，6，3}和{1，2，4，5，3，6}）构造二叉树？为什么可以使用Inorder + Preorder或Inorder + Postorder组合来构造树，而不能使用Preorder + Postorder？有人能提供一个详细的算法和代码实现在C构造二叉树使用中序和前序遍历？我感谢任何关于这一点的见解和解释。谢谢你，谢谢！
if (traversal_type == "pre") {
root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start + 1, t_start + left_len, orderIndex, traversal_type);
root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start + left_len + 1, t_end, orderIndex, traversal_type);
}
else if (traversal_type == "post") {
root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start, t_end - 1, orderIndex, traversal_type);
root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start, t_start + left_len - 1, orderIndex, traversal_type);
}
1条答案
按热度按时间pdkcd3nj1#
重申导线的定义，以便于参考。对于一个给定的树，根为R，子树为T_L和T_r，你有：
R T_l... T_r...T_l... R T_r...如果你看一下你的前序遍历，你会看到根是1，但你不知道T_l在哪里停止，T_r在哪里开始。也可能是空的。这就是按序遍历的作用：
1左边的一切都是T_l的一部分，右边的一切都是T_r的一部分。因为1在有序遍历的位置4上，所以T_l包含3个项目，T_r包含2个项目。现在可以对输入数组进行切片，并递归地应用此过程，直到最终得到长度为1（叶节点）或0（空子树）的切片。
对于后序遍历，您从数组的末尾开始阅读根，但除此之外没有任何变化。
实现就交给你了，读者。