作业2

问题1

将关键字序列(10, 2, 26, 4, 18, 24, 21, 15, 8, 23, 5, 12, 14)依次插入到初态为空的二叉排序树中，请画出所得到的树T； 然后画出删除10之后的二叉排序树T1 ； 若再将10插入到T1中得到的二叉排序树T2是否与T1相同? 请给出T2的先序、中序和后序序列。

• 二叉排序树：

  
  

• 删除10后：

  
  

• 插入10后：

  
  

• 先序序列：12， 2， 4， 8， 5， 10， 26， 18， 15， 14， 24， 21， 23

• 中序序列：2， 4， 5， 8， 10， 12， 14， 15， 18， 21， 23， 24， 26

• 后序序列： 5， 10， 8， 4， 2， 14， 15， 23， 21， 24， 18， 26， 12

问题2

设有关键字序列为：(Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar) ，请手工构造一棵二叉排序树。该树是平衡二叉排序树? 若不是，请为其构造一棵平衡二叉排序树。

• 大小顺序是：Apr 1< Aug 2< Dec 3< Feb4 < Jan 5 < July6 < June 7< Mar8 < May9 < Nov 10< Oct11 < Sept12。转化为数字表示，则输入(Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar) --->(3，4，10，11，7，12，2，1，9，6，5，8)

  
  
  
  

  不是平衡二叉树。