C# 3.0 Cookbook, 3rd Edition

11.4. Creating a Binary Search 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 in which 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

To implement a binary tree of the type described in the Problem statement, each node must be an object that inherits from the IComparable<T> interface. This means that every node 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 BinaryTree<T> class shown in Example 11-6, which contains all of the nodes in a binary tree and lets you traverse it.

Example 11-6. Generic BinaryTree class

using System;
using System.Collections;
using System.Collections.Generic;


public class BinaryTree<T> : IEnumerable<T>
    where T: IComparable<T>
{
    public BinaryTree() {} public BinaryTree(T value) { BinaryTreeNode<T> node = new BinaryTreeNode<T>(value); root = node; counter = 1; } private int counter = 0; // Number of nodes in tree private BinaryTreeNode<T> root = null; // Pointer to root node in this tree public void AddNode(T value { BinaryTreeNode<T> node = new BinaryTreeNode<T>(value); ++counter; if (root == null) { root = node; } else { root.AddNode(node); } } public void AddNode(T value, int index) ...