Binary Search Tree in C # Implementation

Question

class Node { public int data; public Node left, right; public Node(int data) { this.data = data; left = null; right = null; } } class BinaryTreeImp { Node root; static int count = 0; public BinaryTreeImp() { root = null; } public Node addNode(int data) { Node newNode = new Node(data); if (root == null) { root = newNode; } count++; return newNode; } public void insertNode(Node root,Node newNode ) { Node temp; temp = root; if (newNode.data < temp.data) { if (temp.left == null) { temp.left = newNode; } else { temp = temp.left; insertNode(temp,newNode); } } else if (newNode.data > temp.data) { if (temp.right == null) { temp.right = newNode; } else { temp = temp.right; insertNode(temp,newNode); } } } public void displayTree(Node root) { Node temp; temp = root; if (temp == null) return; displayTree(temp.left); System.Console.Write(temp.data + " "); displayTree(temp.right); } static void Main(string[] args) { BinaryTreeImp btObj = new BinaryTreeImp(); Node iniRoot= btObj.addNode(5); btObj.insertNode(btObj.root,iniRoot); btObj.insertNode(btObj.root,btObj.addNode(6)); btObj.insertNode(btObj.root,btObj.addNode(10)); btObj.insertNode(btObj.root,btObj.addNode(2)); btObj.insertNode(btObj.root,btObj.addNode(3)); btObj.displayTree(btObj.root); System.Console.WriteLine("The sum of nodes are " + count); Console.ReadLine(); } } 

This is the code to implement. The code works fine, but if in the displayTree function I replace it with

 public void displayTree(Node root) { Node temp; temp = root; while(temp!=null) { displayTree(temp.left); System.Console.Write(temp.data + " "); displayTree(temp.right); } } 

an endless cycle arises. I do not understand what causes this. I would also like to know if there is a better way to implement BST in C #.

Answer 1

I'm not sure why you need this loop, but answering your question:

 while(temp!=null) { displayTree(temp.left); System.Console.Write(temp.data + " "); displayTree(temp.right); } 

this code checks to see if temp null , but it will never become null, as a result, inside the loop, you only act on temp sheets. That is why you have an infinite loop.

Answer 2

You do not need a while loop or temp variable, let recursion do your work:

 public void displayTree(Node root) { if(root == null) return; displayTree(root.left); System.Console.Write(root.data + " "); displayTree(root.right); } 

Answer 3

temp is set to the root at the beginning, and after that its value never changes

how to rewrite your function as

 public void displayTree(Node root) { if (root == null) return; displayTree(root.left); Console.Write(...); displayTree(root.right); } 

Answer 4

try it

  public void displayTree(Node root) { Node temp; temp = root; if (temp != null) { displayTree(temp.left); Console.WriteLine(temp.data + " "); displayTree(temp.right); } } 

Answer 5

I just thought you could also use recursion for the add function. It might look something like this.

  private void Add(BinaryTree node, ref BinaryTree rootNode) { if (rootNode == null) { rootNode = node; } if (node.value > rootNode.value) { Add(node, ref rootNode.right); } if (node.value < rootNode.value) { Add(node, ref rootNode.left); } } 

Answer 6

See https://msdn.microsoft.com/en-us/library/ms379572%28v=vs.80%29.aspx . See Sample Code in Moving BST Nodes

Also ... don't forget to check out SortedDictionary, etc. They may have a BST, that you need everything ready! https://msdn.microsoft.com/en-us/library/f7fta44c.aspx