C# Cookbook

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 ...