C语言递归实现二叉树的遍历
时间: 2023-09-21 16:07:45 浏览: 44
二叉树的遍历分为三种:前序遍历、中序遍历和后序遍历。递归实现二叉树的遍历是比较简单的方法之一,下面以前序遍历为例,给出C语言递归实现二叉树的遍历的代码:
```c
// 定义二叉树结点
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 前序遍历
void preorderTraversal(struct TreeNode* root){
if(root == NULL) return;
printf("%d ",root->val); // 先访问根结点
preorderTraversal(root->left); // 再访问左子树
preorderTraversal(root->right); // 最后访问右子树
}
```
在上面的代码中,我们定义了二叉树结点的结构体,包括结点值和左右子树指针。然后,我们定义了一个前序遍历函数`preorderTraversal`,它接受一个指向二叉树根结点的指针作为参数。
在函数内部,我们首先判断当前结点是否为空,如果为空,则直接返回。否则,我们先访问当前结点的值,然后递归访问左子树和右子树。这样就可以完成前序遍历了。
当然,中序遍历和后序遍历的递归实现与前序遍历类似,只需要改变访问结点的顺序即可。
相关问题
c语言递归函数二叉树的遍历
以下是C语言递归函数实现二叉树的遍历的代码示例:
1.先序遍历
```c
void PreOrder(BiTree T) {
if (T ! NULL) {
printf("%d ", T->key); // 先访问根节点
PreOrder(T->left); // 再遍历左子树
PreOrder(T->right); // 最后遍历右子树
}
}
```
2.中序遍历
```c
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->left); // 先遍历左子树
printf("%d ", T->key); // 再访问根节点
InOrder(T->right); // 最后遍历右子树
}
}
```
3.后序遍历
```c
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->left); // 先遍历左子树
PostOrder(T->right); // 再遍历右子树
printf("%d ", T->key); // 最后访问根节点
}
}
```
C语言非递归二叉树遍历用栈实现
二叉树的非递归遍历一般使用栈来实现。以下是 C 语言实现二叉树非递归遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 定义栈结构
struct Stack {
struct TreeNode *data[MAX_SIZE];
int top;
};
// 初始化栈
void initStack(struct Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(struct Stack *s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(struct Stack *s) {
return s->top == MAX_SIZE - 1;
}
// 入栈
void push(struct Stack *s, struct TreeNode *node) {
if (isFull(s)) {
printf("Stack is full.\n");
return;
}
s->top++;
s->data[s->top] = node;
}
// 出栈
struct TreeNode *pop(struct Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return NULL;
}
struct TreeNode *node = s->data[s->top];
s->top--;
return node;
}
// 二叉树非递归前序遍历
void preorderTraversal(struct TreeNode *root) {
if (root == NULL) {
return;
}
struct Stack s;
initStack(&s);
push(&s, root);
while (!isEmpty(&s)) {
struct TreeNode *node = pop(&s);
printf("%d ", node->val);
if (node->right != NULL) {
push(&s, node->right);
}
if (node->left != NULL) {
push(&s, node->left);
}
}
}
// 二叉树非递归中序遍历
void inorderTraversal(struct TreeNode *root) {
if (root == NULL) {
return;
}
struct Stack s;
initStack(&s);
struct TreeNode *node = root;
while (node != NULL || !isEmpty(&s)) {
while (node != NULL) {
push(&s, node);
node = node->left;
}
node = pop(&s);
printf("%d ", node->val);
node = node->right;
}
}
// 二叉树非递归后序遍历
void postorderTraversal(struct TreeNode *root) {
if (root == NULL) {
return;
}
struct Stack s;
initStack(&s);
struct TreeNode *node = root;
struct TreeNode *lastVisit = NULL;
while (node != NULL || !isEmpty(&s)) {
while (node != NULL) {
push(&s, node);
node = node->left;
}
node = s.data[s.top];
if (node->right == NULL || node->right == lastVisit) {
printf("%d ", node->val);
lastVisit = node;
node = NULL;
pop(&s);
} else {
node = node->right;
}
}
}
int main() {
struct TreeNode *root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
struct TreeNode *left = (struct TreeNode *) malloc(sizeof(struct TreeNode));
struct TreeNode *right = (struct TreeNode *) malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = left;
root->right = right;
left->val = 2;
left->left = NULL;
left->right = NULL;
right->val = 3;
right->left = NULL;
right->right = NULL;
printf("前序遍历结果:");
preorderTraversal(root);
printf("\n中序遍历结果:");
inorderTraversal(root);
printf("\n后序遍历结果:");
postorderTraversal(root);
return 0;
}
```
这里实现了二叉树的非递归前序、中序和后序遍历。需要注意的是,后序遍历的实现比较复杂,需要设置一个 lastVisit 指针来记录上一个访问的结点,以保证不重复访问。