题目内容
(请给出正确答案)
[主观题]
将二叉排序树T的先序序列中的关键字依次插入到一棵空的二叉排序树中,所得到的二叉排序树T'与T是否相同?为什么?
答案
二叉排序树 T' 与 T 相同。 因为二叉排序树属于二叉树,其先序序列的第一个元素一定是二叉排序树的根,而对应先序序列的根后面所有元素分为两组:从根的后一元素开始的其值小于根值的一组元素(第一组)就是根的左子树的节点的先序序列,剩下的元素(第二组)值大于根值,即为根的右子树的节点的先序序列。 在把先序序列的元素依次插入初始为空的二叉排序树时,第一个元素就成树的根,它后面第一组元素的值都小于根节点的值,可以递归建立根的左子树;第二组元素的值都大于根节点的值,可以递归建立根的右子树。
![](https://lstatic.shangxueba.com/sxbcn/h5/images/tips_org.png)