如何在C#中实现二叉树? [英] how to implement binary tree in c#?
问题描述
我尝试了这个.我为树上课
i tried this. i make a class for tree
class BT
{
private BT left;
internal BT Left
{
get { return left; }
set { left = value; }
}
private BT right;
internal BT Right
{
get { return right; }
set { right = value; }
}
private int value;
public int Value
{
get { return this.value; }
set { this.value = value; }
}
static private int count=0;
public static int Count
{
get { return BT.count; }
set { BT.count = value; }
}
public BT()
{
left = null;
right = null;
value = 0;
}
public void Add(BT t,int input)
{
if (t.value == 0)
{
t.value = input;
t.Left = null;
t.Right= null;
count++;
}
else if(t.value>=input)
{
t.left.value = input;
t.left.left = null;
t.right.right = null;
count++;
}
else if(t.value<input)
{
t.right.value = input;
t.left.left = null;
t.right.right = null;
count++;
}
}
public void Print(BT tree)
{
Form1 o = new Form1();
if (tree.right != null)
Print(tree.right);
o.richTextBox1.AppendText(tree.value.ToString());
if (tree.left != null)
Print(tree.left);
}
}
}并通过此代码
进行调用
and call it by this code
BT pNode = new BT();
pNode.Add(pNode, 5);
pNode.Add(pNode, 2);
pNode.Add(pNode,1);
pNode.Add(pNode,3);
pNode.Print(pNode);给出运行时错误对象引用未设置为对象实例".在行t.left.value = input;
it gives run time error "Object reference not set to an instance of an object." on line t.left.value = input;
推荐答案
上，您没有为树创建新对象.首先替换以下代码块.
You are not creating the new objects for your tree. Start by replacing the following code blocks.
else if(t.value>=input)
{
t.left.value = input;
t.left.left = null;
t.right.right = null;
count++;
}
与
with
else if(t.value>=input)
{
t.left = new BT();
t.left.value = input;
t.left.left = null;
t.left.right = null;
count++;
}
和
and
else if(t.value<input)
{
t.right.value = input;
t.left.left = null;
t.right.right = null;
count++;
}
与
with
else if(t.value<input)
{
t.right = new BT();
t.right.value = input;
t.right.left = null;
t.right.right = null;
count++;
}
添加和更改的代码为粗体.
在添加的new语句旁边，在null分配中使用了错误的left和right分支.顺便说一下，由于BT构造函数已经将它们分配为null，因此不需要这些分配.
The added and changed code is bold.
Next to the new statements being added the incorrect left and right branches were used in the null assignments. By the way these assignments are not needed as the BT constructor sets them to null already.
安德烈在某种程度上是正确的，但是他的解决方案无法为您构建一棵完整的树-当您提供其他值时，他会覆盖任何现有节点.
如果您的树值用于创建树，例如
Andre is right to a certain extent, but his solution does not build you a full tree - he overwrites any existing node when you provide a different value.
If your tree values are meant to create a tree such as
5
/ \
2
/ \
1 3然后您需要检查节点是否已经存在，然后再创建新节点.
另外，我不会将节点传递给您的add方法:而是使其在当前实例上起作用:
Then you need to check is nodes exist already, before creating new ones.
In addition, I would not pass through the node to your add method: make it work on the current instance instead:
public class BTree
{
public int Value { get; set; }
public BTree Left { get; set; }
public BTree Right { get; set; }
public BTree() : this(0) { }
public BTree(int val)
{
Value = val;
}
public void Add(int val)
{
if (Value == 0)
{
Value = val;
}
else if (Value > val)
{
if (Left == null)
{
Left = new BTree(val);
}
else
{
Left.Add(val);
}
}
else
{
if (Right == null)
{
Right = new BTree(val);
}
else
{
Right.Add(val);
}
}
}
}还有另外两件事发生:
1)您的Count几乎没有用:它返回已缩放的节点总数，而不是正在使用的节点或该树中涉及的节点数.如果您覆盖一个节点(如Andre在其示例中所做的那样)，则它不会减少计数.从这一点开始，您最好实现一个Count属性，该属性对树中的节点数进行计数:
Two other things occur:
1) Your Count is pretty useless: it returns the total number of nodes that have been cretaed, rather than the number which are in use, or which are involved in this tree. If you overwrite a node (as Andre does in his example), it does not decrease the count. You would be better off implementing a Count property which counted the number of nodes in teh tree from this point:
public int Count
{
get
{
int count = 1;
if (Left != null) count += Left.Count;
if (Right != null) count += Right.Count;
return count;
}
}
2)您可能不希望使用Print方法-该单词在计算中具有特定含义.相反，请考虑提供一个ToString方法，该方法将整个树作为字符串返回:
2) You probably don''t want a Print method - that word has a particular meaning in computing. Instead, consider providing a ToString method which returns the whole tree as a string:
public override string ToString()
{
StringBuilder sb = new StringBuilder();
sb.Append(Value.ToString());
if (Left != null || Right != null)
{
sb.Append(":(");
if (Left != null)
{
sb.Append(Left.ToString());
}
sb.Append(",");
if (Right != null)
{
sb.Append(Right.ToString());
}
sb.Append(")");
}
return sb.ToString();
}
创建树时，其中的节点数会随着您添加新元素而改变，对吗?
因此您需要为每个添加"操作创建一个新节点
when creating a tree, the number of nodes in it changes as you add new elements, right?
so you need to create a new node for every ''add'' operation
class BT
{
...
public void Add(BT t,int input)
{
...
else if(t.value>=input)
{
//add: t.left = new BT();
t.left.value = input; //<--- here t.left is null in your problem
t.left.left = null;
t.right.right = null;
count++;
}
else if(t.value<input)
{
//similarly here,
//add: t.right = new BT();
t.right.value = input;
t.left.left = null;
t.right.right = null;
count++;
}
}
public void Print(BT tree)
{
Form1 o = new Form1();
if (tree.right != null)
Print(tree.right);
o.richTextBox1.AppendText(tree.value.ToString());
if (tree.left != null)
Print(tree.left);
}
}
}
这篇关于如何在C#中实现二叉树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
