第十七天作业

老郭

今日主要学习内容

17.1 树的基本概念 二叉树及二叉搜索树的概念 实现二叉搜索树的插入操作
17.2 二叉搜索树的中序遍历 递归的问题
17.3 二叉搜索树的先序遍历与后序遍历
17.4 二叉搜索树 查找指定节点 取最大值  取最小值
17.5 二叉搜索树 删除指定节点(复杂)

今日作业:

1. 描述一下二叉搜索树的特点?
2. 下面的二叉搜索树在执行先序排序 后序排序 中序排序后的结果分别是?
3. 如果删除二叉搜索树中的节点需要考虑那些事项?

鱼塘是我的

• 今日作业:
  • 描述一下二叉搜索树的特点?
    具备数组索引cha询的深度与速度
    具备链表节点的宽度，同时插入删除的速度快
    二叉搜索树本身的特点为：从根节点开始，每个节点只有两个子节点，小的放左边，大的放右边
  • 下面的二叉搜索树在执行先序排序 后序排序 中序排序后的结果分别是?
    中序查找：40 53 56 60 62 63 65 71
    先序查找：60 53 40 56 63 62 65 71
    后序查找：40 56 53 62 71 65 63 60
  • 如果删除二叉搜索树中的节点需要考虑那些事项?
    • 叶子节点，直接删除
    • 删除的节点只有左节点，删除后左节点顶上来
    • 删除的节点只有右节点，删除后右节点顶上来
    • 删除的节点具有左右两个节点，右子节点下的最小节点值来替换该值，并将该最小节点用其子右节点覆盖掉

曜石头

1. 描述一下二叉搜索树的特点?
二叉搜索树每个节点都只有2个子节点，且小于节点的值在左边大于的在右边

2. 下面的二叉搜索树在执行先序排序 后序排序 中序排序后的结果分别是?  
先序排序：60        53        40        56        62        63        65        71
后序排序：40        56        53        62        71        65        63        60
中序排序：40        53        56        60        62        63        65        71

3. 如果删除二叉搜索树中的节点需要考虑那些事项?
一、删除的节点是叶子节点；直接删除就好
二、删除的节点是只有左子节点；左子节点顶上来就好
三、删除的节点是只有右子节点；右子节点顶上来就好；
四、删除的节点是有左右子节点。我们选择右子节点下的最小节点值来替换该值，并将该最小节点用其子右节点覆盖掉

本来自己想何不直接删除该节点 把剩下的 删除节点的父节点,左子节点,右子节点。当成3个有规律的二叉树拼接起来多简单，只要右子节点接上父节点，左子节点接上右子节点的最小值。可是这种方法会增加二叉树的深度，还是老师的方法好，不会增加二叉树的深度

qingshanlushui

哈哈，也就老郭敢讲这么复杂的逻辑，并且能够讲得很清晰了。。
1. 描述一下二叉搜索树的特点?
节点的左子节点的值小于该节点的值，右子节点的值大于该节点的值。细想一下根节点如果偏大或偏小这棵树就长歪了。。

2. 下面的二叉搜索树在执行先序排序 后序排序 中序排序后的结果分别是?  
先序排序：60        53        40        56        62        63        65        71
后序排序：40        56        53        62        71        65        63        60
中序排序：40        53        56        60        62        63        65        71

3. 如果删除二叉搜索树中的节点需要考虑那些事项?
一、要删除的节点是不是叶子节点；
二、如果不是，那么要删除的节点是不是只有左子节点或右子节点；
三、如果不是，那么就要进行节点替换（采用要删除的节点右子节点的最左节点  或  左子节点的最右节点）；
四、要进行替换的节点是否存在子节点（如果存在肯定只有一个）。

如果数据量较小，似乎可以按顺序遍历要删除节点之后的所有子节点。。然后全部重新插入原二叉树。。数据量太大的话，这样应该会比较耗时耗资源吧