24 | 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？

精选留言(142)

• 

  失火的夏天

  确定二叉树高度有两种思路：第一种是深度优先思想的递归，分别求左右子树的高度。当前节点的高度就是左右子树中较大的那个+1；第二种可以采用层次遍历的方式，每一层记录都记录下当前队列的长度，这个是队尾，每一层队头从0开始。然后每遍历一个元素，队头下标+1。直到队头下标等于队尾下标。这个时候表示当前层遍历完成。每一层刚开始遍历的时候，树的高度+1。最后队列为空，就能得到树的高度。

  作者回复: 👍 大家可以看看这条留言

  2018-11-14

   14

   241
• 

  拉欧

  递归法，根节点高度=max(左子树高度，右子树高度)+1

  作者回复: 👍 精髓

  2018-11-14

  

   101
• 

  Smallfly

  老师我有一个疑问，二叉树删除时，如果待删除节点有两个子节点，能否用左子树中的最大值来替换待删除节点呢？

  作者回复: 好像也可以 👍

  2018-11-15

   7

   57
• 

  Monday

  1、思考题：leetcode 104 题，可以使用递归法。
  递归公式： depth =Math.max(maxDepth(node.left), maxDepth(node.right) )+ 1;
  递归出口： depth = 0 (node == null)
  2、二叉查找树的删除操作（无重复的数据）leetcode 450。
  根据老师的思路，先不看代码，自己写了好长段时间，写出来都跑过leetcode的所有案例。回过头来再看老师的删除的代码，感觉到了巧妙之处就是：当删除节点有两个子节点的情况，很巧得一起套用了删除结点子节点个数小于1的两种场景。

  作者回复: 是的 钻研精神值得称赞👍

  2018-11-17

   1

   48
• 

  一般社员

  老师，不理解删除有两个子节点那段代码，最后删除minp，不是minpp.left =null,minp =null吗

  2018-11-14

   5

   40
• 

  🌟

  姜威老大没写总结笔记了吗？我是个算法菜鸟萌新，一直看着姜大佬的笔记总结学习。。。

  2018-11-26

  

   24
• 

  www.xnsms.com小鸟接码

  p.data = minP.data; // 将 minP 的数据替换到 p 中
  p = minP; // 下面就变成了删除 minP 了
  pp = minPP;
  
  
  总于看明白这段代码了……各位老铁，单纯看这3行代码是看不出是删除后继节点的，是要结合后面的代码来看的……不过说实话这种代码是不好看的懂……

  作者回复: 😄 是不好看懂

  2018-11-15

   1

   15
• 

  莫弹弹

  在sf的微信公众号上刚好看到二叉树相关的文章，二叉树常规操作都有了，基本思路是：
  
  - 只有一个根结点时，二叉树深度为 1
  - 只有左子树时，二叉树深度为左子树深度加 1
  - 只有右子树时，二叉树深度为右子树深度加 1
  - 同时存在左右子树时，二叉树深度为左右子树中深度最大者加 1
  
  https://mp.weixin.qq.com/s/ONKJyusGCIE2ctwT9uLv9g

  作者回复: 👍

  2018-11-14

  

   10
• 

  一个慢慢爬行的普通人

  p = minP; // 下面就变成了删除 minP 了...
  pp = minPP;
  老师，对这里不太搞懂，似乎也有些人对这里感到困惑，老师可以对这两句集中解释下嘛

  作者回复: 好的。我们用后继节点替换到要删除节点的位置。 然后就变成删除后继节点的问题了。为了逻辑统一 代码书写简洁。我们把后继节点赋给了p

  2018-11-14

  

   9
• 

  Ryan-Hou

  平衡树相比于哈希表，保存了节点数据间的顺序信息，所以操作的时间复杂度上会比哈希表大(因为额外的提供了顺序性，对应的会有代价)。也正因为保存了顺序性，平衡树可以方便的实现min, max, ceil, floor 等操作，所以个人认为这两种数据结构最大的不同在于这里，有不同的取舍

  2018-11-14

  

   8
• 

  allean

  连续看好几遍，每一次的感受都更深刻，谢谢老师。可是有一点要吐槽下，老师给变量命名也有点太随意了啊，二叉树删除节点那个，好多p啊，看的晕了都

  2019-01-14

  

   7
