计算二叉搜索树的深度？

5 回答

• 2

  您只需在遍历树时保留深度计数器（如果必须，查找树遍历）并在每次到达节点时添加计数器的值 . 然后除以节点数 .

  这看起来像家庭作业所以我没有提供更详细的解决方案 .

  回复于 2024-05-04T20:20:43+08:00
• 0

  如果我在一张纸上向你展示了一张BST的照片，想一想如何用手来规范 . 当您在某个节点时，您需要跟踪哪些信息？如何找到给定节点的高度？

  从这里开始，尝试将其转换为伪代码甚至直接转换为Java . 如果您遇到问题，请随时发表评论，以便用户可以帮助您 .

  回复于 2024-05-04T20:20:43+08:00
• 0

  这是家庭作业吗？如果是这样就标记问题 .

  您可以创建一个方法：

  • 有一个节点引用和一个深度作为参数

  • 增量深度

  • 如果节点不是左右递归子节点调用，则相应地更新和

  • 否则返回总和深度

  一旦你通过树中的孩子数量来获得平均深度 .

  回复于 2024-05-04T20:20:43+08:00
• 0

  我们需要访问所有叶节点并确定它们的深度 . 这表明：

  为您的节点访问函数提供额外的参数 . 它不仅要知道它的发展方向，还要知道它的深度 . 每次调用它时，它都会被调深，因此您的节点访问者只需增加从调用者那里获得的深度数 .

  现在可以发生两件事之一：

  • 您找到的节点是叶节点，即它没有任何子节点;在这种情况下，您的访问者需要将其深度返回给调用者 . 是的，它只返回从调用者那里获得的数字，1 .

  • 或它不是叶子节点 . 在这种情况下，它将有1或2个孩子 . 我们需要从我们的孩子那里得到那些深度报告回到呼叫者，所以只需返回孩子们返回的深度总和 .

  通过递归的魔力，返回根访问者的数字将是所有孩子的深度之和 .

  要获得平均深度，您需要将其除以叶节点的数量;我将留下第二次遍历来计算 . 它可以在一个完成，但它会更复杂一点 .

  回复于 2024-05-04T20:20:43+08:00
• 4

  由于这是家庭作业，我不想只给你一个答案 . 相反，这是一种计算单链表长度的递归方法 . 希望这将以您能理解的方式演示递归，并且您可以从那里推断出来解决您的BST问题 .

  public final class LL {
      public final int value;
      public LL next;
  
      public LL(final int value) {
          this.value = value;
      }
  
      public void add(final int value) {
          if (null == next) {
              next = new LL(value);
          } else {
              next.add(value);
          }
      }
  
      /**
       * Calculate the length of the linked list with this node as its head (includes this node in the count).
       *
       * @return the length.
       */
      public int length() {
          if (null == next) {
              return 1;
          }
          return 1 + next.length();
      }
  
      public static void main(final String... args) {
          final LL head = new LL(1);
          head.add(2);
          head.add(3);
          System.out.println(head.length());
          System.out.println(head.next.length());
      }
  }
  

  回复于 2024-05-04T20:20:43+08:00