二叉排序树的C#实现

二叉排序树说起来其实并不是很难二叉查找树是一种把值比较小的节点存储在左子节点内而值比较大的节点存储在右子节点里的树其基本操作有以下几种

插入

我们对这个二叉树插入节点如果二叉树本身没有任何节点那么插入的这个节点就成为根节点否则根据定义你应该遍历树找出某一个节点如果带插入节点的值大于这个节点则成为带插入节点的右节点否则就是左节点从这里看来根节点本身就是一个树的节点因此我首先实现了一个TreeNode类型如下

: public class TreeNode<T>:IComparableIComparable<TreeNode<T>> {

:

: #region ctor 串联构造函数

:

: public TreeNode():this(default(T)nullnull){

: }

:

: public TreeNode(T value):this(valuenullnull) {

: }

:

: public TreeNode(T valueTreeNode<T> leftNodeTreeNode<T> rightNode):this(valueleftNoderightNode) {

: }

:

: public TreeNode(T value TreeNode<T> leftNode TreeNode<T> rightNode int deepness) {

: Value = value;

: LeftNode = leftNode;

: RightNode = rightNode;

: Deepness = deepness;

: IsLeaf = true;

: }

:

: public override string ToString() {

: return ValueToString();

: }

:

: #endregion

:

: #region Interface Members

:

: int IComparableCompareTo(Object item) {

: TreeNode<T> node = item as TreeNode<T>;

: if (node == null)

: throw new ArgumentException(Argument for comparing is not a object of TreeNode Type !!);

: else {

: if (this == item)

: return ;

: else {

: Comparer comparer = new Comparer(CultureInfoCurrentCulture);

: return comparerCompare(thisValue nodeValue);

: }

: }

: }

:

: int IComparable<TreeNode<T>>CompareTo(TreeNode<T> item) {

: if (item == null) {

: throw new ArgumentException(Argument for comparing is not a object of TreeNode Type !!);

: } else {

: if (this == item)

: return ;

: else {

: Comparer comparer = new Comparer(CultureInfoCurrentCulture);

: return comparerCompare(thisValue itemValue);

: }

: }

: }

: #endregion

:

: #region Properties

:

: public TreeNode<T> LeftNode {

: get;

: set;

: }

:

: public TreeNode<T> RightNode {

: get;

: set;

: }

:

: public TreeNode<T> FatherNode {

: get;

: set;

: }

:

: //这个属性是指数的层数也就是深度根的深度为

: public int Deepness {

: get;

: set;

: }

:

: //这个属性指示这个节点是不是叶子节点

: public bool IsLeaf {

: get;

: set;

: }

:

: //这个属性返回或者设置该节点的值

: public T Value {

: get;

: set;

: }

:

: #endregion

: }

接下来我们就能实现插入的功能了通常我觉得好的代码是自描述的也就是一段好的代码应该能自己描述自己的用途的

: public void Add(T itemValue) {

: if (Root == null) {

: TreeNode<T> root = new TreeNode<T>(itemValue);

: thisRoot = root;

: thisCount++;

: } else {

: TreeNode<T> _iterator = thisRoot;

: bool okFlag = true;;

: int deepness = ;

: int result = _comparerCompare(itemValue _iteratorValue); ;

:

: while (okFlag) {

: DebugWriteLine(Comaper Result is : + resultToString());

: DebugWriteLine();

: if (result > ) {

: if (_iteratorRightNode != null) {

: _iterator = _iteratorRightNode;

: result = _comparerCompare(itemValue _iteratorValue);

: deepness++;

: } else {

: //在添加节点的时候就设置该节点的深度而在计算整棵树的深度的时候其实只要对所有叶节点的深度的值进行排序就可以得到了

: _iteratorRightNode = new TreeNode<T>(itemValuenullnulldeepness);

: _iteratorIsLeaf = false;

: _iteratorRightNodeFatherNode = _iterator;

: Count++;

: okFlag = false;

: }

: } else if (result < ) {

: if (_iteratorLeftNode != null) {

: _iterator = _iteratorLeftNode;

: result = _comparerCompare(itemValue _iteratorValue);

: deepness++;

: } else {

: _iteratorLeftNode = new TreeNode<T>(itemValue null null deepness);

: _iteratorIsLeaf = false;

: _iteratorLeftNodeFatherNode = _iterator;

: Count++;

: okFlag = false;

: }

: } else

: okFlag = false;

: }

: }

: }

