图形化二叉树
4.94/5 (45投票s)
一个图形化的二叉树。 特点：添加，删除或搜索一个节点。已使用递归算法
引言
本文是关于二叉树的。二叉树包含无限数量的节点，节点可以被删除、添加、搜索等。在这里，我们将讨论如何在 C# 代码中创建一个二叉树，以及如何使用 GDI+ 将其绘制在位图上。
二叉树中的每个节点都有一个唯一的值。例如，图像顶部的776是树的根节点的唯一值。
将新节点添加到树的规则是
从根节点开始
- 如果节点的值小于根节点的值，则将其添加到根节点的左节点
- 如果节点的值大于根节点的值，则将其添加到根节点的右节点
考虑将节点添加到任何节点的过程与 1 和 2 相同。
从二叉树中删除节点的规则是
- 节点没有子节点 => 直接删除该节点
- 节点只有一个左子节点 => 删除节点的左子节点将占用其在树中的位置
- 节点有右子节点，并且右子节点没有任何左子节点 => 节点的右子节点将占用删除节点在树中的位置
- 节点有右子节点，并且右子节点也有左子节点 => 右子节点最左边的子节点将被删除（删除此节点将导致递归算法！）并占用删除节点的位置
Using the Code
当应用程序启动时，它会随机向树中添加一些节点。通过按添加按钮（或在textbox上按回车键），textbox的值将被添加为二叉树的一个节点。通过按创建按钮，将创建一个新的二叉树。通过按删除按钮，将从树中删除包含textbox值的节点。
通过按“Rnd Add”按钮，一个随机值将作为节点添加到树中。通过按保存按钮，picturebox上的当前图像将保存在磁盘上。
在主源代码中以 XML 形式表示了如何使用代码及其方法的完整描述。为了完全理解它，我们建议您阅读附加到本文的主源代码。
这很容易理解。
要创建树并绘制它，请使用这些行
private BinaryTree tree;
tree = new BinaryTree();
PaintTree();
要添加一个具有唯一数字val的节点
tree.Add(val);
add()方法
public void Add(int val)
{
if (val < Value)// add to left
{
if (Left == null)
Left = new Node(val);
else
Left.Add(val);
IsChanged = true;
}
else if (val > Value) // add to right
{
IsChanged = true;
if (Right == null)
Right = new Node(val);
else
Right.Add(val);
}
}
要删除一个值为val的节点
tree.Remove(val);
remove()方法以之前描述的方式工作。删除包含插入值的节点，并删除其子节点。
public bool Remove(int val, out bool containedOnMe)
{
Node nodeToRemove;
containedOnMe = false;
var isLeft = val < Value;
if (val < Value)
nodeToRemove = Left;
else if (val > Value)
nodeToRemove = Right;
else
{
if(Left!=null)
Left.IsChanged = true;
if (Right != null)
Right.IsChanged = true;
containedOnMe = true;
return false;
}
if (nodeToRemove == null)
return false;
bool containOnChild;
var result = nodeToRemove.Remove(val, out containOnChild);
if (containOnChild)
{
IsChanged = true;
if (nodeToRemove.Left == null && nodeToRemove.Right == null)// no child
{
if (isLeft) Left = null; else Right = null;
}
else if (nodeToRemove.Right == null)// left child
{
if (isLeft) Left = nodeToRemove.Left; else Right = nodeToRemove.Left;
}
else // left and right are not null
{
if (nodeToRemove.Right.Left == null)// no left child for right child of node
{
nodeToRemove.Right.Left = nodeToRemove.Left;
if (isLeft)
Left = nodeToRemove.Right;
else
Right = nodeToRemove.Right;
}
else // there is a left child for right child of node
{
Node nLeft = null;
for (var n = nodeToRemove.Right; n != null; n = n.Left)
if (n.Left == null)
nLeft = n;
bool temp;
var v = nLeft.Value;
Remove(nLeft.Value, out temp);
nodeToRemove.Value = v;
}
}
return true;
}
return result;
}
绘制操作非常简单：每个节点将绘制自身及其子节点，绘制方法是递归调用每个子节点来绘制自身，然后将结果传递给父节点，以便父节点可以绘制自身，并且此过程对所有节点都发生。
/// <summary>
/// paints the node and it's childs
/// </summary>
public Image Draw(out int center)
{
center = _lastCenter;
if (!IsChanged)
return _lastImage;
var lCenter = 0;
var rCenter = 0;
Image lImg = null, rImg = null;
if (Left != null)
lImg = Left.Draw(out lCenter);
if (Right != null)
rImg = Right.Draw(out rCenter);
var me = new Bitmap(40, 40);
var g = Graphics.FromImage(me);
g.SmoothingMode = SmoothingMode.HighQuality;
var rcl = new Rectangle(0, 0, me.Width - 1, me.Height - 1);
g.FillRectangle(Brushes.White, rcl);
g.FillEllipse(new LinearGradientBrush(new Point(0, 0),
new Point(me.Width, me.Height), Color.Gold, Color.Black), rcl);
var lSize = new Size();
var rSize = new Size();
var under = (lImg != null) || (rImg != null);
if (lImg != null)
lSize = lImg.Size;
if (rImg != null)
rSize = rImg.Size;
var maxHeight = lSize.Height;
if (maxHeight < rSize.Height)
maxHeight = rSize.Height;
var resSize = new Size
{
Width = me.Size.Width + lSize.Width + rSize.Width,
Height = me.Size.Height + (under ? maxHeight + me.Size.Height : 0)
};
var result = new Bitmap(resSize.Width, resSize.Height);
g = Graphics.FromImage(result);
g.SmoothingMode = SmoothingMode.HighQuality;
g.FillRectangle(Brushes.White, new Rectangle(new Point(0, 0), resSize));
g.DrawImage(me, lSize.Width, 0);
g.DrawString(Value.ToString(), new Font("Tahoma", 14),
Brushes.White, lSize.Width + 5, me.Height / 2f - 12);
center = lSize.Width + me.Width / 2;
var pen = new Pen(Brushes.Black, 2.5f)
{
EndCap = LineCap.ArrowAnchor,
StartCap = LineCap.Round
};
float x1 = center;
float y1 = me.Height;
float y2 = me.Height * 2;
float x2 = lCenter;
var h = Math.Abs(y2 - y1);
var w = Math.Abs(x2 - x1);
if (lImg != null)
{
g.DrawImage(lImg, 0, me.Size.Height * 2);
var points1 = new List<PointF>
{
new PointF(x1, y1),
new PointF(x1 - w/6, y1 + h/3.5f),
new PointF(x2 + w/6, y2 - h/3.5f),
new PointF(x2, y2),
};
g.DrawCurve(pen, points1.ToArray(), 0.5f);
}
if (rImg != null)
{
g.DrawImage(rImg, lSize.Width + me.Size.Width, me.Size.Height * 2);
x2 = rCenter + lSize.Width + me.Width;
w = Math.Abs(x2 - x1);
var points = new List<PointF>
{
new PointF(x1, y1),
new PointF(x1 + w/6, y1 + h/3.5f),
new PointF(x2 - w/6, y2 - h/3.5f),
new PointF(x2, y2)
};
g.DrawCurve(pen, points.ToArray(), 0.5f);
}
IsChanged = false;
_lastImage = result;
_lastCenter = center;
return result;
}
最后，BinaryTree类使用这些方法并创建二叉树的实例。
class BinaryTree
{
public Node RootNode { get; private set; }
public BinaryTree()//int rootValue)
{
RootNode = new Node(-1);//rootValue);
}
public List<int> Items { get; private set; }
/// <summary>
/// adds an item to tree
/// </summary>
public void Add(int value)
{
RootNode.Add(value);
}
/// <summary>
/// Removes the node containing the inserted value and also it's childs,
/// returns true if could find and remove the node.
/// return false if the inserted value is on rootNode, or the value does not exist on any of nodes.
/// </summary>
public bool Remove(int value)
{
bool isRootNode;
var res = RootNode.Remove(value, out isRootNode);
return !isRootNode && res;// return false if the inserted value is on rootNode,
// or the value does not exist on any of nodes
}
// draw
public Image Draw()
{
int temp;
return RootNode.Right == null ? null : RootNode.Right.Draw(out temp);
}
}
历史
您可能会发现许多关于二叉树的示例！ 但我们想展示的是如何从视觉上以及在 C# 代码中查看它们。