如何计算二叉搜索树的深度 [英] How to calculate the depth of a binary search tree

问题描述

我想计算二元搜索树每个节点深度的总和。

I would like to calculate the summation of the depths of each node of a Binary Search Tree.

元素的各个深度尚未存储。

The individual depths of the elements are not already stored.

推荐答案

这样的事情：

int countChildren(Node node)
{
    if ( node == null )
        return 0;
    return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}

并获得每个孩子的深度总和：

And to get the sum of the depths of every child:

int sumDepthOfAllChildren(Node node, int depth)
{
    if ( node == null )
        return 0;  // starting to see a pattern?
    return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + 
                   sumDepthOfAllChildren(node.getRight(), depth + 1);
}

现在有一个有希望提供信息的解释，以防这是家庭作业。计算节点数非常简单。首先，如果节点不是节点（ node == null ），则返回0.如果是节点，则首先计算其自身（ 1 ），加上左子树中的节点数加上右子树中的节点数。另一种思考方式是通过BFS访问每个节点，并为您访问的每个节点添加一个计数。

Now for a hopefully informative explanation in case this is homework. Counting the number of nodes is quite simple. First of all, if the node isn't a node (node == null) it returns 0. If it is a node, it first counts its self (the 1), plus the number of nodes in its left sub-tree plus the number of nodes in its right sub-tree. Another way to think of it is you visit every node via BFS, and add one to the count for every node you visit.

深度的总和是相似的，除了相反为每个节点添加一个节点，该节点添加其自身的深度。它知道自己的深度，因为它的父母告诉它。每个节点都知道它的子节点的深度是它自己的深度加一，所以当你得到一个节点的左右子节点的深度时，你告诉它们它们的深度是当前节点的深度加1.

The Summation of depths is similar, except instead of adding just one for each node, the node adds the depth of its self. And it knows the depth of its self because its parent told it. Each node knows that the depth of it's children are it's own depth plus one, so when you get the depth of the left and right children of a node, you tell them their depth is the current node's depth plus 1.

同样，如果节点不是节点，则它没有深度。因此，如果您想要所有根节点的子节点的深度总和，则传入根节点和根节点的深度，如下所示： sumDepthOfAllChildren（root，0）

And again, if the node isn't a node, it has no depth. So if you want the sum of the depth of all the root node's children, you pass in the root node and the root node's depth like so: sumDepthOfAllChildren(root, 0)

递归是非常有用的，它只是一种非常不同的思考方式，需要习惯才能习惯它

Recursion is quite useful, it's just a very different way of thinking about things and takes practice to get accustomed to it

这篇关于如何计算二叉搜索树的深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！