在二叉搜索树中查找高度

发布于 2024-08-28 01:53:15 字数 690 浏览 9 评论 0原文

我想知道是否有人可以帮助我重新设计这个方法来找到二叉搜索树的高度。到目前为止,我的代码如下所示。然而,我得到的答案比实际高度大 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(26

戒ㄋ 2024-09-04 01:53:15

问题在于你的基本情况。

“树的高度是从根到树中最深节点的路径长度。只有节点(根)的(有根)树的高度为零。” - Wikipedia

如果没有节点,您希望返回 -1 而不是 0。这是因为您末尾加 1。

因此,如果没有节点,则返回 -1,从而抵消 +1。

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 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.

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}
蓝天白云 2024-09-04 01:53:15

二叉搜索树的高度等于层数 - 1

请参阅 http://en.wikipedia.org/wiki/Binary_tree 上的图表,

您的递归很好,所以只需在根级别减一即可。

另请注意,您可以通过处理空节点来稍微清理该函数:

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}

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:

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}
烙印 2024-09-04 01:53:15
int getHeight(Node node) {
 if (node == null) return -1;

 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
int getHeight(Node node) {
 if (node == null) return -1;

 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
安人多梦 2024-09-04 01:53:15

在我看来,稍微简化一下您的代码将会受益。当 child 指针为 null 时,不要尝试结束递归,而是仅在 current 指针为 null 时结束递归无效的。这使得代码编写起来更加简单。在伪代码中,它看起来像这样:

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

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:

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);
ぃ双果 2024-09-04 01:53:15
class Solution{
    public static int getHeight(Node root) {
        int height = -1;

        if (root == null) {
            return height;
        } else {
            height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }

        return height;
    }
class Solution{
    public static int getHeight(Node root) {
        int height = -1;

        if (root == null) {
            return height;
        } else {
            height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }

        return height;
    }
乙白 2024-09-04 01:53:15

对于像我这样喜欢单线解决方案的人:

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}

For people like me who like one line solutions:

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}
我很OK 2024-09-04 01:53:15

这是一个简洁且希望正确的表达方式:

  private int findHeight(TreeNode<T> aNode){
    if(aNode == null || (aNode.left == null && aNode.right == null))
      return 0;
    return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
  }

如果当前节点为空,则不存在树。如果两个孩子都是,则只有一个层,这意味着高度为 0。这使用高度的定义(由斯蒂芬提到)作为层数 - 1

Here's a concise and hopefully correct way to express it:

  private int findHeight(TreeNode<T> aNode){
    if(aNode == null || (aNode.left == null && aNode.right == null))
      return 0;
    return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
  }

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

牵你的手,一向走下去 2024-09-04 01:53:15

这未经测试,但显然是正确的:

private int findHeight(Treenode<T> aNode) {
  if (aNode.left == null && aNode.right == null) {
    return 0; // was 1; apparently a node with no children has a height of 0.
  } else if (aNode.left == null) {
    return 1 + findHeight(aNode.right);
  } else if (aNode.right == null) {
    return 1 + findHeight(aNode.left);
  } else {
    return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
  }
}

通常简化代码比弄清楚为什么它会差一更容易。这段代码很容易理解:四种可能的情况都以明显正确的方式清楚地处理:

  • 如果左树和右树都为空,则返回 0,因为根据定义单个节点的高度为 0。(为 1)
  • 如果左树或右树(但不是两者!)都为空,返回非空树的高度,加上 1 以说明当前节点的添加高度。
  • 如果两棵树都不为空,则返回较高子树的高度,并为当前节点再次加一。

This is untested, but fairly obviously correct:

private int findHeight(Treenode<T> aNode) {
  if (aNode.left == null && aNode.right == null) {
    return 0; // was 1; apparently a node with no children has a height of 0.
  } else if (aNode.left == null) {
    return 1 + findHeight(aNode.right);
  } else if (aNode.right == null) {
    return 1 + findHeight(aNode.left);
  } else {
    return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
  }
}

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:

  • If both the left and right trees are null, return 0, since a single node by definition has a height of 0. (was 1)
  • If either the left or right trees (but not both!) are null, return the height of the non-null tree, plus 1 to account for the added height of the current node.
  • If neither tree is null, return the height of the taller subtree, again plus one for the current node.
多彩岁月 2024-09-04 01:53:15
    public void HeightRecursive()
    {
        Console.WriteLine( HeightHelper(root) ); 
    }

    private int HeightHelper(TreeNode node)
    {
        if (node == null)
        {
            return -1;
        }
        else
        {
            return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));           
        }
    }

