c# - 在 C# 中实现一个完整的二叉树，而不是二叉搜索树

Question

我正在尝试用 C# 实现二叉树，而不是二叉搜索树。我实现了下面的代码，它工作正常但不是我想要的。基本上我正在尝试实现一个完整的二叉树，但是使用下面的代码，我得到了一个不平衡的二叉树。

Input : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired Output : 

                        10
                     /       \
                 20            30
               /    \         /  \
            40        50    60    70
           /  \      /
         80    90  100     


Current Output : 
                                10
                              /    \
                            20      30
                                  /    \
                                40      50    
                                       /   \
                                     60     70
                                           /  \
                                         80    90  
                                              /
                                            100   

这是我的代码:

  class Node 
  {
    public int data;
    public Node left;
    public Node right;

    public Node() 
    {
      data = 0;
      left = null;
      right = null;
    }
  }

  class Tree 
  {
    private Node root;

    public Tree() 
    {
      root = null;
    }

    public void AddNode(int data)
    {
      root = AddNode(root, data);
    }

    public Node AddNode(Node node, int data) 
    {
      if (node == null)
      {
        node = new Node();
        node.data = data;
      }
      else
      {
        if (node.left == null)
        {
          node.left = AddNode(node.left, data);
        }
        else
        {
          node.right = AddNode(node.right, data);
        }
      }
      return node;
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      int[] nodeData = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
      Tree tree1 = new Tree();
      foreach (int i in nodeData)
      {
        tree1.AddNode(i);
      }
      Console.ReadKey();
    }
  }

我知道问题出在我的 AddNode(Node node, int data) {...} 函数的 else block 中，但我无法找出解决方案。

我试图在网上寻找解决方案，但大多数地方都是二叉搜索树实现。我喜欢的解决方案之一是 here但解决方案是将输入数组作为递归调用的参数传递，我不知道在非常大的树的情况下这是否有效。还有其他几个帖子，但没有一个能解决我的问题。

虽然我是在 C# 中实现它，但更具体地说，我正在寻找修复我的 AddNode(...) 函数的逻辑，所以即使不是代码实现，我也能接受算法。

有什么帮助吗？

Answer 1

根据定义，树是递归数据结构。

class Node<T>
{
    public Node(T data)
    {
        Data = data;
    }
    public T Data { get; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
}

因此，使用递归构建它们要直观得多。

Input: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100

Desired output --complete binary tree:

               10
           /        \
         20          30
      /     \     /      \
    40       50  60      70
  /   \     /    
80     90  100

Matching index of input:

               0
           /       \
          1         2
      /     \     /     \
    3        4   5       6
  /   \     /    
 7     8   9

出现一个模式，对于索引为 i 的节点:

• 左 child 的索引为 2*i + 1
• 右 child 的索引为 2*i + 2

有了递归的基本情况，

i >= input.length

我们需要做的就是调用根上的递归方法。

class TreeBuilder<T>
{
    public Node<T> Root { get; }

    public TreeBuilder(params T[] data)
    {
        Root = buildTree(data, 0);
    }

    private Node<T> buildTree(T[] data, int i)
    {
        if (i >= data.Length) return null;
        Node<T> next = new Node<T>(data[i]);
        next.Left = buildTree(data, 2 * i + 1);
        next.Right = buildTree(data, 2 * i + 2);
        return next;
    }
}

用法:

int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data);
Node<int> tree = builder.Root;

---

切换API，一对一添加节点的几种方式:

• 从根向下遍历树(绝对)
• 从先前添加的节点(相对)开始
• 维护没有两个子节点的有序节点集合

由于第二个涉及较长的行进距离(2 * 树的高度)并且第三个已经实现(用于记账的队列)，让我们看一下第一个。

这一次，可视化给定位置的节点数:

               1
           /        \
         2           3
      /     \     /     \
    4        5   6       7 
  /   \     /    
8      9   10 

映射到二进制表示:

               1
           /        \
         10          11
      /     \     /     \
   100     101  110     111 
  /   \     /    
1000  1001 1010 

如果我们忽略最左边的位，同样会出现一个模式。我们可以将这些位用作路线图，或者在本例中为节点图。

class TreeBuilder<T>
{
    private int level;
    private int nodeCount;
    public Node<T> Root { get; }

    public TreeBuilder(T data)
    {
        Root = new Node<T>(data);
        nodeCount = 1;
        level = 0;
    }

    public void addNode(T data)
    {
        nodeCount++;
        Node<T> current = Root;
        if (nodeCount >= Math.Pow(2, level + 1)) level++;
        for (int n=level - 1; n>0; n--)
            current = checkBit(nodeCount, n) ? current.Left : current.Right;
        if (checkBit(nodeCount, 0))
            current.Left = new Node<T>(data);
        else
            current.Right = new Node<T>(data);
    }

    private bool checkBit(int num, int position)
    {
        return ((num >> position) & 1) == 0;
    }
}

用法:

int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data[0]);
for (int i=1; i<data.Length; i++)
{
    builder.addNode(data[i]);
}
Node<int> tree = builder.Root;