有没有办法构建一个平衡的二叉搜索树？
例：
1 2 3 4 5 6 7 8 9
5
/ \
3 etc
/ \
2 4
/
1
我认为有一种方法可以做到这一点,而不使用更复杂的自平衡树.否则我可以自己做,但有人可能已经这样做了:)
谢谢你的答案！这是最后的python代码：
def _buildTree(self,keys):
if not keys:
return None
middle = len(keys) // 2
return Node(
key=keys[middle],left=self._buildTree(keys[:middle]),right=self._buildTree(keys[middle + 1:])
)
解决方法
对于每个子树：
>查找子树的中间元素,并将其放在树的顶部.
>查找中间元素之前的所有元素,并使用该算法递归获取左子树.
>查找中间元素后的所有元素,并递归使用该算法获得正确的子树.
如果您首先对元素进行排序(如您的示例),则可以在常量时间内找到子树的中间元素.
这是构建一次性平衡树的简单算法.它不是自平衡树的算法.
这是C#中的一些源代码,您可以为自己尝试：
public class Program
{
class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
}
TreeNode constructBalancedTree(List<int> values,int min,int max)
{
if (min == max)
return null;
int median = min + (max - min) / 2;
return new TreeNode
{
Value = values[median],Left = constructBalancedTree(values,min,median),Right = constructBalancedTree(values,median + 1,max)
};
}
TreeNode constructBalancedTree(IEnumerable<int> values)
{
return constructBalancedTree(
values.OrderBy(x => x).ToList(),values.Count());
}
void Run()
{
TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1,9));
// displayTree(balancedTree); // TODO: implement this!
}
static void Main(string[] args)
{
new Program().Run();
}
}
