关于c#二叉树的实现

本篇纯属娱乐，源于整理代码，发现还曾实现过遍历二叉树。

虽然.net/c#中的各种集合类已经实现了最优的排序设计，但了解基本的算法实现有助于软件开发中的各种权衡和选择。
比如，如果你实现过b+树排序和查找，并将树节点序列化至二进制文件块，则你应该已经了解了各种数据库索引的基本设计。

什么是二叉树？
http://en.wikipedia.org/wiki/binary_tree

二叉树节点类定义

view code
   /// <summary>
   /// 二叉树节点
   /// </summary>
   /// <typeparam name="t">the item type</typeparam>
   public class binarytreenode<t>
   {
     #region constructors

     /// <summary>
     /// 二叉树节点
     /// </summary>
     public binarytreenode()
     {
     }

     /// <summary>
     /// 二叉树节点
     /// </summary>
     /// <param name="value">节点中的值</param>
     public binarytreenode(t value)
     {
       this.value = value;
     }

     /// <summary>
     /// 二叉树节点
     /// </summary>
     /// <param name="value">节点中的值</param>
     /// <param name="parent">节点的父节点</param>
     public binarytreenode(t value, binarytreenode<t> parent)
     {
       this.value = value;
       this.parent = parent;
     }

     /// <summary>
     /// 二叉树节点
     /// </summary>
     /// <param name="value">节点中的值</param>
     /// <param name="parent">节点的父节点</param>
     /// <param name="left">节点的左节点</param>
     /// <param name="right">节点的右节点</param>
     public binarytreenode(t value,
       binarytreenode<t> parent,
       binarytreenode<t> left,
       binarytreenode<t> right)
     {
       this.value = value;
       this.right = right;
       this.left = left;
       this.parent = parent;
     }

     #endregion

     #region properties

     /// <summary>
     /// 节点值
     /// </summary>
     public t value { get; set; }

     /// <summary>
     /// 父节点
     /// </summary>
     public binarytreenode<t> parent { get; set; }

     /// <summary>
     /// 左节点
     /// </summary>
     public binarytreenode<t> left { get; set; }

     /// <summary>
     /// 右节点
     /// </summary>
     public binarytreenode<t> right { get; set; }

     /// <summary>
     /// 是否为根节点
     /// </summary>
     public bool isroot { get { return parent == null; } }

     /// <summary>
     /// 是否为叶子节点
     /// </summary>
     public bool isleaf { get { return left == null && right == null; } }

     /// <summary>
     /// 是否为可访问的
     /// </summary>
     internal bool visited { get; set; }

     #endregion

     #region public overridden functions

     /// <summary>
     /// returns a <see cref="system.string"/> that represents this instance.
     /// </summary>
     /// <returns>
     /// a <see cref="system.string"/> that represents this instance.
     /// </returns>
     public override string tostring()
     {
       return value.tostring();
     }

     #endregion
   }

二叉树类实现

