二叉树的遍历c语言二级

### C语言中二叉树遍历的实现方法及示例 #### 定义二叉树节点结构体 为了在C语言中操作二叉树，首先定义一个表示二叉树节点的数据结构。通常情况下，这个数据结构会包含三个部分：指向左子树的指针、存储当前节点值的空间以及指向右子树的指针。 ```c typedef struct TreeNode { char val; struct TreeNode *left; struct TreeNode *right; } TreeNode; ``` #### 创建二叉树 构建一棵具体的二叉树对于理解和测试不同的遍历算法非常重要。这里给出一种简单的创建方式： ```c TreeNode* newNode(char value) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); node->val = value; node->left = NULL; node->right = NULL; return(node); } ``` #### 前序遍历（Pre-order Traversal） 前序遍历遵循访问根节点 -> 访问左子树 -> 访问右子树的原则[^1]。 ```c void preOrderTraversal(struct TreeNode* root){ if (!root) return ; printf("%c ", root->val); // Visit the root. preOrderTraversal(root->left); // Traverse left subtree. preOrderTraversal(root->right); // Traverse right subtree. } ``` #### 中序遍历（In-order Traversal） 中序遍历按照访问左子树 -> 访问根节点 -> 访问右子树的方式进行。 ```c void inOrderTraversal(struct TreeNode* root){ if (!root) return ; inOrderTraversal(root->left); // Traverse left subtree. printf("%c ", root->val); // Visit the root. inOrderTraversal(root->right); // Traverse right subtree. } ``` #### 后序遍历（Post-order Traversal） 后序遍历则采取先访问左子树 -> 右子树最后才访问根节点的方法。 ```c void postOrderTraversal(struct TreeNode* root){ if (!root) return ; postOrderTraversal(root->left); // Traverse left subtree. postOrderTraversal(root->right); // Traverse right subtree. printf("%c ", root->val); // Visit the root. } ``` #### 层次遍历（Level Order Traversal） 层次遍历是从上到下逐层打印每一层上的所有节点，在同一层内从左向右依次处理各个节点[^2]。 ```c #include <queue> using namespace std; void levelOrderTraversal(struct TreeNode* root){ queue<TreeNode*> q; if (root != nullptr) q.push(root); while(!q.empty()){ TreeNode* current = q.front(); cout << current->val << " "; if(current->left != nullptr) q.push(current->left); if(current->right != nullptr) q.push(current->right); q.pop(); } } ``` 以上就是几种常见的二叉树遍历技术及其对应的C语言实现代码片段。这些基础知识不仅适用于准备计算机等级考试的学生们学习掌握，也是编程实践中经常需要用到的基础技能之一。