在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块中,但是我无法弄清楚它的分辨率.

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

虽然我在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 的节点，出现了一个模式：

• 左孩子的索引为 2*i + 1
• 右孩子的索引为 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;