一、基本结构
1. 节点定义
二叉树的每个节点包含三个部分：
-
数据域：存储节点的值（如整数、字符等）。
-
左子节点指针：指向左子树。
-
右子节点指针：指向右子树。
C语言中的节点定义如下：
typedef struct BinTreeNode {struct BinTreeNode* left; // 左子节点struct BinTreeNode* right; // 右子节点int val; // 节点值
} BTNode;2. 树的构建
通过动态分配内存创建新节点：
BTNode* BuyBTNode(int val) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}二、遍历方式
遍历的核心思想：递归分解问题，将树拆分为根节点、左子树、右子树，并按特定顺序访问。
1. 前序遍历（PreOrder）
遍历顺序：根节点 -> 左子树 -> 右子树
逻辑流程
-
第一步：访问当前树的根节点。
-
第二步：将左子树视为新的子树，递归调用自身处理。
-
第三步：将右子树视为新的子树，递归调用自身处理。
void PreOrder(BTNode* root) {if (root == NULL) {printf(" N"); // 空节点标记为Nreturn;}printf(" %d", root->val); // 1. 访问根PreOrder(root->left); // 2. 遍历左子树PreOrder(root->right); // 3. 遍历右子树
}对如下二叉树：
1/ \2 3/ \ / \N N N N输出：1 2 N N 3 N N
2. 中序遍历（InOrder）
遍历顺序：左子树 -> 根节点 -> 右子树
逻辑流程
-
第一步：优先递归处理左子树，直到左子树为空。
-
第二步：回溯到当前根节点并访问。
-
第三步：递归处理右子树。
代码实现
void InOrder(BTNode* root) {if (root == NULL) {printf(" N");return;}InOrder(root->left); // 1. 遍历左子树printf(" %d", root->val); // 2. 访问根InOrder(root->right); // 3. 遍历右子树
} 对上述二叉树，输出：N 2 N 1 N 3 N
3. 后序遍历（PostOrder）
遍历顺序：左子树 -> 右子树 -> 根节点
逻辑流程
-
第一步：递归处理左子树，直到左子树为空。
-
第二步：递归处理右子树，直到右子树为空。
-
第三步：回溯到当前根节点并访问。
void PostOrder(BTNode* root) {if (root == NULL) {printf(" N");return;}PostOrder(root->left); // 1. 遍历左子树PostOrder(root->right); // 2. 遍历右子树printf(" %d", root->val); // 3. 访问根
} 对上述二叉树，输出：N N 2 N N 3 1
三、遍历过程
以下列二叉树为例：
A/ \B C/ \ / \D N N E-
前序：A → B → D → N → C → N → E
-
中序：D → B → N → A → N → C → E
-
后序：N → D → B → N → E → C → A
四、总结
递归分解：将树拆解为根、左子树、右子树，递归处理子树。
前序遍历：优先处理根节点，适合自上而下的操作。
中序遍历：按顺序访问节点，适合二叉搜索树。
后序遍历：优先处理子树，适合自下而上的操作。
顺序控制：通过调整访问根的时机（前序：最先；中序：中间；后序：最后）实现不同遍历。
终止条件：遇到空节点时终止递归，避免无限循环。
堆栈机制：递归调用依赖函数调用栈，隐式实现了遍历的路径回溯。