C# 代码。
将这两个方法包含在 BST 类中。您需要两种方法来计算树的高度。 HeightHelper计算它,& HeightRecursive 在 main() 中打印它。

    public void HeightRecursive()
    {
        Console.WriteLine( HeightHelper(root) ); 
    }

    private int HeightHelper(TreeNode node)
    {
        if (node == null)
        {
            return -1;
        }
        else
        {
            return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));           
        }
    }

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().

梦境 2024-09-04 01:53:15

上面给出的高度定义是不正确的。这就是深度的定义。

“树中节点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

桜花祭 2024-09-04 01:53:15
public int height(){

    if(this.root== null) return 0;

    int leftDepth = nodeDepth(this.root.left, 1);
    int rightDepth = nodeDepth(this.root.right, 1);

    int height = leftDepth > rightDepth? leftDepth: rightDepth;

    return height;
}


private int nodeDepth(Node node, int startValue){

    int nodeDepth = 0;

    if(node.left == null && node.right == null) return startValue;
    else{
        startValue++;
        if(node.left!= null){
            nodeDepth = nodeDepth(node.left, startValue);
        }

        if(node.right!= null){
            nodeDepth = nodeDepth(node.right, startValue);
        }
    }

    return nodeDepth;
}
public int height(){

    if(this.root== null) return 0;

    int leftDepth = nodeDepth(this.root.left, 1);
    int rightDepth = nodeDepth(this.root.right, 1);

    int height = leftDepth > rightDepth? leftDepth: rightDepth;

    return height;
}


private int nodeDepth(Node node, int startValue){

    int nodeDepth = 0;

    if(node.left == null && node.right == null) return startValue;
    else{
        startValue++;
        if(node.left!= null){
            nodeDepth = nodeDepth(node.left, startValue);
        }

        if(node.right!= null){
            nodeDepth = nodeDepth(node.right, startValue);
        }
    }

    return nodeDepth;
}
∞琼窗梦回ˉ 2024-09-04 01:53:15

//求BST高度的函数

int height(Node* root) {
    if(root == NULL){
        return -1;
    }

    int sum=0;
    int rheight = height(root->right);
    int lheight = height(root->left);

    if(lheight>rheight){
        sum = lheight +1;
    }
    if(rheight > lheight){
        sum = rheight + 1;
    }

    return sum;
}

//function to find height of BST

int height(Node* root) {
    if(root == NULL){
        return -1;
    }

    int sum=0;
    int rheight = height(root->right);
    int lheight = height(root->left);

    if(lheight>rheight){
        sum = lheight +1;
    }
    if(rheight > lheight){
        sum = rheight + 1;
    }

    return sum;
}
难理解 2024-09-04 01:53:15
int height(Node* root) {
        if(root==NULL) return -1;
        return max(height(root->left),height(root->right))+1;
}

取左右子树的最大高度并加 1。这也处理基本情况(具有 1 个节点的树的高度为 0)。

int height(Node* root) {
        if(root==NULL) return -1;
        return max(height(root->left),height(root->right))+1;
}

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).

如梦亦如幻 2024-09-04 01:53:15

我知道我参加聚会迟到了。在研究了这里提供的精彩答案之后,我认为我的答案将为这篇文章增加一些价值。尽管发布的答案令人惊叹且易于理解,但它们都是在线性时间内计算 BST 的高度。我认为这可以改进,并且可以在恒定时间内检索高度,因此写下这个答案 - 希望你会喜欢它。
让我们从 Node 类开始:

public class Node
{
    public Node(string key)
    {
        Key = key;
        Height = 1;
    }    

    public int Height { get; set; } 
    public string Key { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    public override string ToString()
    {
        return $"{Key}";
    }
}

BinarySearchTree

所以您可能已经猜到了这里的技巧...我保留节点实例变量 Height 来跟踪添加的每个节点。
让我们转到 BinarySearchTree 类,它允许我们将节点添加到 BST 中:

public class BinarySearchTree
{
    public Node RootNode { get; private set; }

    public void Put(string key)
    {
        if (ContainsKey(key))
        {
            return;
        }

        RootNode = Put(RootNode, key);
    }

