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 ...Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access