view code
   /// <summary>
   /// 二叉树
   /// </summary>
   /// <typeparam name="t">二叉树中节点内容类型</typeparam>
   [suppressmessage("microsoft.naming", "ca1710:identifiersshouldhavecorrectsuffix")]
   public class binarytree<t> : icollection<t>, ienumerable<t> where t : icomparable<t>
   {
     #region constructor

     /// <summary>
     /// 二叉树
     /// </summary>
     public binarytree()
     {
       numberofnodes = 0;
     }

     /// <summary>
     /// 二叉树
     /// </summary>
     /// <param name="root">二叉树根节点</param>
     public binarytree(binarytreenode<t> root)
       : this()
     {
       this.root = root;
     }

     #endregion

     #region properties

     /// <summary>
     /// 树的根节点
     /// </summary>
     public binarytreenode<t> root { get; set; }

     /// <summary>
     /// 树中节点的数量
     /// </summary>
     protected int numberofnodes { get; set; }

     /// <summary>
     /// 树是否为空
     /// </summary>
     public bool isempty { get { return root == null; } }

     /// <summary>
     /// 获取树中节点的最小值
     /// </summary>
     public t minvalue
     {
       get
       {
         if (isempty)
           return default(t);

         binarytreenode<t> minnode = root;
         while (minnode.left != null)
           minnode = minnode.left;

         return minnode.value;
       }
     }

     /// <summary>
     /// 获取树中节点的最大值
     /// </summary>
     public t maxvalue
     {
       get
       {
         if (isempty)
           return default(t);

         binarytreenode<t> maxnode = root;
         while (maxnode.right != null)
           maxnode = maxnode.right;

         return maxnode.value;
       }
     }

     #endregion

     #region ienumerable<t> members

     /// <summary>
     /// returns an enumerator that iterates through the collection.
     /// </summary>
     /// <returns>
     /// a <see cref="t:system.collections.generic.ienumerator`1"></see>
     /// that can be used to iterate through the collection.
     /// </returns>
     public ienumerator<t> getenumerator()
     {
       foreach (binarytreenode<t> node in traverse(root))
       {
         yield return node.value;
       }
     }

     #endregion

     #region ienumerable members

     /// <summary>
     /// returns an enumerator that iterates through a collection.
     /// </summary>
     /// <returns>
     /// an <see cref="t:system.collections.ienumerator"/>
     /// object that can be used to iterate through the collection.
     /// </returns>
     ienumerator ienumerable.getenumerator()
     {
       foreach (binarytreenode<t> node in traverse(root))
       {
         yield return node.value;
       }
     }

     #endregion

     #region icollection<t> members

     /// <summary>
     /// 新增节点
     /// </summary>
     /// <param name="item">the object to add to the
     /// <see cref="t:system.collections.generic.icollection`1"></see>.</param>
     /// <exception cref="t:system.notsupportedexception">the
     /// <see cref="t:system.collections.generic.icollection`1"></see>
     /// is read-only.</exception>
     public void add(t item)
     {
       if (root == null)
       {
         root = new binarytreenode<t>(item);
         ++numberofnodes;
       }
       else
       {
         insert(item);
       }
     }

     /// <summary>
     /// 清除树
     /// </summary>
     public void clear()
     {
       root = null;
     }

     /// <summary>
     /// 树中是否包含此节点
     /// </summary>
     /// <param name="item">the object to locate in the
     /// <see cref="t:system.collections.generic.icollection`1"></see>.</param>
     /// <returns>
     /// true if item is found in the
     /// <see cref="t:system.collections.generic.icollection`1"></see>; otherwise, false.
     /// </returns>
     public bool contains(t item)
     {
       if (isempty)
         return false;

       binarytreenode<t> currentnode = root;
       while (currentnode != null)
       {
         int comparedvalue = currentnode.value.compareto(item);
         if (comparedvalue == 0)
           return true;
         else if (comparedvalue < 0)
           currentnode = currentnode.left;
         else
           currentnode = currentnode.right;
       }

       return false;
     }

     /// <summary>
     /// 将树中节点拷贝至目标数组
     /// </summary>
     /// <param name="array">the array.</param>
     /// <param name="arrayindex">index of the array.</param>
     public void copyto(t[] array, int arrayindex)
     {
       t[] temparray = new t[numberofnodes];
       int counter = 0;
       foreach (t value in this)
       {
         temparray[counter] = value;
         ++counter;
       }
       array.copy(temparray, 0, array, arrayindex, count);
     }

     /// <summary>
     /// 树中节点的数量
     /// </summary>
     public int count
     {
       get { return numberofnodes; }
     }

     /// <summary>
     /// 树是否为只读
     /// </summary>
     public bool isreadonly
     {
       get { return false; }
     }

     /// <summary>
     /// 移除节点
     /// </summary>
     /// <param name="item">节点值</param>
     /// <returns>是否移除成功</returns>
     public bool remove(t item)
     {
       binarytreenode<t> node = find(item);
       if (node == null)
         return false;

       list<t> values = new list<t>();
       foreach (binarytreenode<t> l in traverse(node.left))
       {
         values.add(l.value);
       }
       foreach (binarytreenode<t> r in traverse(node.right))
       {
         values.add(r.value);
       }

       if (node.parent.left == node)
       {
         node.parent.left = null;
       }
       else
       {
         node.parent.right = null;
       }

       node.parent = null;

       foreach (t v in values)
       {
         this.add(v);
       }

       return true;
     }

     #endregion

     #region private functions

     /// <summary>
     /// 查找指定值的节点
     /// </summary>
     /// <param name="value">指定值</param>
     /// <returns>
     /// 指定值的节点
     /// </returns>
     protected binarytreenode<t> find(t value)
     {
       foreach (binarytreenode<t> node in traverse(root))
         if (node.value.equals(value))
           return node;
       return null;
     }

     /// <summary>
     /// 遍历树
     /// </summary>
     /// <param name="node">遍历搜索的起始节点</param>
     /// <returns>
     /// the individual items from the tree
     /// </returns>
     [suppressmessage("microsoft.design", "ca1006:donotnestgenerictypesinmembersignatures")]
     protected ienumerable<binarytreenode<t>> traverse(binarytreenode<t> node)
     {
       // 遍历左子树
       if (node.left != null)
       {
         foreach (binarytreenode<t> left in traverse(node.left))
           yield return left;
       }

       // 中序遍历二叉树, 顺序是 左子树，根，右子树
       yield return node;

       // 遍历右子树
       if (node.right != null)
       {
         foreach (binarytreenode<t> right in traverse(node.right))
           yield return right;
       }
     }

     /// <summary>
     /// 插入节点
     /// </summary>
     /// <param name="value">插入的节点值</param>
     protected void insert(t value)
     {
       // 从根节点开始比较
       binarytreenode<t> currentnode = root;

       while (true)
       {
         if (currentnode == null)
           throw new invalidprogramexception("the current tree node cannot be null.");

         // 比较当前节点与新节点的值
         int comparedvalue = currentnode.value.compareto(value);
         if (comparedvalue < 0)
         {
           // 当前节点值小于新节点值
           if (currentnode.left == null)
           {
             currentnode.left = new binarytreenode<t>(value, currentnode);
             ++numberofnodes;
             return;
           }
           else
           {
             currentnode = currentnode.left;
           }
         }
         else if (comparedvalue > 0)
         {
           // 当前节点值大于新节点值
           if (currentnode.right == null)
           {
             currentnode.right = new binarytreenode<t>(value, currentnode);
             ++numberofnodes;
             return;
           }
           else
           {
             currentnode = currentnode.right;
           }
         }
         else
         {
           // 当前节点值等于新节点值
           currentnode = currentnode.right;
         }
       }
     }

     #endregion
   }

使用举例

class program
   {
     static void main(string[] args)
     {
       console.foregroundcolor = consolecolor.green;

       binarytree<string> tree = new binarytree<string>();
       tree.add("dennis");
       tree.add("gao");
       tree.add("is");
       tree.add("a");
       tree.add("c#");
       tree.add("programmer");

       console.writeline("root node is : " + tree.root.tostring());
       console.writeline();

       foreach (var node in tree)
       {
         console.writeline(node);
       }

       console.readkey();
     }
   }

中序遍历二叉树