C# 实现二叉树的遍历算法

数据结构

• BiTreeNode: 树节点

  public char Value { get; set; } // 本例中以 char 作为节点值的数据类型
  public BiTreeNode LChild { get; set; } // 左孩子
  public BiTreeNode RChild { get; set; } // 右孩子
  
  // 默认构造方法
  public BiTreeNode() {...}
  
  // 带参构造方法
  public BiTreeNode(char val) { ... }
  

• SqStack: 顺序栈（辅助非递归遍历算法）

  // 为节点类型 BiTreeNode 起别名
  using SElementType = TraversalAlgrithm.BiTreeNode;
  
  /* 变量 */
  private const int STACK_SIZE = 100; // 栈空间大小
  private SElementType[] elements;    // 栈存储空间
  private int top;    // 栈顶元素的下标值
  
  /* 属性 */
  public SElementType[] Elements { get { return elements; } } // 外部通过该属性访问栈空间
  public int Count { get { return top + 1; } }    // 栈内元素数量
  public bool IsEmpty { get { return top < 0; } } // 是否栈空
  public bool IsFull { get { return top >= STACK_SIZE; } } // 是否栈满
  
  /* 操作 */
  public SqStack() {...}  // 初始化栈空间
  
  public bool Push(SElementType elem) {...}   // 将元素 elem 入栈
  
  public bool Pop(ref SElementType topElem) {...} // 使元素 topElem 出栈
  
  public SElementType Peek() {...}    // 获取栈顶元素
  
  public void Clear() {...}   // 重置栈
  

• BiTreeManager: 二叉树的管理类

  private BiTreeNode root; // 根节点
  public BiTreeNode Root { get { return root; } } // 外部通过该属性访问树的根节点
  
  public BiTreeManager() {...} // 构建一棵空树
  public bool CreateBiTree() {...} // 创建二叉树（本例中二叉树的形态由程序指定），返回创建结果
  
  public void Traversal_Recursive() {...} // 调用前、中、后序的递归遍历算法
  public void Traversal_Iterative() {...} // 调用非递归遍历算法
  
  // 递归遍历
  private void PreOrderTraversal_R(BiTreeNode node) {...}
  private void InOrderTraversal_R(BiTreeNode node) {...}
  private void PostOrderTraversal_R(BiTreeNode node) {...}
  
  // 非递归(迭代)遍历
  private void PreOrderTraversal(BiTreeNode node) {...}
  private void InOrderTraversal(BiTreeNode node) {...}
  private void PostOrderTraversal(BiTreeNode node) {...}
  
  // 对节点的访问（如：打印节点的值）
  private void Visit(BiTreeNode node) {...}
  

• 遍历算法的实现

  • 递归算法

    3种遍历算法的唯一区别仅在于访问根节点的时机，即对 Visit() 的调用时机不同

  /* 前序 */
  private void PreOrderTraversal_R(BiTreeNode node) {
      if (node == null) {
          //Console.WriteLine("PreOrderTraverse_R Failed: root is null");
          return;
      }
  
      Visit(node); // 根
      PreOrderTraversal_R(node.LChild); // 左
      PreOrderTraversal_R(node.RChild); // 右
  }
  
  /* 中序 */
  private void InOrderTraversal_R(BiTreeNode node) {
      if (node == null) {
          //Console.WriteLine("InOrderTraverse_R Failed: root is null");
          return;
      }
  
      InOrderTraversal_R(node.LChild); // 左
      Visit(node); // 根
      InOrderTraversal_R(node.RChild); // 右
  }
  
  /* 后序 */
  private void PostOrderTraversal_R(BiTreeNode node) {
      if (node == null) {
          //Console.WriteLine("PostOrderTraverse_R Failed: root is null");
          return;
      }
  
      PostOrderTraversal_R(node.LChild); // 左
      PostOrderTraversal_R(node.RChild); // 右
      Visit(node); // 根
  }
  

  • 非递归算法

    • 前序遍历

    private void PreOrderTraversal(BiTreeNode node) {
        if (node == null) {
            return;
        }
    
        var s = new SqStack();
        var p = node;
    
        while (!s.IsEmpty || p != null) {
            // 向左走到尽头
            while (p != null) {
                s.Push(p); // 先压根，再压左孩子
                Visit(s.Peek()); // 节点一入栈就访问
                p = p.LChild;   // 向左孩子移动
            }
    
            if (!s.IsEmpty) {
                // 出栈元素p的身份必定遵循以下顺序：先为左孩子，再为根，最后为右孩子
                s.Pop(ref p);
                
                // 左孩子出栈后，再处理右孩子入栈
                p = p.RChild;
            }
        }
    }
    

    • 中序遍历

      中序遍历的栈运行规律与前序相同，区别仅在于对节点的访问时机，前序按入栈次序访问，中序按出栈次序访问

    private void InOrderTraversal(BiTreeNode node) {
        if (node == null) {
            return;
        }
    
        var s = new SqStack();
        var p = node;
    
        while (!s.IsEmpty || p != null) {
            while (p != null) {
                s.Push(p);
                p = p.LChild;
            }
    
            if (!s.IsEmpty) {
                // 出栈元素p的身份必定遵循以下顺序：先为左孩子，再为根，最后为右孩子
                s.Pop(ref p);
                
                // 即按上述注释所述的顺序对节点进行访问
                Visit(p);
    
                // 左孩子出栈后，再处理右孩子入栈
                p = p.RChild;
            }
        }
    }
    

    • 后序遍历

    private void PostOrderTraversal(BiTreeNode node) {
        if (node == null) {
            return;
        }
        
        // 利用了两个栈空间
        var s1 = new SqStack();
        var s2 = new SqStack();
    
        var p = node;
        s1.Push(p); // 首先向 s1 中压入根节点
    
        while (!s1.IsEmpty) {
            // 将 s1 的栈顶元素压入 s2 
            s1.Pop(ref p);
            s2.Push(p);
    
            // s1 先压左孩子
            if (p.LChild != null) {
                s1.Push(p.LChild);
            }
            
            // 再压右孩子
            if (p.RChild != null) {
                s1.Push(p.RChild);
            }
        }
    
        // 对 s2 由顶至底依次访问栈顶元素即形成后序序列
        while (!s2.IsEmpty) {
            s2.Pop(ref p);
            Visit(p);
        }
    }