小学网站模板源码,网站开发到上线的流程,wordpress 腾讯qq登陆,郑州官网seo以下是用C语言实现二叉树的前序遍历、中序遍历和后序遍历的代码示例#xff0c;包括递归和非递归#xff08;借助栈实现#xff09;两种方式#xff1a;
1. 二叉树节点结构体定义
#include stdio.h
#include stdlib.h// 二叉树节点结构体
typedef struct…以下是用C语言实现二叉树的前序遍历、中序遍历和后序遍历的代码示例包括递归和非递归借助栈实现两种方式
1. 二叉树节点结构体定义
#include stdio.h
#include stdlib.h// 二叉树节点结构体
typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;2. 前序遍历
ps:图来自一位前辈非常感谢无商用
2.1 递归方式
// 前序遍历递归函数
void preorderTraversalRecursive(TreeNode* root) {if (root NULL) {return;}printf(%d , root-val);preorderTraversalRecursive(root-left);preorderTraversalRecursive(root-right);
}解释
首先判断根节点是否为空NULL如果为空说明已经遍历完或者二叉树本身就是空树直接返回不做任何操作。若根节点不为空则先输出根节点的值通过printf函数这符合前序遍历“根节点、左子树、右子树”的顺序。接着递归调用preorderTraversalRecursive函数去遍历左子树完成左子树的前序遍历。最后再递归调用该函数遍历右子树完成整个二叉树的前序遍历。
2.2 非递归方式借助栈实现
// 前序遍历非递归函数借助栈
void preorderTraversalNonRecursive(TreeNode* root) {if (root NULL) {return;}struct TreeNode *stack[100]; // 简单起见这里假设栈的最大容量为100可以根据实际情况调整int top -1;stack[top] root;while (top 0) {TreeNode* current stack[top--];printf(%d , current-val);if (current-right! NULL) {stack[top] current-right;}if (current-left! NULL) {stack[top] current-left;}}
}解释
同样先判断根节点是否为空为空则直接返回。然后创建一个数组来模拟栈这里简单地定义了固定大小为100的数组作为栈实际应用中可根据二叉树规模动态分配内存并初始化栈顶指针top为 -1表示栈为空。将根节点入栈后进入循环只要栈不为空即top 0 取出栈顶元素current stack[top--]输出其值这模拟了访问根节点的操作。按照前序遍历先右后左的顺序将子节点入栈因为栈是后进先出的数据结构先入栈右子节点后入栈左子节点这样出栈时就能先访问左子树如果右子节点或左子节点不为空就将它们依次入栈以便后续继续遍历。
3. 中序遍历 3.1 递归方式
// 中序遍历递归函数
void inorderTraversalRecursive(TreeNode* root) {if (root NULL) {return;}inorderTraversalRecursive(root-left);printf(%d , root-val);inorderTraversalRecursive(root-right);
}解释
先判断根节点是否为空为空则返回。按照中序遍历“左子树、根节点、右子树”的顺序首先递归调用inorderTraversalRecursive函数去遍历左子树确保左子树的节点先被访问。当左子树遍历完后输出根节点的值。最后再递归调用该函数遍历右子树完成整个二叉树的中序遍历。
3.2 非递归方式借助栈实现
// 中序遍历非递归函数借助栈
void inorderTraversalNonRecursive(TreeNode* root) {if (root NULL) {return;}struct TreeNode *stack[100]; // 假设栈最大容量为100可按需调整int top -1;TreeNode* current root;while (current! NULL || top 0) {while (current! NULL) {stack[top] current;current current-left;}current stack[top--];printf(%d , current-val);current current-right;}
}解释
还是先判断根节点是否为空为空则返回。创建一个栈并初始化栈顶指针同时用current指针指向根节点。进入循环只要current不为空或者栈不为空 先通过内层循环将当前节点及其所有左子树节点依次入栈不断将current指向其左子节点并入栈直到current为空这意味着找到了最左边的节点。然后取出栈顶元素即最左边的节点输出其值这模拟了访问根节点的操作在中序遍历中此时访问的是左子树遍历完后的根节点。最后将current更新为该节点的右子节点以便继续遍历右子树重复上述过程完成中序遍历。
4. 后序遍历 4.1 递归方式
// 后序遍历递归函数
void postorderTraversalRecursive(TreeNode* root) {if (root NULL) {return;}postorderTraversalRecursive(root-left);postorderTraversalRecursive(root-right);printf(%d , root-val);
}解释
首先判断根节点是否为空为空则返回不做后续操作。按照后序遍历“左子树、右子树、根节点”的顺序先递归调用postorderTraversalRecursive函数遍历左子树。接着递归调用该函数遍历右子树。最后输出根节点的值完成整个二叉树的后序遍历。
4.2 非递归方式借助栈实现
// 后序遍历非递归函数借助栈
void postorderTraversalNonRecursive(TreeNode* root) {if (root NULL) {return;}struct TreeNode *stack1[100]; // 假设栈1最大容量为100可按需调整struct TreeNode *stack2[100]; // 假设栈2最大容量为100可按需调整int top1 -1, top2 -1;stack1[top1] root;while (top1 0) {TreeNode* current stack1[top1--];stack2[top2] current;if (current-left! NULL) {stack1[top1] current-left;}if (current-right! NULL) {stack1[top1] current-right;}}while (top2 0) {printf(%d , stack2[top2--]-val);}
}解释
先判断根节点是否为空为空则返回。创建两个栈stack1和stack2这里同样是简单地假设了固定大小为100的数组来模拟栈实际可按需优化以及对应的栈顶指针top1和top2并将根节点入stack1。在第一个循环中 从stack1中取出栈顶元素放入stack2中这一步是为了后续能按后序遍历的顺序输出节点。然后按照后序遍历先左后右的顺序将其左子节点和右子节点如果存在依次入stack1方便后续处理。 第一个循环结束后stack2中存储的节点顺序就是后序遍历的顺序了通过第二个循环依次输出stack2中节点的值完成二叉树的后序遍历。
你可以使用以下代码来测试这些遍历函数
int main() {// 构建一个简单的二叉树示例TreeNode* root (TreeNode*)malloc(sizeof(TreeNode));root-val 1;root-left (TreeNode*)malloc(sizeof(TreeNode));root-left-val 2;root-left-right (TreeNode*)malloc(sizeof(TreeNode));root-left-right-val 4;root-right (TreeNode*)malloc(sizeof(TreeNode));root-right-val 3;root-right-left (TreeNode*)malloc(sizeof(TreeNode));root-right-left-val 5;// 测试前序遍历printf(前序遍历递归结果);preorderTraversalRecursive(root);printf(\n);printf(前序遍历非递归结果);preorderTraversalNonRecursive(root);printf(\n);// 测试中序遍历printf(中序遍历递归结果);inorderTraversalRecursive(root);printf(\n);printf(中序遍历非递归结果);inorderTraversalNonRecursive(root);printf(\n);// 测试后序遍历printf(后序遍历递归结果);postorderTraversalRecursive(root);printf(\n);printf(后序遍历非递归结果);postorderTraversalNonRecursive(root);printf(\n);return 0;
}在上述main函数中构建了一个简单的二叉树示例然后分别调用不同的遍历函数并输出结果方便直观地看到不同遍历方式的效果。实际应用中你可以根据实际的二叉树结构来进行相应的测试和使用这些遍历方法。
