关于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();
     }
   }

中序遍历二叉树

(0)

相关推荐

  • C#求解哈夫曼树,实例代码

    复制代码 代码如下: class HuffmanTree    {        private Node[] data;        public int LeafNum { get; set; }        public Node this[int index]        {            get { return data[index]; }            set { data[index] = value; }        }        public Hu

  • C# 递归查找树状目录实现方法

    1.递归查找树状目录 复制代码 代码如下: public partial class Form1 : Form    {        string path = @"F:\学习文件";//递归查找树状目录        public Form1()        {递归查找树状目录            InitializeComponent();        }        private void Form1_Load(object sender, EventArgs e) 

  • 一个很简单的jquery+xml+ajax的无刷新树结构(无css,后台是c#)

    复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Web.UI; using System.Web.UI.WebControls; using System.Data.Linq; using System.Xml; using System.Xml.Linq; namespace WebApplication3 { public

  • c#反射表达式树模糊搜索示例

    复制代码 代码如下: public static Expression<Func<T, bool>> GetSearchExpression<T>(string SearchString)        {            Expression<Func<T, bool>> filter = null; if (string.IsNullOrEmpty(SearchString)) return null;            var l

  • C#之Expression表达式树实例

    本文实例讲述了C#之Expression表达式树,分享给大家供大家参考.具体实现方法如下: 表达式树表示树状数据结构的代码,树状结构中的每个节点都是一个表达式,例如一个方法调用或类似 x < y 的二元运算 1.利用 Lambda 表达式创建表达式树 复制代码 代码如下: Expression<Func<int, int, int, int>> expr = (x, y, z) => (x + y) / z; 2.编译表达式树,该方法将表达式树表示的代码编译成一个可执行

  • C#通过KD树进行距离最近点的查找

    本文首先介绍Kd-Tree的构造方法,然后介绍Kd-Tree的搜索流程及代码实现,最后给出本人利用C#语言实现的二维KD树代码.这也是我自己动手实现的第一个树形的数据结构.理解上难免会有偏差,敬请各位多多斧正. 1. KD树介绍 Kd-Tree(KD树),即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最邻近查找和近似最邻近查找.我实现的KD树是二维的Kd - tree.目的是在点集中寻找最近点.参考资料是Kd-Tree的百度百科.并且根据百度

  • ASP.NET C#生成下拉列表树实现代码

    效果图: 代码: 复制代码 代码如下: using System.Data; using System.Web.UI.WebControls; /// <summary> /// 根据DataTable生成下拉列表树 /// </summary> public class DropDownListHelp { private string gridline; private DataTable dt; public DropDownListHelp() { // //TODO: 在

  • C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法

    本文实例讲述了C#使用前序遍历.中序遍历和后序遍历打印二叉树的方法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data;

  • C#实现获取系统目录并以Tree树叉显示的方法

    本文讲述C#获取Windows系统目录,如何目录遍历以及将信息捆绑在TreeView中显示出来的实现方法,具体实现代码如下: using System; using System.Drawing; using System.Collections; using System.ComponentModel; using System.Windows.Forms; using System.Data; using System.IO; namespace 获取系统目录 { public class

  • C# TreeView无限目录树实现方法

    本文实例讲述了C# TreeView无限目录树实现方法.分享给大家供大家参考,具体如下: #region 绑定客户树 protected void bindTreeView() { TreeView1.Nodes.Clear(); string userid = Session["UserID"].ToString(); string sqlwr = new SY_ADMINUSER().GetUserIDListByLoginUser(userid, "CUSTOMERSE

随机推荐