二叉树遍历方法详解：递归与非递归、层次遍历

本文档主要介绍了二叉树的基本操作，包括递归和非递归遍历算法，以及层次遍历和计算叶子节点数。二叉树是一种数据结构，每个节点最多有两个子节点，通常被表示为一个包含数据和指向左右子节点指针的结构。文档中的关键部分提供了一个C语言代码示例，展示了如何使用栈（SqStack）来实现这些遍历方法。 1. **递归遍历**: - **先序遍历**: 先访问根节点，然后递归地遍历左子树和右子树。在C代码中，这可能通过函数调用自身来实现，例如`void Preorder(BiTNode* root)`，递归终止条件是当节点为空时返回。 - **中序遍历**: 先遍历左子树，然后访问根节点，最后遍历右子树。中序遍历的C代码实现可能是`void Inorder(BiTNode* root)`。 - **后序遍历**: 先遍历左子树和右子树，最后访问根节点。后序遍历的函数名如`void Postorder(BiTNode* root)`。 2. **非递归遍历**: - **使用栈实现**: - **先序遍历**: 使用栈存储待访问节点的顺序。首先将根节点入栈，然后取出栈顶元素并访问，再将其右子节点（如果存在）和左子节点（如果右子节点未访问）依次入栈。C代码中的`InitStack`和`GetTop`函数用于管理这个过程。 - **中序遍历**: 类似于先序遍历，但需在访问节点前检查其左子树是否为空，直到找到左子树的最右侧节点，然后访问该节点，入栈右子节点。这需要辅助栈和一个临时变量。 - **后序遍历**: 同样借助栈，但顺序不同，可以先将左子节点和右子节点入栈，最后访问根节点。这种情况下，需要在访问完子树后再出栈根节点。 3. **层次遍历**: - **广度优先搜索（BFS）**: 逐层遍历二叉树，每次访问同一层的所有节点，然后再访问下一层。这通常使用队列来实现，将根节点入队，然后在队列非空时取出节点，访问并将其左右子节点（如果有的话）加入队列。 4. **计算叶子节点数**: - 叶子节点是指没有子节点的节点。在遍历过程中，每当遇到一个没有左右子节点的节点，就增加计数器。在非递归遍历的层次遍历或先/中/后序遍历中，可以在访问节点后简单地检查它是否有子节点来判断是否为叶子节点。 以上是文档提供的核心知识点，通过这些函数和数据结构，读者可以学习如何在C语言中实现二叉树的各种遍历方式，并理解其中涉及的数据结构管理和逻辑。