计算BST高度的递归函数

Question

工商及科技局成员如下：

    50 (Root 1)
   / \
  40  80 (Root 2)
 / \
20 41

正如你所看到的，有两个根，我正在处理。我尝试了下面的代码，它可以从根1返回树的高度，我不太知道如何从根2返回树的高度。

任何关于如何解决问题的帮助都将不胜感激。

// Java program to find height of tree 

// A binary tree node 
class Node  
{ 
    int data; 
    Node left, right; 

    Node(int item)  
    { 
        data = item; 
        left = right = null; 
    } 
} 

class BinaryTree  
{ 
    Node root; 

    int maxDepth(Node node)  
    { 
        if (node == null) 
            return 0; 
        else 
        { 
            /* compute the depth of each subtree */
            int lDepth = maxDepth(node.left); 
            int rDepth = maxDepth(node.right); 

            /* use the larger one */
            if (lDepth > rDepth) 
                return (lDepth + 1); 
             else 
                return (rDepth + 1); 
        } 
    } 

    /* Driver program to test above functions */
    public static void main(String[] args)  
    { 
        BinaryTree tree = new BinaryTree(); 

        tree.root = new Node(1); 
        tree.root.left = new Node(2); 
        tree.root.right = new Node(3); 
        tree.root.left.left = new Node(4); 
        tree.root.left.right = new Node(5); 

        System.out.println("Height of tree is : " +  
                                      tree.maxDepth(tree.root)); 
    } 

Answer 1

您查找最大深度的功能似乎是正确工作的。所以解决这个问题很简单。

System.out.println("Height of tree is : " +  
                                  tree.maxDepth(tree.root));

上面的一行打印出从根开始的树的高度。但是，如果要从"root 2“开始(您称之为”root 2“)，则需要修改该行以从正确的节点开始。

System.out.println("Height of tree is : " +  
                                  tree.maxDepth(tree.root.right));

Answer 2

应该通过insert方法向Tree类添加项。并且我们可以使Node类私有，它只被BinaryTree类使用。

树的更好的数据结构应该如下所示，它具有公共插入和高度方法。

public class BinaryTree {

    private class Node {

        private int value;
        private Node left;
        private Node right;

        private Node(int value) {
            this.value = value;
        }
    }

    private Node root;

    public void insert(int item) {

        var node = new Node(item);
        if (root == null) {
            root = node;
            return;
        }

        var current = root;

        while (true) {

            if (item < current.value) {
                if (current.left == null) {
                    current.left = node;
                    break;
                }
                current = current.left;

            } else {
                if (current.right == null) {
                    current.right = node;
                    break;
                }
                current = current.right;
            }
        }
    }

    public int height() {
       return height(root);
    }

    private int height(Node root) {
        if (root == null)
            return -1;

        if (isLeaf(root))
            return 0;

        return 1 + Math.max(height(root.left), height(root.right));
    }

    private boolean isLeaf(Node node) {
        return node.left == null && node.right == null;
    }
}

要使用它，只需添加一些值，并打印高度。使用此树类插入项要容易得多。

        BinaryTree tree = new BinaryTree();

        tree.insert(50);
        tree.insert(40);
        tree.insert(80);
        tree.insert(20);
        tree.insert(41);

        System.out.println(tree.height());