java - 二进制搜索树平衡工作以获得高度

Question

我知道这是非常简单的代码，但想知道内部工作到底是怎样的。

public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
            System.out.print(getHeight(root.left) +"\t");
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

据我了解，我添加了 print 语句，但结果如下。

打印 root.left() 打印如下:0 0 0 1 0 0 0

打印 root.right() 打印如下:0 0 2 0 0 3 0 0 2 0 0 0 1 0

下面是在主程序中创建的树:

TreeNode parent = new TreeNode(10);

        parent.insertInOrder(2);
        parent.insertInOrder(13);
        parent.insertInOrder(5);
        parent.insertInOrder(6);
        parent.insertInOrder(15);
        parent.insertInOrder(6);

这是如何打印上述结果的，它是如何工作的。如果有人能用上面的例子解释我，那真的对我有帮助。

我知道遍历是如何工作的以及如何打印树，但我真的很想了解上面的输出。如果有人可以提供帮助，那就太好了。

void setLeftChild(TreeNode left)
    {
        this.left = left;
        if(left == null)
        {
            left.parent = this;
        }
    }

    void setRightChild(TreeNode right)
    {
        this.right = right;
        if(right == null)
        {
            right.parent =  this;
        }
    }

    void insertInOrder(int d)
    {
        if(d <= data)
        {
            if(left == null)
            {
                setLeftChild(new TreeNode(d));
            }
            else
            {
                left.insertInOrder(d);
            }
        }
        else{
            if(right == null)
            {
                setRightChild(new TreeNode(d));
            }
            else{
                right.insertInOrder(d);
            }
        }
        size++;
    }

Answer 1

您应该创建一个函数来输出有关树的信息。例如，此函数执行前序遍历，显示有关每个节点的信息:

public static void ShowTree(TreeNode root, TreeNode parent, depth)
{
    if (root == null) return;

    // output 'depth' spaces.
    // The indentation will help show the structure of the tree.        

    // output node value, and parent (if parent not null)

    // Traverse the left node
    ShowTree(root.left, root, depth+1);

    // Traverse the right node
    ShowTree(root.right, root, depth+1);
}

使用 ShowTree(tree, null, 0) 调用该函数。生成的输出将显示树的结构，您可以确定树是否平衡。在开发树代码时，这很有用，因为您可以执行插入操作，例如，然后调用 ShowTree 查看插入操作是否按预期工作。

更新

代码的输出有点奇怪，因为您的 print 语句导致递归调用。因此，当前节点下方的每个节点最终都会被打印多次。

我想你想这样做:

int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
// now output output leftHeight or rightHeight, or both
return Math.max(leftHeight, rightHeight) + 1;

这样你就不会得到产生奇怪输出的多次递归调用。

更多信息

您看到这些额外递归调用的原因是因为您调用了两次 getHeight(root.left)。假设您的树看起来像这样:

       root
      /
   child
   /
grandchild

所以你调用了getHeight(root)。然后:

getHeight(child) is called in your print statement
getHeight(grandchild) is called in your print statement
getHeight(null) is called in your print statement
getHeight(grandchild) prints 0
getHeight(null) is called twice (once for the left node and once for the right node) in the return statement
getHeight(grandchild) returns 1
getHeight(child) prints 1
getHeight(grandchild) is called in the return statement
getHeight(null) is called in your print statement
getHeight(grandchild) prints 0
getHeight(grandchild) returns 1
getHeight(null) (the right node) is called in the return statement
...

你看到问题出在哪里了吗？ getHeight(grandchild) 再次被调用!每次您的 print 语句调用 getHeight 时，它都必须遍历每个后代节点。所以每个节点的高度都会输出多次。节点在树中越深，输出的次数越多。

我在上面的更新中建议的更改通过确保没有节点被访问超过一次来防止这种情况发生。