在二叉搜索树中查找高度
我想知道是否有人可以帮助我重新设计这个方法来找到二叉搜索树的高度。到目前为止,我的代码如下所示。然而,我得到的答案比实际高度大 1。但是当我从 return 语句中删除 +1 时,它比实际高度小 1。我仍然试图用递归来解决我的问题这些二叉搜索树。任何帮助将不胜感激。
public int findHeight(){
if(this.isEmpty()){
return 0;
}
else{
TreeNode<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> aNode){
int heightLeft = 0;
int heightRight = 0;
if(aNode.left!=null)
heightLeft = findHeight(aNode.left);
if(aNode.right!=null)
heightRight = findHeight(aNode.right);
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
I was wondering if anybody could help me rework this method to find the height of a binary search tree. So far, my code looks like this. However, the answer I'm getting is larger than the actual height by 1. But when I remove the +1 from my return statements, it's less than the actual height by 1. I'm still trying to wrap my head around recursion with these BST. Any help would be much appreciated.
public int findHeight(){
if(this.isEmpty()){
return 0;
}
else{
TreeNode<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> aNode){
int heightLeft = 0;
int heightRight = 0;
if(aNode.left!=null)
heightLeft = findHeight(aNode.left);
if(aNode.right!=null)
heightRight = findHeight(aNode.right);
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(26)
问题在于你的基本情况。
“树的高度是从根到树中最深节点的路径长度。只有节点(根)的(有根)树的高度为零。” - Wikipedia
如果没有节点,您希望返回 -1 而不是 0。这是因为您末尾加 1。
因此,如果没有节点,则返回 -1,从而抵消 +1。
The problem lies in your base case.
"The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero." - Wikipedia
If there is no node, you want to return -1 not 0. This is because you are adding 1 at the end.
So if there isn't a node, you return -1 which cancels out the +1.
二叉搜索树的高度等于
层数 - 1
。请参阅 http://en.wikipedia.org/wiki/Binary_tree 上的图表,
您的递归很好,所以只需在根级别减一即可。
另请注意,您可以通过处理空节点来稍微清理该函数:
The height of a binary search tree is equal to
number of layers - 1
.See the diagram at http://en.wikipedia.org/wiki/Binary_tree
Your recursion is good, so just subtract one at the root level.
Also note, you can clean up the function a bit by handling null nodes:
在我看来,稍微简化一下您的代码将会受益。当 child 指针为 null 时,不要尝试结束递归,而是仅在 current 指针为 null 时结束递归无效的。这使得代码编写起来更加简单。在伪代码中,它看起来像这样:
In my opinion, your code would benefit from being simplified a bit. Rather than attempting to end the recursion when a child pointer is null, only end it when the current pointer is null. That makes the code a lot simpler to write. In pseudo-code, it looks something like this:
对于像我这样喜欢单线解决方案的人:
For people like me who like one line solutions:
这是一个简洁且希望正确的表达方式:
如果当前节点为空,则不存在树。如果两个孩子都是,则只有一个层,这意味着高度为 0。这使用高度的定义(由斯蒂芬提到)作为层数 - 1
Here's a concise and hopefully correct way to express it:
If the current node is null, there's no tree. If both children are, there's a single layer, which means 0 height. This uses the definition of height (mentioned by Stephen) as # of layers - 1
这未经测试,但显然是正确的:
通常简化代码比弄清楚为什么它会差一更容易。这段代码很容易理解:四种可能的情况都以明显正确的方式清楚地处理:
This is untested, but fairly obviously correct:
Often simplifying your code is easier than figuring out why it's off by one. This code is easy to understand: the four possible cases are clearly handled in an obviously correct manner:
C# 代码。
将这两个方法包含在 BST 类中。您需要两种方法来计算树的高度。 HeightHelper计算它,& HeightRecursive 在 main() 中打印它。
C# code.
Include these two methods in your BST class. you need two method to calculate height of tree. HeightHelper calculate it, & HeightRecursive print it in main().
上面给出的高度定义是不正确的。这就是深度的定义。
“树中节点M的深度是从树根到M的路径长度。树的高度比深度大一树中最深节点的所有深度为 d 的节点都位于树中的 d 层,根是唯一位于 0 层的节点,其深度为 0。 ”。
引文:“数据结构和算法分析实用介绍”
3.2版(Java版)
克利福德·谢弗
计算机科学系
弗吉尼亚理工大学
布莱克斯堡, VA 24061
The definition given above of the height is incorrect. That is the definition of the depth.
"The depth of a node M in a tree is the length of the path from the root of the tree to M. The height of a tree is one more than the depth of the deepest node in the tree. All nodes of depth d are at level d in the tree. The root is the only node at level 0, and its depth is 0."
Citation: "A Practical Introduction to Data Structures and Algorithm Analysis"
Edition 3.2 (Java Version)
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
Blacksburg, VA 24061
//求BST高度的函数
//function to find height of BST
取左右子树的最大高度并加 1。这也处理基本情况(具有 1 个节点的树的高度为 0)。
Take of maximum height from left and right subtree and add 1 to it.This also handles the base case(height of Tree with 1 node is 0).
我知道我参加聚会迟到了。在研究了这里提供的精彩答案之后,我认为我的答案将为这篇文章增加一些价值。尽管发布的答案令人惊叹且易于理解,但它们都是在线性时间内计算 BST 的高度。我认为这可以改进,并且可以在恒定时间内检索高度,因此写下这个答案 - 希望你会喜欢它。
让我们从 Node 类开始:
BinarySearchTree 类
所以您可能已经猜到了这里的技巧...我保留节点实例变量 Height 来跟踪添加的每个节点。
让我们转到 BinarySearchTree 类,它允许我们将节点添加到 BST 中:
一旦我们在 BST 中添加了键、值,我们就可以调用 RootNode 对象的 Height 属性,该属性将返回 < 中 RootNode 树的高度强>恒定时间。
诀窍是在将新节点添加到树中时保持高度更新。
希望这对计算机科学爱好者的狂野世界有所帮助!
单元测试:
注意:在每次 Put 操作中保持树的高度的想法受到《Size of BST》第 3 章(第 399 页)中的方法的启发。 算法(第四版)一本书。
I know that I’m late to the party. After looking into wonderful answers provided here, I thought mine will add some value to this post. Although the posted answers are amazing and easy to understand however, all are calculating the height to the BST in linear time. I think this can be improved and Height can be retrieved in constant time, hence writing this answer – hope you will like it.
Let’s start with the Node class:
BinarySearchTree class
So you might have guessed the trick here… Im keeping node instance variable Height to keep track of each node when added.
Lets move to the BinarySearchTree class that allows us to add nodes into our BST:
Once we have added the key, values in the BST, we can just call Height property on the RootNode object that will return us the Height of the RootNode tree in constant time.
The trick is to keep the height updated when a new node is added into the tree.
Hope this helps someone out there in the wild world of computer science enthusiast!
Unit test:
Note: This idea of keeping the Height of tree maintained in every Put operation is inspired by the Size of BST method found in the 3rd chapter (page 399) of Algorithm (Fourth Edition) book.
我想这个问题可能意味着两个不同的事情......
高度是最长分支中的节点数:-
int calcHeight(节点*根){
如果(根==NULL)
返回0;
int l=calcHeight(root->left);
int r=calcHeight(根->右);
如果(l>r)
返回l+1;
别的
返回r+1;
}
高度是树本身节点总数:
int calcSize(节点*根){
如果(根==NULL)
返回0;
return(calcSize(根->左)+1+calcSize(根->右));
}
I guess this question could mean two different things...
Height is the number of nodes in the longest branch:-
int calcHeight(node* root){
if(root==NULL)
return 0;
int l=calcHeight(root->left);
int r=calcHeight(root->right);
if(l>r)
return l+1;
else
return r+1;
}
Height is the total number of nodes in the tree itself:
int calcSize(node* root){
if(root==NULL)
return 0;
return(calcSize(root->left)+1+calcSize(root->right));
}
将 tempHeight 设置为静态变量(初始为 0)。
静态无效findHeight(节点节点,int计数){
Set a tempHeight as a static variable(initially 0).
static void findHeight(Node node, int count) {
这是 Java 中的一个解决方案,虽然有点长,但很有效。
Here is a solution in Java a bit lengthy but works..
这是 C# 中的解决方案
Here is a solution in C#
二叉树的高度
Height of Binary Tree
对于其他读到此内容的人!!!!
HEIGHT 定义为从根节点到叶节点的最长路径中的节点数。因此:只有根节点的树的高度为 1 而不是 0。
给定节点的 LEVEL 是距根的距离加 1。因此:根位于第 1 层,其子节点位于第 2 层,并且很快。
(信息由《数据结构:使用 Java 进行抽象和设计》第二版提供,作者:Elliot B. Koffman 和 Paul AT Wolfgang)- 我目前在哥伦布州立大学学习的数据结构课程中使用的书籍。
For anyone else that reads this!!!!
HEIGHT is defined as the number of nodes in the longest path from the root node to a leaf node. Therefore: a tree with only a root node has a height of 1 and not 0.
The LEVEL of a given node is the distance from the root plus 1. Therefore: The root is on level 1, its child nodes are on level 2 and so on.
(Information courtesy of Data Structures: Abstraction and Design Using Java, 2nd Edition, by Elliot B. Koffman & Paul A. T. Wolfgang) - Book used in Data Structures Course I am currently taking at Columbus State University.
在此处输入图像描述
根据 Thomas H. Cormen、Charles E. 的“算法简介” Leiserson、Ronald L. Rivest 和 Clifford Stein 给出了树高的定义:
以下是我的红宝石解决方案。大多数人在实现中忘记了空树或单节点树的高度。
enter image description here
According to "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, following is the definition of tree height:
Following is my ruby solution. Most of the people forgot about height of empty tree or tree of single node in their implementation.
我自己也在努力解决这个问题,试图找到一些优雅的东西,但仍然能产生正确的值。这是我使用 Swift 的想法。请注意,
height
是一个计算变量,从技术上讲不是一个函数。这个 Node 定义还有更多内容,但您可以看到
left
和right
变量(可能为零)以及isLeaf
vartrue
当left
和right
均为nil
时。可能不是最有效的,但我相信它会产生正确的结果。BST 定义还有一个计算的高度变量,当树为空时返回 -1。
I struggled with this myself trying to find something elegant that still resulted in the correct value. Here's what I came up with using Swift. Note that
height
is a computed variable and technically not a function.There's more to this Node definition but you can see the
left
andright
variables (possibly nil) and anisLeaf
var that istrue
when bothleft
andright
arenil
. Might not be the most efficient but I believe it yields the correct result.The BST definition also has a computed
height
variable and returns -1 when the tree is empty.