二叉树非递归遍历c语言
在计算机科学中，二叉树是一种非常重要的数据结构，它是由节点组成的树状结构，每个节点最多有两个子节点。由于二叉树结构的重要性，二叉树的遍历一直是计算机科学研究的重点之一。在二叉树遍历中，递归算法是最为常见的实现方式。本篇文章将为大家介绍二叉树的非递归遍历在c语言中的实现。
1. 二叉树的遍历
在二叉树中，遍历就是按照一定的顺序访问每一个节点，使得能够对整个树结构进行处理。一般遍历二叉树的方式有三种：前序遍历、中序遍历和后序遍历。因为遍历方式的不同，访问节点的顺序也不同。前序遍历是先访问根节点，然后分别访问左子树和右子树。中序遍历是先访问左子树，然后访问根节点，最后访问右子树。后序遍历是先访问左子树，然后访问右子树，最后访问根节点。下面是常用的递归算法：
```c
#include
#include
typedef struct node {
int data;
struct node *left;
struct node *right;
} node_t;
void preorder(node_t *root) {
if (!root) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
void inorder(node_t *root) {
if (!root) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
void postorder(node_t *root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
int main() {
node_t *root = malloc(sizeof(node_t));
root->data = 1;
node_t *node1 = malloc(sizeof(node_t));
node1->data = 2;
node_t *node2 = malloc(sizeof(node_t));
node2->data = 3;
node_t *node3 = malloc(sizeof(node_t));
node3->data = 4;
node_t *node4 = malloc(sizeof(node_t));
node4->data = 5;
node_t *node5 = malloc(sizeof(node_t));
node5->data = 6;
root->left = node1;
root->right = node2;
node1->left = node3;
node1->right = node4;
node2->left = node5;
node2->right = NULL;
preorder(root); // 1 2 4 5 3 6
printf("\n");
inorder(root); // 4 2 5 1 6 3
printf("\n");
postorder(root); // 4 5 2 6 3 1
printf("\n");
return 0;
}
```
2. 二叉树的非递归遍历
二叉树的递归遍历虽然实现起来简单，但对于大规模的树结构来说，递归遍历会使函数的调用压力过大，导致栈溢出等问题，因此非递归遍历成为更优的实现方式。二叉树的非递归遍历基于栈数据结构。在遍历的过程中，需要将遍历的节点入栈，同时在遍历完左子树后弹出该节点，把右子树入堆栈中。这里我们会用到一个辅助指针prev，用来判断当前节点是否已经遍历完成。
2.1 非递归前序遍历代码实现：
```c
void NonRecursionPreorder(struct TreeNode* root) {
if (!root) return;
Stack stack;
StackInit(&stack);
struct TreeNode* p = root;
while (p || !StackEmpty(&stack)) {
if (p) {
printf("%d ", p->val);
StackPush(&stack, p);
p = p->left;
} else {
p = StackTop(&stack);
StackPop(&stack);
p = p->right;
}
}
}
```
2.2 非递归中序遍历代码实现：
```c
void NonRecursionInorder(struct TreeNode* root) {
if (!root) return;
Stack stack;
StackInit(&stack);
struct TreeNode* p = root;
while (p || !StackEmpty(&stack)) {
if (p) {
StackPush(&stack, p);
p = p->left;
} else {
p = StackTop(&stack);
printf("%d ", p->val);
StackPop(&stack);
p = p->right;
}
}
}
```
2.3 非递归后序遍历代码实现：
```c
void NonRecursionPostorder(struct TreeNode* root) {
if (!root) return;
Stack stack;
StackInit(&stack);
struct TreeNode* p = root;
struct TreeNode* r = NULL;
while (p || !StackEmpty(&stack)) {
if (p) {
StackPush(&stack, p);
p = p->left;
} else {
p = StackTop(&stack);
if (p->right == NULL || p->right == r) {
printf("%d ", p->val);
r = p;
StackPop(&stack);
p = NULL;
} else {
p = p->right;
}
}
}
}
```
3. 总结
三种遍历方式的非递归代码非常类似，都是基于栈数据结构实现的。由于空间复杂度低，非递归遍历成为更优的实现方式。值得注意的是，非递归后序遍历需要多一个节点指针prev来判断当前节点是否已经被遍历过，这点要注意。二叉树的遍历方式虽然相对简单，但是在实际应用中也听到了很多挑战，比如大量的节点、平衡、二叉搜索树等问题。建议在使用之前做好决策和评估，并结合具体的应用场景规划相应的算法实现。
