如何構建大型二叉樹？

Question

這是一個多年來一直困擾着我的問題。我想知道如何構建大型二叉樹，我知道的唯一方法是創建一個將一個元素推送到樹上的函數（稱爲insert（）;的函數）。如果我有一個3元素樹並且想要添加5個元素，我將不得不調用插入函數5次。這似乎是一個非常糟糕的方法，如果我想添加50個元素呢？必須有比調用insert（）函數五十次更好的方法。

Answer 1

有。 Knuth給出了一個用於構建合理平衡二進制的算法排序輸入，在ACP第三卷我想。

Answer 2

如果數據是預先排序的，您可以遞歸構建它。

基本上建立了樹的一些輸入：

1. 創建一個新的節點
2. 如果輸入的是隻有一個條目，該節點的值是進入
3. 否則：
   1. 在節點的左側子樹中，放置從輸入的前半部分構建的樹
   2. 在節點的右側子樹中，放置構建的樹M中的輸入

第三步將遞歸本身適用於輸入的多個部分的第二個一半。

下面是一些僞代碼：

FUNCTION TREE (input -> node) 
    IF input IS 1 ENTRY 
     VALUE OF node IS entry OF input 
    ELSE 
     SPLIT input IN 2 
     LEFT SUB-TREE OF node IS TREE(FIRST HALF OF input) 
     RIGHT SUB-TREE OF node IS TREE(SECOND HALF OF input) 

下面是一些LINQPad C＃代碼，你可以體驗：

// Add the following two using-directives to LINQPad: 
// System.Drawing 
// System.Drawing.Imaging 

static Bitmap _Dummy = new Bitmap(16, 16, PixelFormat.Format24bppRgb); 
static Font _Font = new Font("Arial", 12); 

void Main() 
{ 
    var sorted = Enumerable.Range(1, 16).ToArray(); 
    var tree = BuildTree(sorted); 
    Visualize(tree); 
} 

public Node<T> BuildTree<T>(T[] input) 
{ 
    return BuildTree<T>(input, 0, input.Length); 
} 

public Node<T> BuildTree<T>(T[] input, int left, int right) 
{ 
    if (right <= left) 
     return null; 

    if (right == left + 1) 
     return new Node<T> { Value = input[left] }; 

    int middle = (left + right)/2; 
    return new Node<T> 
    { 
     Left = BuildTree<T>(input, left, middle), 
     Right = BuildTree<T>(input, middle, right) 
    }; 
} 

public class Node<T> 
{ 
    public T Value; 
    public Node<T> Left; 
    public Node<T> Right; 

    public Bitmap ToBitmap() 
    { 
     Size valueSize; 
     using (Graphics g = Graphics.FromImage(_Dummy)) 
     { 
      var tempSize = g.MeasureString(Value.ToString(), _Font); 
      valueSize = new Size((int)tempSize.Width + 4, (int)tempSize.Height + 4); 
     } 

     Bitmap bitmap; 
     Color valueColor = Color.LightPink; 
     if (Left == null && Right == null) 
     { 
      bitmap = new Bitmap(valueSize.Width, valueSize.Height); 
      using (var g = Graphics.FromImage(bitmap)) 
       g.Clear(Color.White); 
      valueColor = Color.LightGreen; 
     } 
     else 
     { 
      using (var leftBitmap = Left.ToBitmap()) 
      using (var rightBitmap = Right.ToBitmap()) 
      { 
       int subNodeHeight = Math.Max(leftBitmap.Height, rightBitmap.Height); 
       bitmap = new Bitmap(
        leftBitmap.Width + rightBitmap.Width + valueSize.Width, 
        valueSize.Height + 32 + subNodeHeight); 

       using (var g = Graphics.FromImage(bitmap)) 
       { 
        g.Clear(Color.White); 
        int baseY = valueSize.Height + 32; 

        int leftTop = baseY; // + (subNodeHeight - leftBitmap.Height)/2; 
        g.DrawImage(leftBitmap, 0, leftTop); 

        int rightTop = baseY; // + (subNodeHeight - rightBitmap.Height)/2; 
        g.DrawImage(rightBitmap, bitmap.Width - rightBitmap.Width, rightTop); 

        g.DrawLine(Pens.Black, bitmap.Width/2 - 4, valueSize.Height, leftBitmap.Width/2, leftTop); 
        g.DrawLine(Pens.Black, bitmap.Width/2 + 4, valueSize.Height, bitmap.Width - rightBitmap.Width/2, rightTop); 
       } 
      } 
     } 

     using (var g = Graphics.FromImage(bitmap)) 
     { 
      float x = (bitmap.Width - valueSize.Width)/2; 
      using (var b = new SolidBrush(valueColor)) 
       g.FillRectangle(b, x, 0, valueSize.Width - 1, valueSize.Height - 1); 
      g.DrawRectangle(Pens.Black, x, 0, valueSize.Width - 1, valueSize.Height - 1); 
      if (Left == null && Right == null) 
       g.DrawString(Value.ToString(), _Font, Brushes.Black, x + 1, 2); 
     } 

     return bitmap; 
    } 
} 

void Visualize<T>(Node<T> node) 
{ 
    node.ToBitmap().Dump(); 
} 

這裏的輸出：