二叉树非递归遍历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来判断当前节点是否已经被遍历过，这点要注意。二叉树的遍历方式虽然相对简单，但是在实际应用中也听到了很多挑战，比如大量的节点、平衡、二叉搜索树等问题。建议在使用之前做好决策和评估，并结合具体的应用场景规划相应的算法实现。