闲着无事，写写二叉查找树用C#的简单实现。
二叉查找树是二叉树的一种特别类型，特点是小值在父节点的左边，其余值在其右边，对排序、值查找有很好的支持。据说应用很广泛，但是我还没在项目中用到过。
1，结构分析
树由节点组成，首先对节点结构进行分析。这里使用双向链表的思想来确定节点与节点间的关系。
a，属性：
1，父级节点
2，左子节点
3，右子节点
4，节点数据
为了方便，还加上HasChild属性、重写ToString方法。下面是泛型代码：
public class TreeNode
{ public T Data { get; set; } public TreeNode Parent { get; set; } public TreeNode Left { get; set; } public TreeNode Right { get; set; } public bool HasChild { get { if (this.Left != null || this.Right != null) { return true; } return false; } } public override string ToString() { return string.Format("Data:{0} Parent:{1} Left:{2} Right:{3} HasChild:{4}", Data,
Parent == null ? "null" : Parent.Data.ToString(), Left == null ? "null" : Left.Data.ToString(),
Right == null ? "null" : Right.Data.ToString(), HasChild.ToString()); } }
然后，对树本身结构进行分析。为了防止数据结构在外部被破坏，3个属性都为只读。
a，私有字段：
1，根节点
a，只读属性：
1，节点数量
2，最大值
3，最小值
b，方法
1，插入
2，查找
3，删除
5，遍历
2，算法分析
插入：
a，如果根节点为null，设为根节点。
b，把根节点设为当前节点，如果新节点的值小于当前节点的值，把当前节点设为当前节点的左子节点。反侧，设为其右子节点。直到当前节点的左（右）子节点为null，把新节点插入到这个位置，并把新节点的父级节点设为当前节点。
c，节点数量加1。
public void Insert(T item) { TreeNode node = new TreeNode() { Data = item }; if (root == null) { root = node; } else { TreeNode current = root; while (current != null) { if (current.Data.CompareTo(item) > -1) { if (current.Left == null) { node.Parent = current; current.Left = node; current = null; } else { current = current.Left; } } else { if (current.Right == null) { node.Parent = current; current.Right = node; current = null; } else { current = current.Right; } } } } count++; }
最大值、最小值：二叉查找树找最大值和最小值是再容易不过的事了，最底层最左的节点有最小值，最右的节点有最大值。
public T Min { get { TreeNode current = root; while (current.Left != null) { current = current.Left; } return current.Data; } } public T Max { get { TreeNode current = root; while (current.Right != null) { current = current.Right; } return current.Data; } }
查找特定值：
a，把根节点设为当前节点，如果查找值等于当前节点的值，返回当前节点。
b，如果查找的值小于当前节点的值，把当前节点设为其右子节点。反侧，设为其左子节点。直到当前节点为null，返回null。
public TreeNode Find(T item) { TreeNode current = root; while (!current.Data.Equals(item)) { if (current.Data.CompareTo(item) < 0) { current = current.Right; } else { current = current.Left; } if (current == null) { return null; } } return current; }
遍历：
二叉查找树常用的3种遍历方法：中序遍历、先序遍历和后序遍历。中序遍历是按照值的升序顺序访问所有节点的，虽然我很想写清楚这3个方法，无赖语文不怎么好，直接上代码吧。
/// /// 中序遍历 /// ///
private void InOrder(TreeNode node) { if (node != null) { InOrder(node.Left); Console.Write(node.Data.ToString() + " "); InOrder(node.Right); } } /// /// 先序遍历 /// ///
private void PreOrder(TreeNode node) { if (node != null) { Console.Write(node.Data.ToString() + " "); InOrder(node.Left); InOrder(node.Right); } } /// /// 后序遍历 /// ///
private void PostOrder(TreeNode node) { if (node != null) { InOrder(node.Left); InOrder(node.Right); Console.Write(node.Data.ToString() + " "); } }
删除：
由于二叉查找树特殊的结构，删除时需要对树进行重构，因此删除算法是比较复杂的。
a，要删除的节点如果没有子节点，直接删除（去除引用）。
b，如果有一个子节点，用子节点顶替该节点位置。
c，如果有两个子节点，使用中序遍历，用该节点的右子节点的最左节点顶替该节点位置。
d，节点数量减1。
其实删除和顶替，还可以分解为更细的算法步骤，为了理解，所以就不说那么细，直接看代码：
public void Remove(T item) { TreeNode current = this.Find(item); if (current == null) { return; } this.count--; bool isLeftNode = false; if (current != root) { isLeftNode = current.Parent.Data.CompareTo(item) == 1; } if (current.HasChild) { if (current.Left != null && current.Right != null) { TreeNode temp = current.Right; TreeNode node = current.Right; while (temp != null) { node = temp; temp = temp.Left; } if (node.HasChild) { node.Right.Parent = node.Parent; node.Parent.Left = node.Right; } else { node.Parent.Left = null; } node.Parent = current.Parent; if (node != current.Right) { node.Right = current.Right; current.Right.Parent = node; } node.Left = current.Left; current.Left.Parent = node; if (current != root) { if (isLeftNode) { current.Parent.Left = node; } else { current.Parent.Right = node; } } else { this.root = node; } } else { if (current == root) { this.root = current.Left == null ? current.Right : current.Left; } else { if (isLeftNode) { current.Parent.Left = current.Left == null ? current.Right : current.Left; } else { current.Parent.Right = current.Right == null ? current.Left : current.Right; } } } } else { if (current == this.root) { this.root = null; } else if (isLeftNode) { current.Parent.Left = null; } else { current.Parent.Right = null; } } }
延伸阅读
最新评论