给定一个预定的二叉树访问，构造一个具有相同的预定访问的二叉搜索树。 （如果可能的话） [英] Given a pre-order binary tree visit construct a binary search tree with the same pre-order visit. (if possible)

问题描述

我正在尝试解决此问题：给出了一个二叉树，检查他的预订访问，并用相同的预订访问构建一棵二叉搜索树。演示是否总是可能的，如果没有给出示例，何时这不可能。
有什么帮助吗？我需要编写伪代码并给出时间复杂度，但我对构建一个二进制搜索树有很多疑问，对于每个可能的二进制树都具有相同的预访问。

Im trying to solve this problem:" A binary tree is given, check his pre-order visit and build a binary search tree with the same pre-order visit. Demonstrate if it is always possible, if not give an example when this is not possible." Any help? I need to write pseudocode and give time complexity but i have a lot of doubts about building a binary-search-tree with the same pre-order visit for every possible binary tree.

推荐答案

如果使用经典算法插入二进制搜索树，即执行搜索并在找到的 NULL 停止搜索以放置新节点的指针，然后仅将其插入空树中，则预排序序列将产生恰好具有给定预排序序列的二叉树。

If you are using the classic algorithm for inserting in a binary search tree, that is, to perform a search and on the found NULL pointer where the search was stopped to put the new node, then just to insert in an empty tree the preorder sequence will produce exactly a binary tree with exactly the given preorder sequence.

尝试一下。遍历任何预购序列并将其插入一棵空树中，您会意识到的。

Just try. Traverse any preorder sequence and insert it in an empty tree and you will realize it.

我希望对您有所帮助。欢迎堆栈溢出！

I hope to help you. And welcome to stack overflow!

这篇关于给定一个预定的二叉树访问，构造一个具有相同的预定访问的二叉搜索树。 （如果可能的话）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！