In computer science, binary search trees are a very essential data structure. They’re binary trees, as the name implies, with a value, a left child, and a right child for each node. The following is an important property of a binary search tree:
- If a node has a left child, the left child is the root of a binary search tree with a maximum value equal to or less than the node’s value.
- If a node has a right child, the right child is the root of a binary search tree with a minimum value equal to or greater than the node’s value.
Below are examples of binary search trees that hold the number
Implementation
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BTree
{
public class Node
{
public int Data { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node()
{
}
public Node(int data)
{
this.Data = data;
}
}
public class BinaryTree
{
private Node _root;
public BinaryTree()
{
_root = null;
}
public void Insert(int data)
{
// 1. If the tree is empty, return a new, single node
if (_root == null)
{
_root = new Node(data);
return;
}
// 2. Otherwise, recur down the tree
InsertRec(_root, new Node(data));
}
private void InsertRec(Node root, Node newNode)
{
if (root == null)
root = newNode;
if (newNode.Data < root.Data)
{
if (root.Left == null)
root.Left = newNode;
else
InsertRec(root.Left, newNode);
}
else
{
if (root.Right == null)
root.Right = newNode;
else
InsertRec(root.Right, newNode);
}
}
private void DisplayTree(Node root)
{
if (root == null) return;
DisplayTree(root.Left);
System.Console.Write(root.Data + " ");
DisplayTree(root.Right);
}
public void DisplayTree()
{
DisplayTree(_root);
}
}
class Program
{
static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
Node root = new Node();
tree.Insert(4);
tree.Insert(2);
tree.Insert(5);
tree.Insert(1);
tree.Insert(3);
tree.DisplayTree();
}
}
}
See the below animation for insertion
Happy Coding 😊
what is the use of that node class ?
ReplyDeleteNode Class hold the node data like node value and there children
Delete