C语言二叉树的先序遍历 完整代码

### C语言实现二叉树先序遍历 以下是基于提供的引用内容和专业知识编写的完整代码示例，用于实现C语言中的二叉树先序遍历。 #### 1. 定义二叉树节点结构体 为了表示二叉树的节点，可以定义一个 `struct` 类型来存储数据以及指向左子节点和右子节点的指针[^1]。 ```c // 定义二叉树节点结构体 typedef struct TreeNode { int data; // 节点的数据部分 struct TreeNode *left; // 左子节点指针 struct TreeNode *right; // 右子节点指针 } TreeNode; ``` #### 2. 创建二叉树节点 通过分配内存动态创建一个新的二叉树节点，并初始化其值和左右子节点指针[^4]。 ```c // 函数：创建新的二叉树节点 TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); if (!newNode) { printf("Memory allocation failed!\n"); exit(1); } newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; } ``` #### 3. 实现递归版本的先序遍历 先序遍历按照 **根 -> 左子树 -> 右子树** 的顺序访问节点。可以通过递归方式轻松实现这一过程。 ```c // 函数：递归实现先序遍历 void preorderTraversalRecursive(TreeNode* root) { if (root != NULL) { printf("%d ", root->data); // 访问当前节点 preorderTraversalRecursive(root->left); // 遍历左子树 preorderTraversalRecursive(root->right); // 遍历右子树 } } ``` #### 4. 构建测试用的二叉树 以下是一个简单的例子，展示如何构建一棵二叉树并调用先序遍历函数。 ```c int main() { // 构造一棵简单的二叉树 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); // 输出先序遍历的结果 printf("Preorder Traversal (Recursive): "); preorderTraversalRecursive(root); printf("\n"); return 0; } ``` 运行上述代码后，输出将是： ``` Preorder Traversal (Recursive): 1 2 4 5 3 ``` --- #### 扩展功能：非递归版先序遍历 如果需要实现非递归版本，则可以借助栈（stack）模拟递归的过程[^3]。 ```c #include <stdio.h> #include <stdlib.h> // 栈的相关操作 typedef struct StackNode { TreeNode* treeNode; struct StackNode* next; } StackNode; StackNode* createStackNode(TreeNode* tree_node) { StackNode* stack_node = (StackNode*)malloc(sizeof(StackNode)); stack_node->treeNode = tree_node; stack_node->next = NULL; return stack_node; } void push(StackNode** top_ref, TreeNode* tree_node) { StackNode* new_stack_node = createStackNode(tree_node); new_stack_node->next = (*top_ref); (*top_ref) = new_stack_node; } TreeNode* pop(StackNode** top_ref) { if ((*top_ref) == NULL) return NULL; StackNode* temp = (*top_ref); (*top_ref) = (*top_ref)->next; TreeNode* popped_tree_node = temp->treeNode; free(temp); return popped_tree_node; } // 非递归先序遍历 void preorderTraversalIterative(TreeNode* root) { StackNode* stack_top = NULL; TreeNode* current = root; while (current || stack_top) { while (current) { // 将当前节点及其所有左子节点压入栈 printf("%d ", current->data); push(&stack_top, current); current = current->left; } current = pop(&stack_top); // 弹出栈顶元素 if (current) { current = current->right; // 处理右子节点 } } } ``` 在 `main()` 中调用该函数即可验证效果。 --- ### 总结 以上展示了完整的C语言实现二叉树先序遍历的方法，包括递归和非递归两种形式。递归方法简单直观，而非递归方法则更贴近底层逻辑，适合深入理解算法原理。