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);
    }
}