这里在比较的时候我是在全局设置了一个与本地文化相关的Comparer类型的私有成员_comparer这个类型用于对象判等关键是你要判断的对象必须实现IComparable 接口我编写的TreeNode类型就实现了这个接口了

查找

根据二叉搜索树的特点如果你要搜索的节点的值比当前节点值小那么就再搜索该节点的左子树否则搜索右子树这个过程是递归过程

如果找到匹配的节点返回ture;否则当前节点为Null然后又不等于你要搜索的节点的值那么就直接返回false我的实现如下

: public bool IsExit(T keyout TreeNode<T> node) {

: node = null;

: TreeNode<T> _iterator = Root;

: int result = _comparerCompare(key _iteratorValue);

: bool okFlag = true;

: while (okFlag) {

: if (result == ) {

: okFlag = false;

: node = _iterator;//如果找到这个叶子结点那么得到叶子节点的指针

: return true;

: } else if (result > ) {

: _iterator = _iteratorRightNode;

: if (_iterator != null)

: result = _comparerCompare(key _iteratorValue);

: else {

: okFlag = false;

: return false;

: }

: } else {

: _iterator = _iteratorLeftNode;

: if (_iterator != null)

: result = _comparerCompare(key _iteratorValue);

: else {

: okFlag = false;

: return false;

: }

: }

: }

: return false;

: }

遍历

这个分三种情况的遍历分别是前根遍历中根遍历后根遍历其实很简单就是按照访问节点的顺序来划分的如果先访问左子节点然后访问父节点最后在访问右节点这个情况就是前序遍历其他的情况以此类推这里我实现的时候是用递归的方式

: /// <summary>

: /// 中根遍历树

: /// </summary>

: /// <param name=root></param>

: public void InOrder(TreeNode<T> root) {

: if (root != null) {

: InOrder(rootLeftNode);

: ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

: InOrder(rootRightNode);

: }

: }

:

: /// <summary>

: /// 先根遍历树

: /// </summary>

: /// <param name=root></param>

: public void PreOrder(TreeNode<T> root) {

: if (root != null) {

: ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

: PreOrder(rootLeftNode);

: PreOrder(rootRightNode);

: }

: }

:

: /// <summary>

: /// 后根遍历树

: /// </summary>

: /// <param name=root></param>

: public void PostOrder(TreeNode<T> root) {

: if (root != null) {

: PostOrder(rootLeftNode);

: PostOrder(rootRightNode);

: stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString());

: }

: }

删除节点

作为这个树的实现里面最有难度的地方要考虑三种情况

要删除的节点时叶子结点这个情况很好解决直接删掉就好了

要删除的节点只有一个子节点这个情况也很好解决子节点替换一下父节点问题解决

要删除的节点有两个节点这个就比较复杂了一些但我们仔细分析就会发现要删除这个节点只要利用中根遍历得到直接前驱或者直接后继结点代替该节点就可以了同时你还要删除前驱或者后继这个节点而这两个节点一定符合前面的两种情况之一

: public void Remove(T key) {

: TreeNode<T> node;

: bool isExit = IsExit(key out node);

: if (!isExit) {

: return;

: } else {

: if (IsLeafNode(node)) {

: if (nodeFatherNodeLeftNode == node)

: nodeFatherNodeLeftNode = null;

: else

: nodeFatherNodeRightNode = null;

: if (node != null) node = null;

: } else {

: if (!HasTwoLeafNodes(node)) {

: TreeNode<T> child = GetUniqueChild(node);

: if (nodeFatherNodeLeftNode == node) {

: nodeFatherNodeLeftNode = child;

: } else {

: if (nodeLeftNode != null)

: nodeFatherNodeRightNode = child;

: }

: if (node != null) node = null;

: } else {

: //首先找到后继结点

: TreeNode<T> successor = GetSuccessor(node);

: //调整节点值这个时候有一个值得注意的地方比如你的树是这样的情况

: /* 或者

: * \ /

: *

: * / \ / \

: * / \

: * / \ /

: * / \ / \

: *

: * \

: *

: */

: //树A中节点相应的后继结点应该是那么的左子节点应调整成就要调整成

: nodeValue = successorValue;

: Remove(successor);

: }

: }

: thisCount;

: }

: }

以下是完整的代码尽管是泛型但其实我仅仅使用int类型编写 过测试如果其他的类型我想只要是实现了IComparable接口应该就能正常工作

