达州中考2017分数线: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 ;
}