Introduction
This article is about binary trees. A Binary Tree contains unlimited number of nodes, the nodes can be removed, added, searched, etc. Here we will discuss on how to make a binary tree on c# code, and how to draw that on bitmap using GDI+.
Each
node on the binary tree has a unique value. for example 776 on the top of the
image is a unique value for the root node on the tree.
The rules of adding a new node to the tree are:
starting from the root node,
1. if the node's value is less than the root's value, it would be added to the left node of root node.
2. if the node's value is greater than the root's value, it would be added to the right node of root node.
Consider that adding a node to any node would have the same process as 1 and 2.
The rules of removing a node from the binary tree are:
1. the node has no child => simply remove that node
2. the node just has a left child => the left child of the removing node will take it's position on the tree
3.
the node has right child, and the right child does not have any left
child => the right child of the node will take the position of the
removing node on the tree
4. the node has right child, and the right
child also has left child => the most left child of the right child
will be removed (removing this node will cause a recursive algorithm!)
and take the position of the removing node.
Using the code
When the application starts, it randomly adds some nodes to the tree. By
pressing the add button (or pressing the enter key on textbox) the
value of the textbox wil be added as a node to the binary tree. By pressing the create button a new binary tree will be created. By pressing the remove button the node containing the value of textbox will be removed from the tree
By pressing the "Rnd Add" button a random value will be added to the three as a node. By pressing the save button the current image on the picturebox will be saved on the disk.
A complete description of how to use the code and it's methods
is represented on the main source code as XML parts. to understand it
completely we prefer you read the main source code attached to this
article.
It is easy to understand.
to create the tree and panit it use these lines:
private BinaryTree tree;
tree = new BinaryTree();
PaintTree();Colourised in 1ms
to add a node with the unique number of val
:
tree.Add(val); Colourised in 0ms
the add()
method :
public void Add(int val)
{
if (val < Value) {
if (Left == null)
Left = new Node(val);
else
Left.Add(val);
IsChanged = true;
}
else if (val > Value) {
IsChanged = true;
if (Right == null)
Right = new Node(val);
else
Right.Add(val);
}
}
Colourised in 11ms
to remove a node with the value of val
tree.Remove(val);
Colourised in 0ms
The remove()
method works the way described before. Removes the node containing the inserted value, also removes it's childs.
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) {
if (isLeft) Left = null; else Right = null;
}
else if (nodeToRemove.Right == null) {
if (isLeft) Left = nodeToRemove.Left; else Right = nodeToRemove.Left;
}
else {
if (nodeToRemove.Right.Left == null) {
nodeToRemove.Right.Left = nodeToRemove.Left;
if (isLeft)
Left = nodeToRemove.Right;
else
Right = nodeToRemove.Right;
}
else {
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;
}Colourised in 34ms
The paint operation is really easy: each node
will draw itself and it's child nodes, the method of drawing is
recursive calling every child to draw itself then passing the result to
the parent so the parent can draw itself and this process happens for
all the nodes
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;
}Colourised in 65ms
Finally the BinaryTree
class uses the methods and creates an instance of the binary tree
class BinaryTree
{
public Node RootNode { get; private set; }
public BinaryTree() {
RootNode = new Node(-1); }
public List<int> Items { get; private set; }
public void Add(int value)
{
RootNode.Add(value);
}
public bool Remove(int value)
{
bool isRootNode;
var res = RootNode.Remove(value, out isRootNode);
return !isRootNode && res; }
public Image Draw()
{
int temp;
return RootNode.Right == null ? null : RootNode.Right.Draw(out temp);
}
} Colourised in 20ms
History
You may find out many samples about binaryTrees! but the way of viewing them visuali and on c# code is what we wanted to show.
Find Us
hmojtaba@live.com