    private Node Put(Node node, string key)
    {
        if (node == null) return new Node(key);

        if (node.Key.CompareTo(key) < 0)
        {
            node.Right = Put(node.Right, key);
        }
        else
        {
            node.Left = Put(node.Left, key);
        }       
        
        // since each node has height property that is maintained through this Put method that creates the binary search tree.
        // calculate the height of this node by getting the max height of its left or right subtree and adding 1 to it.        
        node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
        return node;
    }

    private int GetHeight(Node node)
    {
        return node?.Height ?? 0;
    }

    public Node Get(Node node, string key)
    {
        if (node == null) return null;
        if (node.Key == key) return node;

        if (node.Key.CompareTo(key) < 0)
        {
            // node.Key = M, key = P which results in -1
            return Get(node.Right, key);
        }

        return Get(node.Left, key);
    }

    public bool ContainsKey(string key)
    {
        Node node = Get(RootNode, key);
        return node != null;
    }
}

一旦我们在 BST 中添加了键、值,我们就可以调用 RootNode 对象的 Height 属性,该属性将返回 < 中 RootNode 树的高度强>恒定时间。
诀窍是在将新节点添加到树中时保持高度更新。
希望这对计算机科学爱好者的狂野世界有所帮助!

单元测试:

[TestCase("SEARCHEXAMPLE", 6)]
[TestCase("SEBAQRCHGEXAMPLE", 6)]
[TestCase("STUVWXYZEBAQRCHGEXAMPLE", 8)]
public void HeightTest(string data, int expectedHeight)
{
    // Arrange.
    var runner = GetRootNode(data);

    
    //  Assert.
    Assert.AreEqual(expectedHeight, runner.RootNode.Height);
}

private BinarySearchTree GetRootNode(string data)
{
    var runner = new BinarySearchTree();
    foreach (char nextKey in data)
    {
        runner.Put(nextKey.ToString());
    }

    return runner;
}

注意:在每次 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:

public class Node
{
    public Node(string key)
    {
        Key = key;
        Height = 1;
    }    

    public int Height { get; set; } 
    public string Key { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    public override string ToString()
    {
        return 
quot;{Key}";
    }
}

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:

public class BinarySearchTree
{
    public Node RootNode { get; private set; }

    public void Put(string key)
    {
        if (ContainsKey(key))
        {
            return;
        }

        RootNode = Put(RootNode, key);
    }

    private Node Put(Node node, string key)
    {
        if (node == null) return new Node(key);

        if (node.Key.CompareTo(key) < 0)
        {
            node.Right = Put(node.Right, key);
        }
        else
        {
            node.Left = Put(node.Left, key);
        }       
        
        // since each node has height property that is maintained through this Put method that creates the binary search tree.
        // calculate the height of this node by getting the max height of its left or right subtree and adding 1 to it.        
        node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
        return node;
    }

    private int GetHeight(Node node)
    {
        return node?.Height ?? 0;
    }

    public Node Get(Node node, string key)
    {
        if (node == null) return null;
        if (node.Key == key) return node;

        if (node.Key.CompareTo(key) < 0)
        {
            // node.Key = M, key = P which results in -1
            return Get(node.Right, key);
        }

        return Get(node.Left, key);
    }

    public bool ContainsKey(string key)
    {
        Node node = Get(RootNode, key);
        return node != null;
    }
}

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:

[TestCase("SEARCHEXAMPLE", 6)]
[TestCase("SEBAQRCHGEXAMPLE", 6)]
[TestCase("STUVWXYZEBAQRCHGEXAMPLE", 8)]
public void HeightTest(string data, int expectedHeight)
{
    // Arrange.
    var runner = GetRootNode(data);

    
    //  Assert.
    Assert.AreEqual(expectedHeight, runner.RootNode.Height);
}

private BinarySearchTree GetRootNode(string data)
{
    var runner = new BinarySearchTree();
    foreach (char nextKey in data)
    {
        runner.Put(nextKey.ToString());
    }

    return runner;
}

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.

小红帽 2024-09-04 01:53:15

我想这个问题可能意味着两个不同的事情......

  1. 高度是最长分支中的节点数:-

    int calcHeight(节点*根){
    如果(根==NULL)
    返回0;
    int l=calcHeight(root->left);
    int r=calcHeight(根->右);
    如果(l>r)
    返回l+1;
    别的
    返回r+1;
    }

  2. 高度是树本身节点总数

    int calcSize(节点*根){
    如果(根==NULL)
    返回0;
    return(calcSize(根->左)+1+calcSize(根->右));
    }

I guess this question could mean two different things...

