学步园

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

先看排序二叉树的接口

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叉树的实现也是手到擒来：）