• 

  追风者

  更新二十多篇了，王老师把前面文章的课后思考题都总结回答一下吧。

  作者回复: 好的 基础篇完了后会集中答疑一下

  2018-11-15

  

   7
• 

  李沁

  这两句代码一开始看得很晕
  p = minP; // 下面就变成了删除 minP 了
  pp = minPP;
  
  后面想到其实代码还没有终结，如果minP是右子树的最左节点，那么这个节点肯定是没有左子树的。
  这步操作其实可以理解为把这个节点标记要删除，用后面的删除只有一个子树或没有子树的节点的逻辑去做

  2019-05-01

  

   6
• 

  李建辉

  看了下老师显示的代码，发现老师的删除二叉查找树节点的代码写的有点问题，为此自己实现了一下，希望老师指正：
  先说老师代码问题所在：
      p.data = minP.data; // 将 minP 的数据替换到 p 中
      p = minP; // 下面就变成了删除 minP 了
      pp = minPP;
  这里是有问题的，感觉正确的应该是
  findNode.setData(minP.getData());//覆盖原来的值
  minPP.setLeftNode(minP.getRightNode());//替代删除节点的父节点的左节点指向替代删除节点的右节点
  
  贴上自己的删除代码：
  /**
  * 删除查找二叉树的一个节点
  * @param root
  * @param value
  */
  public static void delete(Node root,int value) {
  Node findNode = root; //记录当前要删除的节点
  Node fatherNode = null; //记录删除节点的父节点
  while (findNode != null && findNode.getData() != value) {
  fatherNode = findNode;
  if (findNode.getData() < value) {
  findNode = findNode.getRightNode();
  } else if (findNode.getData() > value) {
  findNode = findNode.getLeftNode();
  }
  }
  if (findNode != null) {
  if (findNode.getLeftNode() != null && findNode.getRightNode() != null) {//要删除节点 左节点和右节点都存在
  Node minP = findNode.getRightNode(); //minP是获取右节点下面的最小节点
  Node minPP = findNode; //minPP是minP的父节点
  while (minP.getLeftNode() != null) {
  minPP = minP;
  minP = minP.getLeftNode();
  }
  findNode.setData(minP.getData());//覆盖原来的值
  minPP.setLeftNode(minP.getRightNode());//替代删除节点的父节点的左节点指向替代删除节点的右节点
  }else{//要删除节点 左节点和右节点有一个存在 或全部都不存在
  Node tidai = null;
  if (findNode.getLeftNode() == null && findNode.getRightNode() != null) {
  tidai = findNode.getRightNode();
  }
  if (findNode.getLeftNode() != null && findNode.getRightNode() == null) {
  tidai = findNode.getLeftNode();
  }
  if (fatherNode == null) { //父节点为空 即为根节点
  root = tidai;
  } else if (fatherNode.getRightNode().getData() == value) {
  fatherNode.setRightNode(tidai);
  } else {
  fatherNode.setLeftNode(tidai);
  }
  }
  }
  
  }
  

  2018-11-15

  

   5
• 

  陆老师

  有一种更容易理解复杂度的思路，二叉查找树类似二分法搜索，每次缩小一半的区间，而二分查找法时间复杂度就是logN

  作者回复: 是的，👍

  2019-03-13

   1

   4
• 

  humor

  装载因子太大，不是浪费空间，而是节省空间吧？

  2018-12-28

  

   4
• 

  kakasi

  老师，看了二叉树的优点和适用场景，跳表不是都满足吗？

  2018-11-28

  

   4
• 

  james

  散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费内存空间。
  修改：应该是装在因子不能太小吧

  2018-11-22

   1

   4
• 

  等风来

  老师:删除示例的25节点的右节点[21]错误;
  删除节点有两个节点
  p = minP; // 下面就变成了删除 minP 了...
  pp = minPP;
  是不是应该改成: minPP.Left = minP.Right;

  作者回复: 图已经改正 多谢指出。
  代码应该没错

  2018-11-14

  

   4
• 

  PhilZhang

  对于二叉搜索树各种操作的复杂度，有更容易理解的解释方法:每次操作后数据量都减少了一半，所以复杂度自然是logN。

  作者回复: 👍

  2018-11-18

  

   3