logo标签列表

在二叉搜索树中查找高度

algorithmrecursionbinary-search-tree
78

我想知道有没有人能帮我改进这个方法来找到二叉搜索树的高度。到目前为止，我的代码看起来像这样。但是，我得到的答案比实际高度大1。但当我从返回语句中删除+1时，它比实际高度少1。我仍在努力理解这些BST的递归。非常感谢任何帮助。

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;
    }
}
我在我的公共方法中返回findHeight(node)-1以正确返回高度。但是我觉得这是不太优秀的代码，你们有什么关于重构的建议吗？ - mike
这是解决树高的正确方法吗？https://github.com/joeyajames/Python/issues/1 - rittam
26个回答
2

上文给出的高度定义是不正确的，那是深度的定义。

"树中节点 M 的深度是从树的根到 M 的路径长度。树的高度比树中最深节点的深度多1。深度为 d 的所有节点在树的第 d 层。根是唯一位于第0层的节点，其深度为0。"

引用: "《数据结构与算法分析（Java语言描述）》第3.2版" Clifford A. Shaffer 计算机科学系 Virginia Tech Blacksburg, VA 24061

2

//查找二叉搜索树的高度的函数

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;
}
2
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;
}
2
我知道我来晚了。在查看这里提供的精彩答案后，我认为我的答案将为此帖子增加一些价值。虽然发布的答案很棒并且易于理解，但是所有答案都以线性时间计算BST的高度。我认为这可以改进，并且可以在< strong>常数时间内检索高度，因此写下这个答案 - 希望您会喜欢它。 让我们从节点类开始：
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操作中保持树的高度的想法，受到算法（第四版）书第3章（第399页）中BST方法的启发。
1

将tempHeight设为静态变量（初始值为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);

}
1

这里有一个 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);
    }
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;
}
1
这是一个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);
    }
1
我猜这个问题可能有两种不同的意思...
1. 高度是最长分支中节点的数量： ``` 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. 高度是树本身中节点的总数： ``` int calcSize(node* root){ if(root==NULL) return 0; return(calcSize(root->left)+1+calcSize(root->right)); } ```
1
 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接