  1. 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;
    }

  2. 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));
    }

筱武穆 2024-09-04 01:53:15
public int getHeight(Node node)
{
    if(node == null)
        return 0;

    int left_val = getHeight(node.left);
    int right_val = getHeight(node.right);
    if(left_val > right_val)
        return left_val+1;
    else
        return right_val+1;
}
public int getHeight(Node node)
{
    if(node == null)
        return 0;

    int left_val = getHeight(node.left);
    int right_val = getHeight(node.right);
    if(left_val > right_val)
        return left_val+1;
    else
        return right_val+1;
}
可爱咩 2024-09-04 01:53:15

将 tempHeight 设置为静态变量(初始为 0)。

静态无效findHeight(节点节点,int计数){

    if (node == null) {
        return;
    }
    if ((node.right == null) && (node.left == null)) {
        if (tempHeight < count) {
            tempHeight = count;

        }

    }

    findHeight(node.left, ++count);
    count--; //reduce the height while traversing to a different branch
    findHeight(node.right, ++count);

}

Set a tempHeight as a static variable(initially 0).

static void findHeight(Node node, int count) {

    if (node == null) {
        return;
    }
    if ((node.right == null) && (node.left == null)) {
        if (tempHeight < count) {
            tempHeight = count;

        }

    }

    findHeight(node.left, ++count);
    count--; //reduce the height while traversing to a different branch
    findHeight(node.right, ++count);

}
瑶笙 2024-09-04 01:53:15

这是 Java 中的一个解决方案,虽然有点长,但很有效。

public static int getHeight (Node root){
    int lheight = 0, rheight = 0;
    if(root==null) {
        return 0;
    }
    else {
        if(root.left != null) {
            lheight = 1 + getHeight(root.left);
            System.out.println("lheight" + " " + lheight);
        }
        if (root.right != null) {
            rheight = 1+ getHeight(root.right);
            System.out.println("rheight" + " " + rheight);
        }
        if(root != null && root.left == null && root.right == null) {
            lheight += 1; 
            rheight += 1;
        }

    }
    return Math.max(lheight, rheight);
    }

Here is a solution in Java a bit lengthy but works..

public static int getHeight (Node root){
    int lheight = 0, rheight = 0;
    if(root==null) {
        return 0;
    }
    else {
        if(root.left != null) {
            lheight = 1 + getHeight(root.left);
            System.out.println("lheight" + " " + lheight);
        }
        if (root.right != null) {
            rheight = 1+ getHeight(root.right);
            System.out.println("rheight" + " " + rheight);
        }
        if(root != null && root.left == null && root.right == null) {
            lheight += 1; 
            rheight += 1;
        }

    }
    return Math.max(lheight, rheight);
    }
落在眉间の轻吻 2024-09-04 01:53:15
 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }
 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }
仙女 2024-09-04 01:53:15

这是 C# 中的解决方案

    private static int heightOfTree(Node root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = 1 + heightOfTree(root.left);
        int right = 1 + heightOfTree(root.right);

        return Math.Max(left, right);
    }

Here is a solution in C#

    private static int heightOfTree(Node root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = 1 + heightOfTree(root.left);
        int right = 1 + heightOfTree(root.right);

        return Math.Max(left, right);
    }
嘿哥们儿 2024-09-04 01:53:15

二叉树的高度

public static int height(Node root)
    {
        // Base case: empty tree has height 0
        if (root == null) {
            return 0;
        }

        // recursively for left and right subtree and consider maximum depth
        return 1 + Math.max(height(root.left), height(root.right));
    }

Height of Binary Tree

public static int height(Node root)
    {
        // Base case: empty tree has height 0
        if (root == null) {
            return 0;
        }

        // recursively for left and right subtree and consider maximum depth
        return 1 + Math.max(height(root.left), height(root.right));
    }
め七分饶幸 2024-09-04 01:53:15

对于其他读到此内容的人!!!!

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.

淡忘如思 2024-09-04 01:53:15

在此处输入图像描述

根据 Thomas H. Cormen、Charles E. 的“算法简介” Leiserson、Ronald L. Rivest 和 Clifford Stein 给出了树高的定义:

a中节点的高度
树是从节点到节点的最长简单向下路径上的边数
一片叶子,一棵树的高度就是它的根的高度。树的高度也是
等于树中任何节点的最大深度。

以下是我的红宝石解决方案。大多数人在实现中忘记了空树或单节点树的高度。

