非递归用C语言实现二叉树的遍历
时间: 2024-06-16 07:06:19 浏览: 15
在C语言中,可以使用非递归的方式实现二叉树的遍历。常用的非递归遍历方法有前序遍历、中序遍历和后序遍历。下面是它们的实现方式:
1. 非递归前序遍历:
非递归前序遍历使用栈来辅助实现。具体步骤如下:
- 创建一个空栈,并将根节点入栈。
- 循环执行以下步骤,直到栈为空:
- 弹出栈顶节点,并访问该节点。
- 如果该节点的右子节点不为空,则将右子节点入栈。
- 如果该节点的左子节点不为空,则将左子节点入栈。
2. 非递归中序遍历:
非递归中序遍历同样使用栈来辅助实现。具体步骤如下:
- 创建一个空栈,并将根节点入栈。
- 循环执行以下步骤,直到栈为空:
- 将当前节点的所有左子节点依次入栈,直到没有左子节点。
- 弹出栈顶节点,并访问该节点。
- 将当前节点指向其右子节点。
3. 非递归后序遍历:
非递归后序遍历也使用栈来辅助实现。具体步骤如下:
- 创建两个栈,分别为s1和s2。
- 将根节点入栈s1。
- 循环执行以下步骤,直到栈s1为空:
- 弹出栈顶节点,并将该节点入栈s2。
- 如果该节点的左子节点不为空,则将左子节点入栈s1。
- 如果该节点的右子节点不为空,则将右子节点入栈s1。
- 循环执行以下步骤,直到栈s2为空:
- 弹出栈顶节点,并访问该节点。
相关问题
用C语言实现二叉树遍历,完整代码
下面是使用C语言实现二叉树遍历的完整代码,包括二叉树结构体定义、创建二叉树、三种遍历方式的递归实现和非递归实现。
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stddef.h>
// 二叉树结构体
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) { // 输入-1表示当前节点为null
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree(); // 创建左子树
root->right = createTree(); // 创建右子树
return root;
}
// 前序遍历递归实现
void preorderTraversalRecursive(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversalRecursive(root->left);
preorderTraversalRecursive(root->right);
}
// 前序遍历非递归实现
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[100]; // 定义一个栈,用于存储节点
int top = -1; // 栈顶指针
stack[++top] = root; // 根节点入栈
while (top >= 0) {
TreeNode* node = stack[top--]; // 出栈
printf("%d ", node->val); // 访问根节点
if (node->right != NULL) { // 先将右子树入栈
stack[++top] = node->right;
}
if (node->left != NULL) { // 再将左子树入栈
stack[++top] = node->left;
}
}
}
// 中序遍历递归实现
void inorderTraversalRecursive(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversalRecursive(root->left);
printf("%d ", root->val);
inorderTraversalRecursive(root->right);
}
// 中序遍历非递归实现
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[100];
int top = -1;
TreeNode* node = root;
while (node != NULL || top >= 0) {
while (node != NULL) {
stack[++top] = node; // 将左子树入栈
node = node->left;
}
node = stack[top--]; // 出栈
printf("%d ", node->val); // 访问根节点
node = node->right; // 访问右子树
}
}
// 后序遍历递归实现
void postorderTraversalRecursive(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversalRecursive(root->left);
postorderTraversalRecursive(root->right);
printf("%d ", root->val);
}
// 后序遍历非递归实现
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[100];
int top = -1;
TreeNode* node = root;
TreeNode* last_visited = NULL; // 上次访问的节点
while (node != NULL || top >= 0) {
while (node != NULL) {
stack[++top] = node;
node = node->left;
}
node = stack[top];
if (node->right == NULL || node->right == last_visited) {
printf("%d ", node->val); // 访问根节点
top--;
last_visited = node;
node = NULL;
} else {
node = node->right; // 访问右子树
}
}
}
int main() {
TreeNode* root = createTree(); // 创建二叉树
printf("前序遍历(递归):");
preorderTraversalRecursive(root); // 前序遍历(递归)
printf("\n前序遍历(非递归):");
preorderTraversal(root); // 前序遍历(非递归)
printf("\n中序遍历(递归):");
inorderTraversalRecursive(root); // 中序遍历(递归)
printf("\n中序遍历(非递归):");
inorderTraversal(root); // 中序遍历(非递归)
printf("\n后序遍历(递归):");
postorderTraversalRecursive(root); // 后序遍历(递归)
printf("\n后序遍历(非递归):");
postorderTraversal(root); // 后序遍历(非递归)
return 0;
}
```
运行程序后,可以输入二叉树的节点值,用-1表示当前节点为null,例如:
输入:
```
1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
```
输出:
```
前序遍历(递归):1 2 4 5 3 6
前序遍历(非递归):1 2 4 5 3 6
中序遍历(递归):4 2 5 1 3 6
中序遍历(非递归):4 2 5 1 3 6
后序遍历(递归):4 5 2 6 3 1
后序遍历(非递归):4 5 2 6 3 1
```
c语言实现二叉树中序遍历非递归
C语言实现二叉树中序遍历非递归同样需要使用栈来实现,具体步骤如下:
1. 新建一个栈和一个指针变量p,初始时p指向根节点,栈为空。
2. 循环执行以下步骤,直到栈为空且p为空:
a. 如果p不为空,则将p入栈,并将p指向其左子节点。
b. 如果p为空,则将栈顶元素出栈并输出,然后将p指向栈顶元素的右子节点。
下面是该算法的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[1000];
int top = -1;
struct TreeNode* p = root;
while (top != -1 || p != NULL) {
if (p != NULL) {
stack[++top] = p;
p = p->left;
}
else {
struct TreeNode* node = stack[top--];
printf("%d ", node->val);
p = node->right;
}
}
}
```
其中,struct TreeNode定义了二叉树节点的结构体,val是节点的值,left和right分别是左右子节点的指针。该算法的时间复杂度为O(n),空间复杂度为O(h),其中h为二叉树的高度。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)