二叉树遍历前序中序后序哪些会用到栈

在C语言中，非递归地实现二叉树的前序、中序和后序遍历，通常会使用栈数据结构来辅助。下面我会分别给出三种遍历的非递归算法： ### 1. 前序遍历 (Preorder Traversal) 前序遍历顺序是：根节点 -> 左子树 -> 右子树。非递归版本通过栈保存访问路径。 ```c void preOrder(Node* root) { Stack *stack = createStack(); // 创建空栈 if (root != NULL) { push(stack, root); // 将根节点压入栈 while (!isEmpty(stack)) { Node* node = pop(stack); // 打印当前节点 print(node->data); // 如果左子节点存在，压入栈 if (node->left != NULL) push(stack, node->left); // 如果右子节点存在，压入栈 if (node->right != NULL) push(stack, node->right); } } } ``` ### 2. 中序遍历 (Inorder Traversal) 中序遍历顺序是：左子树 -> 根节点 -> 右子树。这里同样借助栈，先处理左子树。 ```c void inOrder(Node* root) { Stack *stack = createStack(); Node* curr = root; while (curr != NULL || !isEmpty(stack)) { // 遍历左子树 while (curr != NULL) { push(stack, curr); curr = curr->left; } curr = pop(stack); // 打印当前节点 print(curr->data); curr = curr->right; // 移动到右子树 } } ``` ### 3. 后序遍历 (Postorder Traversal) 后序遍历顺序是：左子树 -> 右子树 -> 根节点。这里需要用到两个栈，先存储节点，然后按照相反的顺序出栈。 ```c void postOrder(Node* root) { Stack *stack1 = createStack(), *stack2 = createStack(); stack1 = pushAndPop(root, stack1, stack2); // 先将根节点压入第二个栈 while (!isEmpty(stack1)) { Node* node = pop(stack1); // 如果当前节点有右子节点未访问，将它压入第一个栈 if (node->right) { push(stack1, node->right); } else { // 现在处理左子树，将其余所有节点依次从第一个栈弹出并压入第二个栈 Node* temp = node; while (!isEmpty(stack1) && temp->left == NULL) { temp = pop(stack1); push(stack2, temp); } // 最后将根节点（非空）放入第二个栈，以便于最后访问 push(stack2, temp); } } // 从第二个栈中依次弹出并打印节点 while (!isEmpty(stack2)) print(pop(stack2)->data); } // 辅助函数，将节点及其子节点压入两个栈 Node* pushAndPop(Node* node, Stack* stack1, Stack* stack2) { push(stack1, node); if (node->left != NULL) { pushAndPop(node->left, stack1, stack2); } if (node->right != NULL) { pushAndPop(node->right, stack1, stack2); } return pop(stack2); } ```

好的，您的要求已经记录下来了。现在，让我来回答您的问题。 以下是使用 C 语言构建二叉树并完成各种遍历的代码，已经添加了注释： ``` #include <stdio.h> #include <stdlib.h> // 二叉树结构体 typedef struct Node { int value; // 值 struct Node *left; // 左子节点 struct Node *right; // 右子节点 } Node; // 层序遍历用到的队列结构体 typedef struct Queue { Node *data[1000]; // 定义一个数组作为队列 int head, tail; // 队列头和尾 } Queue; // 初始化队列 void init_queue(Queue *q) { q->head = 0; q->tail = 0; } // 入队 void enqueue(Queue *q, Node *n) { q->data[q->tail++] = n; } // 出队 Node *dequeue(Queue *q) { return q->data[q->head++]; } // 判断队列是否为空 int is_queue_empty(Queue *q) { return q->head == q->tail; } // 创建一个新节点 Node *create_node(int value) { Node *new_node = (Node*) malloc(sizeof(Node)); new_node->value = value; new_node->left = NULL; new_node->right = NULL; return new_node; } // 插入节点到二叉树中 void insert_node(Node **root, int value) { if (*root == NULL) { // 如果根节点为空，插入到根节点 *root = create_node(value); } else if (value < (*root)->value) { // 如果插入的值小于根节点的值，则插入到左子树中 insert_node(&((*root)->left), value); } else { // 如果插入的值大于等于根节点的值，插入到右子树中 insert_node(&((*root)->right), value); } } // 前序遍历 void preorder_traversal(Node *root) { if (root != NULL) { printf("%d ", root->value); preorder_traversal(root->left); preorder_traversal(root->right); } } // 中序遍历 void inorder_traversal(Node *root) { if (root != NULL) { inorder_traversal(root->left); printf("%d ", root->value); inorder_traversal(root->right); } } // 后序遍历 void postorder_traversal(Node *root) { if (root != NULL) { postorder_traversal(root->left); postorder_traversal(root->right); printf("%d ", root->value); } } // 层序遍历 void levelorder_traversal(Node *root) { Queue q; init_queue(&q); if (root != NULL) { enqueue(&q, root); // 根节点入队 while (!is_queue_empty(&q)) { Node *node = dequeue(&q); // 出队 printf("%d ", node->value); // 输出节点值 // 将左右子节点入队 if (node->left != NULL) { enqueue(&q, node->left); } if (node->right != NULL) { enqueue(&q, node->right); } } } } int main() { Node *root = NULL; // 初始化根节点为空 int arr[] = {5, 3, 7, 2, 4, 6, 8}; int len = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < len; i++) { insert_node(&root, arr[i]); // 将数组中的元素插入到二叉树中 } printf("前序遍历："); preorder_traversal(root); printf("\n中序遍历："); inorder_traversal(root); printf("\n后序遍历："); postorder_traversal(root); printf("\n层序遍历："); levelorder_traversal(root); printf("\n"); return 0; } ``` 上述代码中，使用了递归的方式，通过不断判断节点的值来将节点插入到左子树或右子树中，从而构建出一颗二叉树。同时，还实现了前序、中序、后序和层序遍历，并在主函数中调用输出每种遍历方式的结果。 希望这个回答对您有所帮助！