我已经从排序数组创建了一个平衡的BST,我的问题是如何测试它简单地测试一棵树是否平衡是没有帮助的,因为即使是二叉树(注意提到的二叉树,不是BST)也可以平衡。测试树是否为BST也不是enof我现在唯一的答案是检查它是否balanced' &&bst`现在这是一个复杂的两步测试过程。有没有更简单/更聪明的解决方案?

最佳答案

如果它是平衡的,那么它的深度最多为log(n)+1,其中n是树/数组中的节点数。
检查树是否确实是BST可以简单地通过“按顺序”遍历节点并确保它们确实是按顺序的来完成。
顺便说一句,如果你有一个排序数组,有一个非常简单的方法来构建一个平衡的bst,你运行的方式和在二进制搜索中一样-只使用“insert”和应用搜索的“both side”。例如,假设您有:

1,2,3,4,5,6,7,8,9

首先插入5,然后插入37,然后插入其余部分。

08-26 23:25
查看更多