c语言二叉树的前序遍历编程
更新时间:2023-09-11前序遍历概述
前序遍历是二叉树遍历的一种方式之一,它的遍历顺序是先遍历父节点,然后再遍历左子节点,最后遍历右子节点。前序遍历的代码实现可以通过递归或迭代的方式来完成。
递归实现前序遍历
#include// 二叉树节点的定义 struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; }; // 递归实现前序遍历 void preorderTraversal(struct TreeNode* root) { if (root == NULL) { return; } // 先遍历根节点 printf("%d ", root->data); // 再遍历左子节点 preorderTraversal(root->left); // 最后遍历右子节点 preorderTraversal(root->right); }
迭代实现前序遍历
#include#include // 栈节点的定义 struct StackNode { struct TreeNode* treeNode; struct StackNode* next; }; // 二叉树节点的定义 struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; }; // 栈的定义 struct Stack { struct StackNode* top; }; // 创建一个空栈 struct Stack* createStack() { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->top = NULL; return stack; } // 判断栈是否为空 int isEmpty(struct Stack* stack) { return stack->top == NULL; } // 入栈 void push(struct Stack* stack, struct TreeNode* treeNode) { struct StackNode* node = (struct StackNode*)malloc(sizeof(struct StackNode)); node->treeNode = treeNode; node->next = stack->top; stack->top = node; } // 出栈并返回出栈节点 struct TreeNode* pop(struct Stack* stack) { if (isEmpty(stack)) { return NULL; } struct StackNode* topNode = stack->top; struct TreeNode* treeNode = topNode->treeNode; stack->top = topNode->next; free(topNode); return treeNode; } // 迭代实现前序遍历 void iterativePreorderTraversal(struct TreeNode* root) { if (root == NULL) { return; } // 创建一个空栈 struct Stack* stack = createStack(); // 将根节点入栈 push(stack, root); while (!isEmpty(stack)) { // 弹出栈顶节点 struct TreeNode* node = pop(stack); // 访问节点的值 printf("%d ", node->data); // 先将右子节点入栈,使其后出栈 if (node->right != NULL) { push(stack, node->right); } // 再将左子节点入栈,使其先出栈 if (node->left != NULL) { push(stack, node->left); } } }
总结
通过上述代码示例,我们可以看到前序遍历的实现方式。递归实现的前序遍历从根节点开始,先输出根节点的值,然后递归遍历左子树和右子树。迭代实现的前序遍历使用了栈来辅助实现,先将根节点入栈,然后循环弹出栈顶节点并输出其值,同时将右子节点先入栈,再将左子节点入栈。
前序遍历是一个常用的树遍历方式,它可以用来实现一些基于树结构的算法和问题,如查找某个节点是否存在于二叉树中、计算二叉树的高度等。在实际应用中,根据具体需求选择递归或迭代的实现方式,以及合适的数据结构辅助完成前序遍历操作。