def height(node, current_height)
  return current_height if node.nil? || (node.left.nil? && node.right.nil?)
  return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
  return height(node.left, current_height + 1) if node.left
  return height(node.right, current_height + 1)
end

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:

The height of a node in a
tree is the number of edges on the longest simple downward path from the node to
a leaf, and the height of a tree is the height of its root. The height of a tree is also
equal to the largest depth of any node in the tree.

Following is my ruby solution. Most of the people forgot about height of empty tree or tree of single node in their implementation.

def height(node, current_height)
  return current_height if node.nil? || (node.left.nil? && node.right.nil?)
  return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
  return height(node.left, current_height + 1) if node.left
  return height(node.right, current_height + 1)
end
零崎曲识 2024-09-04 01:53:15
int maxDepth(BinaryTreeNode root) {
    if(root == null || (root.left == null && root.right == null)) {
       return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
int maxDepth(BinaryTreeNode root) {
    if(root == null || (root.left == null && root.right == null)) {
       return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
悟红尘 2024-09-04 01:53:15

我自己也在努力解决这个问题,试图找到一些优雅的东西,但仍然能产生正确的值。这是我使用 Swift 的想法。请注意,height 是一个计算变量,从技术上讲不是一个函数。

class Node<T: Comparable>: NSObject
{
    var left: Node<T>? = nil
    var right: Node<T>? = nil
 
    var isLeaf: Bool { left == nil && right == nil }

    var height: Int {
        if isLeaf { return 0 }
        return 1 + max(left?.height ?? 0, right?.height ?? 0)
    }
}

这个 Node 定义还有更多内容,但您可以看到 leftright 变量(可能为零)以及 isLeaf var trueleftright 均为 nil 时。可能不是最有效的,但我相信它会产生正确的结果。

BST 定义还有一个计算的高度变量,当树为空时返回 -1。

class BST<T: Comparable>: NSObject
{
    var root: Node<T>?
    var height: Int { root != nil ? root!.height : -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.

class Node<T: Comparable>: NSObject
{
    var left: Node<T>? = nil
    var right: Node<T>? = nil
 
    var isLeaf: Bool { left == nil && right == nil }

    var height: Int {
        if isLeaf { return 0 }
        return 1 + max(left?.height ?? 0, right?.height ?? 0)
    }
}

There's more to this Node definition but you can see the left and right variables (possibly nil) and an isLeaf var that is true when both left and right are nil. 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.

class BST<T: Comparable>: NSObject
{
    var root: Node<T>?
    var height: Int { root != nil ? root!.height : -1 }
}
独享拥抱 2024-09-04 01:53:15
HackerRank Day 22: Finding height in Binary Search Tree, in C#.

     static int getHeight(Node root)
        {
            //Write your code here
            int countr = 0,countl=0;
            Node Leftsubtree=root.left;
            Node rightsubtree = root.right;
            int data=root.data;
             if(root==null ||(root.left == null && root.right == null))
            {
                return 0;
            }
             else
            {
                while (Leftsubtree != null)
                {
                        if(Leftsubtree.data<data)
                        {
                        Leftsubtree = Leftsubtree.left==null?Leftsubtree.right:Leftsubtree.left;
                        countl++;
                        }
                }
                while (rightsubtree != null)
                {
                    if (rightsubtree.data > data)
                    {
                        rightsubtree = rightsubtree.right == null ? rightsubtree.left : rightsubtree.right;
                        countr++;
                    }
    
                }
            }
    
            return countr >= countl ? countr : countl;
    
    
        }
HackerRank Day 22: Finding height in Binary Search Tree, in C#.

     static int getHeight(Node root)
        {
            //Write your code here
            int countr = 0,countl=0;
            Node Leftsubtree=root.left;
            Node rightsubtree = root.right;
            int data=root.data;
             if(root==null ||(root.left == null && root.right == null))
            {
                return 0;
            }
             else
            {
                while (Leftsubtree != null)
                {
                        if(Leftsubtree.data<data)
                        {
                        Leftsubtree = Leftsubtree.left==null?Leftsubtree.right:Leftsubtree.left;
                        countl++;
                        }
                }
                while (rightsubtree != null)
                {
                    if (rightsubtree.data > data)
                    {
                        rightsubtree = rightsubtree.right == null ? rightsubtree.left : rightsubtree.right;
                        countr++;
                    }
    
                }
            }
    
            return countr >= countl ? countr : countl;
    
    
        }
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文