: using System;

: using SystemCollections;

: using SystemCollectionsGeneric;

: using SystemGlobalization;

: using SystemDiagnostics;

: using SystemText;

:

: namespace Ultis {

: public class BinaryTree<T> {

: #region ctor

:

: static BinaryTree() {

: _comparer = new Comparer(CultureInfoCurrentCulture);

: }

:

: public BinaryTree() {

: thisRoot = null;

: thisCount = ;

: this_deepness = ;

: }

:

: public BinaryTree(TreeNode<T> root) {

: if (root == null) {

: throw new ArgumentException(Root can not be null !!);

: }

: thisRoot = root;

: thisCount++;

: this_deepness = ;

: }

: #endregion

:

: #region Public Members

:

: /// <summary>

: ///

: /// </summary>

: /// <param name=itemValue></param>

: public void Add(T itemValue) {

: if (Root == null) {

: TreeNode<T> root = new TreeNode<T>(itemValue);

: thisRoot = root;

: thisCount++;

: } else {

: TreeNode<T> _iterator = thisRoot;

: bool okFlag = true;;

: int deepness = ;

: int result = _comparerCompare(itemValue _iteratorValue); ;

:

: while (okFlag) {

: DebugWriteLine(Comaper Result is : + resultToString());

: DebugWriteLine();

: if (result > ) {

: if (_iteratorRightNode != null) {

: _iterator = _iteratorRightNode;

: result = _comparerCompare(itemValue _iteratorValue);

: deepness++;

: } else {

: //在添加节点的时候就设置该节点的深度而在计算整棵树的深度的时候其实只要对所有叶节点的深度的值进行排序就可以得到了

: _iteratorRightNode = new TreeNode<T>(itemValuenullnulldeepness);

: _iteratorIsLeaf = false;

: _iteratorRightNodeFatherNode = _iterator;

: Count++;

: okFlag = false;

: }

: } else if (result < ) {

: if (_iteratorLeftNode != null) {

: _iterator = _iteratorLeftNode;

: result = _comparerCompare(itemValue _iteratorValue);

: deepness++;

: } else {

: _iteratorLeftNode = new TreeNode<T>(itemValue null null deepness);

: _iteratorIsLeaf = false;

: _iteratorLeftNodeFatherNode = _iterator;

: Count++;

: okFlag = false;

: }

: } else

: okFlag = false;

: }

: }

: }

:

: /// <summary>

: /// 从树中移出一个节点要考虑很多情况比如要删除的节点没有子节点有一个子节点有两个子节点

: /// PS:这个方法应进行测试

: /// </summary>

: /**

: * 删除指定的节点实现

: *

: * 算法思想

: *

: * 若待删除的节点p是叶子节点则直接删除该节点

: *

: * 若待删除的节点p只有一个子节点则将p的子节点与p的父节点直接连接然后删除节点p

: * 为什么只有一个子节点时可以直接接到删除节点的父节点下面呢?因为只有一个子节点直接接上

: * 去不会影响排序子节点本身的排序当然更不会影响另外一个子树（因为另一子树跟本不存在!）

: *

: * 若待删除节点p有两个子节点时应该使用中序遍历方式得到的直接前置节点S或直接后继节点s

: * 的值来代替点s的值然后删除节点s（注节点s肯定属于上述情况之一）而不是直接删除

: * p这样可以将该删除问题转换成上面问题

: */

: public void Remove(T key) {

: TreeNode<T> node;

: bool isExit = IsExit(key out node);

: if (!isExit) {

: return;

: } else {

: if (IsLeafNode(node)) {

: if (nodeFatherNodeLeftNode == node)

: nodeFatherNodeLeftNode = null;

: else

: nodeFatherNodeRightNode = null;

: if (node != null) node = null;

: } else {

: if (!HasTwoLeafNodes(node)) {

: TreeNode<T> child = GetUniqueChild(node);

: if (nodeFatherNodeLeftNode == node) {

: nodeFatherNodeLeftNode = child;

: } else {

: if (nodeLeftNode != null)

: nodeFatherNodeRightNode = child;

: }

: if (node != null) node = null;

: } else {

: //首先找到后继结点

: TreeNode<T> successor = GetSuccessor(node);

: //调整节点值这个时候有一个值得注意的地方比如你的树是这样的情况

: /* 或者

: * \ /

: *

: * / \ / \

: * / \

: * / \ /

: * / \ / \

: *

: * \

: *

: */

: //树A中节点相应的后继结点应该是那么的左子节点应调整成就要调整成

: nodeValue = successorValue;

: Remove(successor);

: }

: }

: thisCount;

: }

: }

:

:

: /**

: * 删除指定的节点实现

: *

: * 算法思想

: *

: * 若待删除的节点p是叶子节点则直接删除该节点

: *

: * 若待删除的节点p只有一个子节点则将p的子节点与p的父节点直接连接然后删除节点p

: * 为什么只有一个子节点时可以直接接到删除节点的父节点下面呢?因为只有一个子节点直接接上

: * 去不会影响排序子节点本身的排序当然更不会影响另外一个子树（因为另一子树跟本不存在!）

: *

: * 若待删除节点p有两个子节点时应该使用中序遍历方式得到的直接前置节点S或直接后继节点s

: * 的值来代替点s的值然后删除节点s（注节点s肯定属于上述情况之一）而不是直接删除

: * p这样可以将该删除问题转换成上面问题

: */

: public void Remove(TreeNode<T> node) {

: if (IsLeafNode(node)) {

: if (nodeFatherNodeLeftNode == node)

: nodeFatherNodeLeftNode = null;

: else

: nodeFatherNodeRightNode = null;

: if (node != null) node = null;

: } else {

: if (!HasTwoLeafNodes(node)) {

: TreeNode<T> child = GetUniqueChild(node);

: if (nodeFatherNodeLeftNode == node) {

: nodeFatherNodeLeftNode = child;

: } else {

: nodeFatherNodeRightNode = child;

: }

: if(node != null) node = null;

: } else {

: //要删除的节点有两个子节点

: TreeNode<T> successor = GetSuccessor(node);

: nodeValue = successorValue;

: Remove(successor); //删除相应的后继结点

: if (successor != null) successor = null;

: }

: }

: thisCount;

: }

:

: /// <summary>

: /// 返回某一节点唯一的一个节点

: /// </summary>

: /// <param name=node></param>

: /// <returns></returns>

: private TreeNode<T> GetUniqueChild(TreeNode<T> node) {

: TreeNode<T> child;

: if (nodeLeftNode != null)

: child = nodeLeftNode;

: else

: child = nodeRightNode;

: return child;

: }

:

: /// <summary>

: /// 根据中根遍历来得到相应的后继结点仍然还有BUG存在！

: /// </summary>

: /// <param name=value></param>

: /// <returns></returns>

: public TreeNode<T> GetSuccessor(T value) {

: throw new NotImplementedException(This function is not complete yet !);

: IComparable icomparable = Root as IComparable;

: TreeNode<T> wanted = new TreeNode<T>(value);

: if (icomparableCompareTo(wanted) == ) {

: return Root;

: } else {

: TreeNode<T> node;

: if (IsExit(value out node)) {

: if (IsLeafNode(node)) { //如果是叶子节点那么应该做么做才能返回正确的后继节点？

: return null;

: }else

: return GetSuccessor(node); //如果是非叶子节点则调用相应的方法返回非叶子节点的后继结点

: } else

: return null;

: }

: }

:

: /// <summary>

: /// 中根遍历树

: /// </summary>

: /// <param name=root></param>

: public void InOrder(TreeNode<T> root) {

: if (root != null) {

: InOrder(rootLeftNode);

: ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

: InOrder(rootRightNode);

: }

: }

:

: /// <summary>

: /// 先根遍历树

: /// </summary>

: /// <param name=root></param>

: public void PreOrder(TreeNode<T> root) {

: if (root != null) {

: ConsoleWriteLine(stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString()));

: PreOrder(rootLeftNode);

: PreOrder(rootRightNode);

: }

: }

:

: /// <summary>

: /// 后根遍历树

: /// </summary>

: /// <param name=root></param>

: public void PostOrder(TreeNode<T> root) {

: if (root != null) {

: PostOrder(rootLeftNode);

: PostOrder(rootRightNode);

: stringFormat(This nodes value is {} and its deepness is {}leaf:{} rootToString() rootDeepnessToString() rootIsLeafToString());

: }

: }

:

: /// <summary>

: /// 返回具有最大节点值的树节点

: /// </summary>

: /// <returns></returns>

: public TreeNode<T> GetMaxNode() {

: TreeNode<T> _iterator = Root;

: while (_iteratorRightNode != null) {

: _iterator = _iteratorRightNode;

: }

: return _iterator;

: }

:

: /// <summary>

: /// 返回最大的值

: /// </summary>

: /// <returns></returns>

: public T GetMaxValue() {

: return GetMaxNode()Value;

: }

:

: /// <summary>

: /// 返回具有最小节点值得节点

: /// </summary>

: /// <returns></returns>

: public TreeNode<T> GetMinNode() {

: TreeNode<T> _iterator = Root;

: while (_iteratorLeftNode != null) {

: _iterator = _iteratorLeftNode;

: }

: return _iterator;

: }

:

: /// <summary>

: /// 返回最小值

: /// </summary>

: /// <returns></returns>

: public T GetMinValue() {

: return GetMinNode()Value;

: }

:

: public bool IsExit(T keyout TreeNode<T> node) {

: node = null;

: TreeNode<T> _iterator = Root;

: int result = _comparerCompare(key _iteratorValue);

: bool okFlag = true;

: while (okFlag) {

: if (result == ) {

: okFlag = false;

: node = _iterator;//如果找到这个叶子结点那么得到叶子节点的指针

: return true;

: } else if (result > ) {

: _iterator = _iteratorRightNode;

: if (_iterator != null)

: result = _comparerCompare(key _iteratorValue);

: else {

: okFlag = false;

: return false;

: }

: } else {

: _iterator = _iteratorLeftNode;

: if (_iterator != null)

: result = _comparerCompare(key _iteratorValue);

: else {

: okFlag = false;

: return false;

: }

: }

: }

: return false;

: }

:

: public override string ToString() {

: string rtnString = stringFormat(This is a kind of binary tree that impleted by Master and it has {} nodes CountToString());

: return rtnString;

: }

:

: public TreeNode<T> Root {

: get;

: set;

: }

:

: public int Count {

: get;

: private set;

: }

:

: //返回树的深度

: public int Deepness {

: get {

: if (Count == )

: return ;

: else {

: int[] _deepnessSortArray = new int[Count];

: int pointer = Count ;

: for (int i = ; i < Count; i++) _deepnessSortArray[i] = ;

: InOrder(Root ref pointer ref _deepnessSortArray);

: ArraySort<int>(_deepnessSortArray); //对_deepnessSortArray进行排序得出其中最大的数值就是该树的深度

: return _deepnessSortArray[Count ];

: }

: }

: }

:

: #endregion

:

: #region Private Members

:

: private static Comparer _comparer;

:

: private int _deepness;

:

: /// <summary>

: /// 遍历树节点然后给深度数组_deepnessSortArray[i]赋值之后对这个数组进行排序得到的最大值就是该树的深度

: /// </summary>

: /// <param name=root></param>

: /// <param name=pointer></param>

: /// <param name=deepnessSortArray></param>

: private void InOrder(TreeNode<T> rootref int pointerref int[] deepnessSortArray) {

: if (root != null) {

: InOrder(rootLeftNoderef pointerref deepnessSortArray);

: deepnessSortArray[pointer] = rootDeepness;

: pointer;

: InOrder(rootRightNoderef pointer ref deepnessSortArray);

: }

: }

:

: /// <summary>

: /// 基于中根遍历的算法来得到某一个非叶子节点的后继结点

: /// </summary>

: /// <param name=wannaDelNode></param>

: private TreeNode<T> GetSuccessor(TreeNode<T> wannaDelNode) {

: TreeNode<T> _iterator = wannaDelNodeRightNode;

: TreeNode<T> successorFather = null;

: TreeNode<T> successor = null;

:

: //DebugWriteLine(stringFormat(_iterators value is {} _iteratorValueToString()));

: //DebugWriteLine(stringFormat(successors value is {} successorValueToString()));

: //首先应该要判断是不是叶子节点如果是叶子节点情况就完全不一样了

: while (_iterator != null) {

: successorFather = _iteratorFatherNode;

: successor = _iterator;

: _iterator = _iteratorLeftNode;

: }

: return successor;

: }

:

: private bool IsLeafNode(TreeNode<T> node) {

: return (nodeLeftNode == null && nodeRightNode == null) ? true : false;

: }

:

: private bool HasTwoLeafNodes(TreeNode<T> node) {

: return (nodeLeftNode != null && nodeRightNode != null) ? true : false;

: }

:

: #endregion

: }

: }