`
feipigwang
  • 浏览: 739104 次
  • 性别: Icon_minigender_2
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

排序二叉树C#实现

 
阅读更多

很久以前写的,现在贴出来交流一下。

先看排序二叉树的接口

public interface ISorttedBinaryTree
{
void InsertElement(IComparable val) ;//如果树中有一个节点的值等于val的值,则val将被忽略
void RemoveElement(IComparable val) ;
bool ContainsElement(IComparable var) ;
ArrayList GetAllNodesAscend(bool ascend) ;//ArrayList 中是Node
//遍历二叉树
ArrayList Traverse(TraverseMode mode) ; //ArrayList 中是Node

IComparable MaxElement {get ;}
IComparable MinElement {get ;}
Node Root {get ;}
int Depth {get ;}
int Count {get ;}
}

//VS2003实现,不支持泛型
public class Node
{
public IComparable val ;
public Node leftChild ;
public Node rightChild ;
}

//遍历模式
public enum TraverseMode
{
PreOrder ,MidOrder ,PostOrder
}

再看整个二叉树的实现:

public class SorttedBinaryTree :ISorttedBinaryTree
{
private Node root = null ;
public SorttedBinaryTree()
{
}

#region ISorttedBinaryTree 接口实现
#region InsertElement
//如果树中有一个节点的值等于val的值,则val将被忽略
public void InsertElement(IComparable val)
{
Node node = new Node() ;
node.val = val ;

if(this.root == null)
{
this.root = node ;
return ;
}

this.DoInsert(node ,this.root) ;
}
#endregion

#region RemoveElement
public void RemoveElement(IComparable val)
{
IAndFather iAndFather = this.SearchElement(val) ;
if(iAndFather == null)
{
return ;
}

this.RemoveRoot(iAndFather) ;

}
#endregion

#region ContainsElement
public bool ContainsElement(IComparable var)
{
IAndFather iAndFather = this.SearchElement(var) ;
return (iAndFather == null) ;
}
#endregion

#region property
public int Depth
{
get
{
return this.GetDepth() ;
}
}

public IComparable MaxElement
{
get
{
if(this.root == null)
{
return null ;
}

Node node = this.root ;

while(node.rightChild != null)
{
node = node.rightChild ;
}

return node.val ;
}
}


public Node Root
{
get
{
return this.root ;
}
}


public IComparable MinElement
{
get
{
if(this.root == null)
{
return null ;
}

Node node = this.root ;

while(node.leftChild != null)
{
node = node.leftChild ;
}

return node.val ;
}
}


public int Count
{
get
{
if(this.root == null)
{
return 0 ;
}

int count = 1 ;
this.CountAllNodes(this.root ,ref count) ;

return count ;
}
}



#endregion

#region GetAllNodesAscend
//非深拷贝 ,外部不得改变得到的各个元素的值
public ArrayList GetAllNodesAscend(bool ascend)
{
ArrayList list = new ArrayList() ;
this.DoGetAllNodes(this.root ,ascend ,ref list ,TraverseMode.MidOrder) ;

return list ;
}

private void DoGetAllNodes(Node childTreeRoot ,bool ascend ,ref ArrayList list ,TraverseMode mode)
{
if(childTreeRoot == null)
{
return ;
}

//中序遍历
if(mode == TraverseMode.MidOrder)
{
if(ascend)
{
this.DoGetAllNodes(childTreeRoot.leftChild ,ascend ,ref list ,mode) ;
list.Add(childTreeRoot) ;
this.DoGetAllNodes(childTreeRoot.rightChild ,ascend ,ref list ,mode) ;
}
else
{
this.DoGetAllNodes(childTreeRoot.rightChild ,ascend ,ref list ,mode) ;
list.Add(childTreeRoot) ;
this.DoGetAllNodes(childTreeRoot.leftChild ,ascend ,ref list ,mode) ;
}
}
else if(mode == TraverseMode.PreOrder)
{
list.Add(childTreeRoot) ;
this.DoGetAllNodes(childTreeRoot.leftChild ,ascend ,ref list ,mode) ;
this.DoGetAllNodes(childTreeRoot.rightChild ,ascend ,ref list ,mode) ;
}
else
{
this.DoGetAllNodes(childTreeRoot.leftChild ,ascend ,ref list ,mode) ;
this.DoGetAllNodes(childTreeRoot.rightChild ,ascend ,ref list ,mode) ;
list.Add(childTreeRoot) ;
}
}
#endregion

#region Traverse
public ArrayList Traverse(TraverseMode mode)
{
ArrayList list = new ArrayList() ;
switch(mode)
{
case TraverseMode.MidOrder :
{
this.DoGetAllNodes(this.root ,true ,ref list ,TraverseMode.MidOrder) ;
return list ;
}
case TraverseMode.PreOrder :
{
this.DoGetAllNodes(this.root ,true ,ref list ,TraverseMode.PreOrder) ;
return list ;
}
case TraverseMode.PostOrder :
{
this.DoGetAllNodes(this.root ,true ,ref list ,TraverseMode.PostOrder) ;
return list ;
}
default:
{
throw new Exception("Error TraverseMode !") ;
}
}
}
#endregion
#endregion

#region privateMethod

#region DoInsert
private void DoInsert(Node node ,Node childTreeRoot)
{
if(childTreeRoot.val.CompareTo(node.val) == 0)
{
return ;
}

if(childTreeRoot.val.CompareTo(node.val) > 0)
{
if(childTreeRoot.leftChild == null)
{
childTreeRoot.leftChild = node ;
return ;
}

this.DoInsert(node ,childTreeRoot.leftChild) ;
return ;
}

if(childTreeRoot.val.CompareTo(node.val) <0)
{
if(childTreeRoot.rightChild == null)
{
childTreeRoot.rightChild = node ;
return ;
}

this.DoInsert(node ,childTreeRoot.rightChild) ;
return ;
}
}
#endregion

#region SearchElement
private IAndFather SearchElement(IComparable val)
{
if(this.root == null)
{
return null ;
}

IAndFather iAndFather = new IAndFather() ;
if(val.CompareTo(this.root.val) == 0)
{
iAndFather.son = this.root ;
return iAndFather ;
}

iAndFather.father = this.root ;
this.DoSearch(val ,this.root ,iAndFather) ;
if(iAndFather.son != null)
{
return iAndFather ;
}

return null ;
}
#endregion

#region DoSearch
private void DoSearch(IComparable val ,Node childTreeRoot ,IAndFather iAndFather)
{
if(childTreeRoot == null)
{
return ;
}

if(val == childTreeRoot.val)
{
iAndFather.son = childTreeRoot ;
return ;
}

iAndFather.father = childTreeRoot ;
if(val.CompareTo(childTreeRoot.val) >0)
{
iAndFather.isLeftChild = false ;
this.DoSearch(val ,childTreeRoot.rightChild ,iAndFather) ;
}
else
{
iAndFather.isLeftChild = true ;
this.DoSearch(val ,childTreeRoot.leftChild ,iAndFather) ;
}
}
#endregion

#region RemoveRoot
private void RemoveRoot(IAndFather childTreeRootAndFather)
{
if(childTreeRootAndFather.son == null)
{
return ;
}

bool isRootDeleted = (childTreeRootAndFather.father == null) ;

//如果删除的为叶子节点
if((childTreeRootAndFather.son.leftChild == null) && (childTreeRootAndFather.son.rightChild ==null))
{
//删除根节点
if(isRootDeleted)
{
this.root = null ;
return ;
}

if(childTreeRootAndFather.isLeftChild)
{
childTreeRootAndFather.father.leftChild = null ;
}
else
{
childTreeRootAndFather.father.rightChild = null ;
}
return ;
}

//要删除的节点有一个子树
if((childTreeRootAndFather.son.leftChild == null) || (childTreeRootAndFather.son.rightChild ==null))
{
//删除根节点
if(isRootDeleted)
{
this.root = (childTreeRootAndFather.son.leftChild == null ? childTreeRootAndFather.son.rightChild :childTreeRootAndFather.son.leftChild) ;
return ;
}

if(childTreeRootAndFather.isLeftChild)
{
childTreeRootAndFather.father.leftChild = (childTreeRootAndFather.son.leftChild == null ? childTreeRootAndFather.son.rightChild :childTreeRootAndFather.son.leftChild) ;
}
else
{
childTreeRootAndFather.father.rightChild = (childTreeRootAndFather.son.leftChild == null ? childTreeRootAndFather.son.rightChild :childTreeRootAndFather.son.leftChild) ;
}

return ;
}

//左右子树均不为空
if((childTreeRootAndFather.son.leftChild != null) && (childTreeRootAndFather.son.rightChild !=null))
{
//删除根节点
if(isRootDeleted)
{
childTreeRootAndFather.father = new Node() ;
childTreeRootAndFather.isLeftChild = true ;
}

//要删除节点的右子节点没有左子树
if(childTreeRootAndFather.son.rightChild.leftChild == null)
{
if(childTreeRootAndFather.isLeftChild)
{
childTreeRootAndFather.father.leftChild = childTreeRootAndFather.son.rightChild ;
}
else
{
childTreeRootAndFather.father.rightChild = childTreeRootAndFather.son.rightChild ;
}
}
else
{
//寻找右子树的最小节点
IAndFather dest = new IAndFather() ;
dest.father = childTreeRootAndFather.son.rightChild ;
dest.son = childTreeRootAndFather.son.rightChild.leftChild ;
dest.isLeftChild = true ;

while(dest.son.leftChild != null)
{
dest.father = dest.son ;
dest.son = dest.son.leftChild ;
dest.isLeftChild = true ;
}

if(childTreeRootAndFather.isLeftChild)
{
childTreeRootAndFather.father.leftChild = dest.son ;
}
else
{
childTreeRootAndFather.father.rightChild = dest.son ;
}

dest.father.leftChild = null ;
}

//如果删除根节点
if(isRootDeleted)
{
this.root = childTreeRootAndFather.father.leftChild ;
}

return ;
}
}
#endregion

#region GetDepth
private int GetDepth()
{
ArrayList list = this.GetAllNodesAscend(true) ;
if(list == null)
{
return 0 ;
}

ArrayList depthList = new ArrayList() ;
foreach(Node node in list)
{
if(this.IsLeaf(node))
{
depthList.Add(this.ComputeDepth(node)) ;
}
}

int depth = (int)depthList[0] ;
foreach(int dep in depthList)
{
if(dep > depth)
{
depth = dep ;
}
}

return depth ;
}

private int ComputeDepth(Node leaf)
{
int count = 1 ;
Node curNode = leaf ;

while(this.GetFather(curNode) != null)
{
++ count ;
curNode = this.GetFather(curNode) ;
}

return count ;
}
#endregion

#region GetFather
private Node GetFather(Node node)
{
if(node == this.root)
{
return null ;
}

ArrayList list = this.GetAllNodesAscend(true) ;
if(list == null)
{
return null ;
}

foreach(Node tar in list)
{
if((tar.leftChild == node) ||(tar.rightChild == node))
{
return tar ;
}
}

return null ;
}
#endregion

#region IsLeaf
private bool IsLeaf(Node node)
{
if((node.leftChild == null) && (node.rightChild == null))
{
return true ;
}

return false ;
}
#endregion

#region CountAllNodes
private void CountAllNodes(Node childTreeRoot ,ref int count)
{
if(childTreeRoot == null)
{
return ;
}

++ count ;

this.CountAllNodes(childTreeRoot.leftChild ,ref count) ;
this.CountAllNodes(childTreeRoot.rightChild ,ref count) ;
}
#endregion

#endregion
}

public class IAndFather
{
public Node father ;
public Node son ;
public bool isLeftChild ;
}

二叉树,不仅是二叉树,所有树型结构的核心思想是递归,只要运用好了这种思想,N叉树的实现也是手到擒来:)

分享到:
评论

相关推荐

    C#实现二叉树基本操作,排序,计算和文件读写

    此系统设计整合了二叉树基本操作,二叉树排序,二叉树计算和文件读写四个功能。

    C#算法实现(哈希表 图 二叉树 KMP prim 最短路径 各种排序)

    C#算法实现(哈希表 图 二叉树 KMP prim 最短路径 各种排序)!希望大家喜欢!

    几种经典排序算法C#实现

    用C#实现的几种典型排序算法,包括二叉树排序、快速排序、希尔排序、插入排序、冒泡排序、选择排序等,代码简单易懂,适合初学者,供学习教育用

    c#代码有查找,二叉树,链表,各种排序

    印度外教提供的,分享一下!包括查找,二叉树,链表,各种排序

    C#数据结构 排序 栈和栈的应用 树和二叉树 递归 例子

    C#数据结构 排序 栈和栈的应用 树和二叉树 递归 实例说明

    C# 二叉树算法排序

    使用二叉树算法写的排序功能,可以对任意数据进行排序。含源代码及示例。

    关于c#二叉树的实现

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

    数据结构C#篇(链表,二叉树,排序)

    数据结构C#篇,数据结构的C#描述链表,二叉树,排序等常用数据结构

    数据结构-代码(C#实现)

    链表:单链表,双向链表,循环链表 栈,队列 二叉树应用-表达式求值 树的操作 图 二分查找 排序算法:插入排序,选择排序,冒泡排序 -全是C#,附上Viso图和一些解释

    动态画二叉树

    数据结构中的考试题目,动态画排序二叉树,并且计算节点数

    C#实现二叉排序树代码实例

    二叉排序树,又称为二叉查找树。...C#链式存储二叉排序树,实现简单的排序,以及查找,具体代码如下: namespace _2_1_3二叉排序树 { /// /// 结点类 /// class BSNode { //结点 public BSNode Lef

    数据结构——线索二叉树排序

    数据结构很讲究算法,我这个写的很好!!用C#语言写的,试试看,相信给你好处的。

    广工C#实验,实践C#语言基础知识及控制台应用程序开发,

    1 实验一 1.1 实验环境与工具: ...(4) 判断二叉树是否为二叉排序树 (5) 输出中序遍历序列的结果 (6) 计算叶子结点数 (7) 计算二叉树深度 2 实验二:窗体应用程序设计 等等,已做好工程文件,可以直接运行

    erchashu.rar_二叉树_叉树

    利用c#语言实现了二叉树的构造,并且同时实现了对二叉树的各种操作,例如二叉树排序,查找最大值或最小值。

    最经典的8大排序算法总结

    最经典的8大排序算法总结,插入排、冒泡排序、快速排序、简单选择排序、归并排序、二叉树排序、基数排序等。

    数据结构与算法-C#版

    这是C#版的数据结构与算法的代码实现,包括:顺序表,单链表,双链表;顺序栈,链栈;顺序队列,链队列;顺序串;用数组进行特殊矩阵的存储,稀疏矩阵的存储;顺序存储二叉树,链式存储二叉树,哈夫曼树;多重链表...

    数据结构与算法(C#)

    数据结构与算法(C#).PDF及代码 第1章 Collections类、泛型类和Timing类概述 第2章 数组和ArrayList 第3章 基础排序算法 第4章 基础查找算法 第5章 栈和队列 第6章 BitArray类 第7章 字符串、String类和StringBuioder...

    c# 数据结构 基础知识

    数据结构 c#的实现 包括了 算法、线性表、 栈和队列、串和数组、数和二叉树、 图、 排序、 是很好的基础技术资料

    数据结构(C#语言版)

    7.8 C#中排序方法 240 习题七 241 -------------------------------------------------- 第8章 查找 8.1 基本概念和术语 243 8.2 静态查找表 243 8.3 动态查找表 248 8.4 哈希表 257 8.5 C#中的查找方法 261 习题八 ...

Global site tag (gtag.js) - Google Analytics