For each subtree:
- Find the middle element of the subtree and put that at the top of the tree.
- Find all the elements before the middle element and use this algorithm recursively to get the left subtree.
- Find all the elements after the middle element and use this algorithm recursively to get the right subtree.
If you sort your elements first (as in your example) finding the middle element of a subtree can be done in constant time.
This is a simple algorithm for constructing a one-off balanced tree. It is not an algorithm for a self-balancing tree.
Here is some source code in C# that you can try for yourself:
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(), 0, values.Count());
}
void Run()
{
TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9));
// displayTree(balancedTree); // TODO: implement this!
}
static void Main(string[] args)
{
new Program().Run();
}
}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…