用迭代器实现二叉树的中序遍历

简单定义一个抽象的节点类，为了看上去更通用一点，写成了比较难看的泛型：

 1  public  abstract  class TreeNode<TNode, TValue>  2      where TNode : TreeNode<TNode, TValue>,  new()  3 {  4      public TValue Value {  get;  set; }  5   6      public TNode LeftChild {  get;  protected  set; }  7   8      public TNode RightChild {  get;  protected  set; }  9  10      public  abstract TNode CreateLeftChild(TValue value); 11  12      public  abstract TNode CreateRightChild(TValue value); 13 }

 

然后我们的二叉树单独写一个接口，里面放一个根节点，然后继承一下IEnumerable，表示我们是可以被迭代的：

 1  public  interface IBinaryTree< out TNode> : IEnumerable<TNode>  2 {  3     TNode Root {  get; }  4 }  5   6  public  class BinaryTree<TNode, TValue> : IBinaryTree<TNode>  7      where TNode : TreeNode<TNode, TValue>,  new()  8 {  9      public TNode Root {  get;  protected  set; } 10  11      public BinaryTree(TValue value) 12     { 13         Root =  new TNode { Value = value }; 14     } 15  16      #region IEnumerable 17  18      public IEnumerator<TNode> GetEnumerator() 19     { 20          return  new InorderTraversalBinaryTreeEnumerator<TNode, TValue>(Root); 21     } 22  23     IEnumerator IEnumerable.GetEnumerator() 24     { 25          return GetEnumerator(); 26     } 27  28      #endregion 29 }

 

 GetEnumerator方法里那个长长的我胡乱命名的东西，就是所谓的迭代器了。用一个栈来配合迭代当前访问的节点：

 1  public  class InorderTraversalBinaryTreeEnumerator<TNode, TValue> : IEnumerator<TNode>  2      where TNode : TreeNode<TNode, TValue>,  new()  3 {  4      private  readonly Stack<TNode> _stack =  new Stack<TNode>();  5      private TNode _current;  6   7     TNode IEnumerator<TNode>.Current  8     {  9          get {  return _current; } 10     } 11  12      object IEnumerator.Current 13     { 14          get {  return _current; } 15     } 16  17      public InorderTraversalBinaryTreeEnumerator(TNode root) 18     { 19         FindLeftBottomNode(root); 20     } 21  22      bool IEnumerator.MoveNext() 23     { 24          if (_stack.Count ==  0) 25              return  false; 26  27         _current = _stack.Pop(); 28  29         FindLeftBottomNode(_current.RightChild); 30  31          return  true; 32     } 33  34      private  void FindLeftBottomNode(TNode node) 35     { 36          while (node !=  null) 37         { 38             _stack.Push(node); 39             node = node.LeftChild; 40         } 41     } 42  43      void IEnumerator.Reset() 44     { 45     } 46  47      void IDisposable.Dispose() 48     { 49     } 50 }

 

基础代码就这些，下面演示一个可以在控制器打印出来的二叉树。

为了打印方便，给节点扩展了Parent属性，外加一点简单的判断方法：

 1  public  class PrintableTreeNode : TreeNode<PrintableTreeNode,  int>  2 {  3      public PrintableTreeNode Parent {  get;  private  set; }  4   5      public PrintableTreeNode()  6         :  this( null)  7     {  8     }  9  10      public PrintableTreeNode(PrintableTreeNode parent) 11     { 12         Parent = parent; 13     } 14  15      public  override PrintableTreeNode CreateLeftChild( int value) 16     { 17          return LeftChild =  new PrintableTreeNode { Value = value, Parent =  this }; 18     } 19  20      public  override PrintableTreeNode CreateRightChild( int value) 21     { 22          return RightChild =  new PrintableTreeNode { Value = value, Parent =  this }; 23     } 24  25      public  bool IsLeftChild() 26     { 27          return Parent !=  null && ReferenceEquals( this, Parent.LeftChild); 28     } 29  30      public  bool IsRightChild() 31     { 32          return Parent !=  null && ReferenceEquals( this, Parent.RightChild); 33     } 34 } 35  36  public  interface IPrintableBinaryTree : IBinaryTree<PrintableTreeNode> 37 { 38      void Print(); 39 }

 

 Print的实现就不贴出来了。

 随机生成一棵树，然后直接foreach就能中序遍历整棵树了：

 

 

转载于:https://www.cnblogs.com/LeoZ/p/4485036.html

相关资源：JAVA上百实例源码以及开源项目