我正在尝试在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块中，但是我无法弄清楚分辨率。
我试图在线寻找解决方案，但大多数地方都使用了Binary Search Tree实现。我喜欢的解决方案之一是在这里，但是解决方案是将输入数组作为递归调用的参数传递，我不知道这对于大型树而言是否有效。还有其他几篇文章，但是都没有解决我的问题。
尽管我正在C＃中实现它，但是更具体地说，我正在寻找修复我的AddNode（...）函数的逻辑，因此即使不是代码实现，我也对算法很好。
有什么帮助吗？
根据定义，树是递归数据结构。
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的节点，出现了一种模式：
有了递归的基本情况，
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;
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句