O'Reilly logo

C# Cookbook by Jay Hilyard, Stephen Teilhet

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

10.6. Creating a Binary Tree

Problem

You need to store information in a tree structure, where the left node is less than its parent node, and the right node is greater than or equal to (in cases where the tree can contain duplicates) its parent. The stored information must be easily inserted into the tree, removed from the tree, and found within the tree.

Solution

Each node must be an object that inherits from the IComparable interface. This means that every node that wishes to be included in the binary tree must implement the CompareTo method. This method will allow one node to determine whether it is less than, greater than, or equal to another node.

Use the following BinaryTree class, which contains all of the nodes in a binary tree and lets you traverse it:

using System; using System.Collections; public class BinaryTree { public BinaryTree( ) {} public BinaryTree(IComparable value, int index) { BinaryTreeNode node = new BinaryTreeNode(value, index); root = node; counter = 1; } // Use this .ctor when you need to flatten this tree (see recipe 9.15) public BinaryTree(IComparable value) { BinaryTreeNode node = new BinaryTreeNode(value); root = node; counter = 1; } protected int counter = 0; // Number of nodes in tree protected BinaryTreeNode root = null; // Pointer to root node in this tree public void AddNode(IComparable value, int index) { BinaryTreeNode node = new BinaryTreeNode(value, index); ++counter; if (root == null) { root = node; } else { root.AddNode(node); } } // Use ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required