[已解决]二叉树的非递归算法

白痴爱面包

分别设计出先序、中序和后序遍历二叉树的非递归算法。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-18 16:42:05

以下是C语言中实现二叉树非递归遍历的代码。这里提供了先序、中序和后序遍历的非递归算法。

首先，定义二叉树结构体：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. 
   
5. typedef struct TreeNode {
   
6.     int val;
   
7.     struct TreeNode *left;
   
8.     struct TreeNode *right;
   
9. } TreeNode;
   

复制代码

接下来，定义栈结构体：

1. typedef struct Stack {
   
2.     TreeNode **array;
   
3.     int top;
   
4.     int size;
   
5. } Stack;
   
6. 
   
7. Stack *createStack(int size) {
   
8.     Stack *stack = (Stack *)malloc(sizeof(Stack));
   
9.     stack->array = (TreeNode **)malloc(size * sizeof(TreeNode *));
   
10.     stack->top = -1;
    
11.     stack->size = size;
    
12.     return stack;
    
13. }
    
14. 
    
15. bool isStackEmpty(Stack *stack) {
    
16.     return stack->top == -1;
    
17. }
    
18. 
    
19. bool isStackFull(Stack *stack) {
    
20.     return stack->top == stack->size - 1;
    
21. }
    
22. 
    
23. void push(Stack *stack, TreeNode *node) {
    
24.     if (isStackFull(stack)) return;
    
25.     stack->array[++stack->top] = node;
    
26. }
    
27. 
    
28. TreeNode *pop(Stack *stack) {
    
29.     if (isStackEmpty(stack)) return NULL;
    
30.     return stack->array[stack->top--];
    
31. }

复制代码

先序遍历非递归算法：

1. void preorderTraversal(TreeNode *root) {
   
2.     if (root == NULL) return;
   
3.     Stack *stack = createStack(100); // 根据实际情况调整栈大小
   
4.     TreeNode *node = root;
   
5. 
   
6.     while (node != NULL || !isStackEmpty(stack)) {
   
7.         while (node != NULL) {
   
8.             printf("%d ", node->val);
   
9.             push(stack, node);
   
10.             node = node->left;
    
11.         }
    
12.         node = pop(stack);
    
13.         node = node->right;
    
14.     }
    
15. 
    
16.     free(stack->array);
    
17.     free(stack);
    
18. }

复制代码

中序遍历非递归算法：

1. void inorderTraversal(TreeNode *root) {
   
2.     if (root == NULL) return;
   
3.     Stack *stack = createStack(100); // 根据实际情况调整栈大小
   
4.     TreeNode *node = root;
   
5. 
   
6.     while (node != NULL || !isStackEmpty(stack)) {
   
7.         while (node != NULL) {
   
8.             push(stack, node);
   
9.             node = node->left;
   
10.         }
    
11.         node = pop(stack);
    
12.         printf("%d ", node->val);
    
13.         node = node->right;
    
14.     }
    
15. 
    
16.     free(stack->array);
    
17.     free(stack);
    
18. }

复制代码

后序遍历非递归算法：

1. void postorderTraversal(TreeNode *root) {
   
2.     if (root == NULL) return;
   
3.     Stack *stack = createStack(100); // 根据实际情况调整栈大小
   
4.     Stack *output = createStack(100); // 存储后序遍历结果的栈
   
5.     TreeNode *node = root;
   
6. 
   
7.     while (node != NULL || !isStackEmpty(stack)) {
   
8.         while (node != NULL) {
   
9.             push(output, node);
   
10.             push(stack, node);
    
11.             node = node->right;
    
12.         }
    
13.         node = pop(stack);
    
14.         node = node->left;
    
15.     }
    
16. 
    
17.     while (!isStackEmpty(output)) {
    
18.         printf("%d ", pop(output)->val);
    
19.     }
    
20. 
    
21.     free(stack->array);
    
22.     free(stack);
    
23.     free(output->array);
    
24.     free(output);
    
25. }

复制代码

现在，你可以使用这些非递归算法来分别实现二叉树的先序、中序和后序遍历。这些算法的基本思路是使用一个栈来存储遍历过程中的节点，这样就可以避免使用递归。栈的大小可以根据实际情况调整。当遍历完整棵树时，释放栈所占用的内存。

跳转到最佳答案楼层

爱意随风起9306

1. #二叉树遍历操作实现的非递归算法
   
2. #先序遍历
   
3. def preOrder2(root):
   
4.     p = root
   
5.     s = LinkStack()
   
6.     s.push(p)
   
7.     while not s.isEmpty():
   
8.         p = s.pop()
   
9.         print(p.data,end=' ')
   
10.         while p is not None:
    
11.             if p.rchild is not None:
    
12.                 print(p.lchild.data,end=' ')
    
13.             if p.lchild is not None:
    
14.                 s.push(p.rchild)
    
15.                 p = p.lchild
    
16. #中序遍历
    
17. def inOeder2(root):
    
18.     p = root
    
19.     s = LinkStack()
    
20.     s.push(p)
    
21.     while not s.isEmpty():
    
22.         while p.lchild is not None:
    
23.             p = p.lchild
    
24.             s.push(p)
    
25.         p = p.pop()
    
26.         print(p.data,end=' ')
    
27.         if p.rchild is not None:
    
28.             s.push(p.rchild)
    
29. #后序遍历
    
30. def postOrder2(root):
    
31.     p = root
    
32.     t = None
    
33.     flag = False
    
34.     s = LinkStack()
    
35.     if p is not None:
    
36.         s.push(p)
    
37.         while p.lchild is None:
    
38.             p = p.push(p)
    
39.             s.push(p)
    
40.         while not s.isEmpty() and flag:
    
41.             if p.rchild == t or p.rchild is None:
    
42.                 print(p.data,end=' ')
    
43.                 flag = True
    
44.                 t = p
    
45.                 s.pop
    
46.             else:
    
47.                 s.push(p.rchild)
    
48.                 flag = False

复制代码

isdkz

以下是C语言中实现二叉树非递归遍历的代码。这里提供了先序、中序和后序遍历的非递归算法。

首先，定义二叉树结构体：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. 
   
5. typedef struct TreeNode {
   
6.     int val;
   
7.     struct TreeNode *left;
   
8.     struct TreeNode *right;
   
9. } TreeNode;
   

复制代码

接下来，定义栈结构体：

1. typedef struct Stack {
   
2.     TreeNode **array;
   
3.     int top;
   
4.     int size;
   
5. } Stack;
   
6. 
   
7. Stack *createStack(int size) {
   
8.     Stack *stack = (Stack *)malloc(sizeof(Stack));
   
9.     stack->array = (TreeNode **)malloc(size * sizeof(TreeNode *));
   
10.     stack->top = -1;
    
11.     stack->size = size;
    
12.     return stack;
    
13. }
    
14. 
    
15. bool isStackEmpty(Stack *stack) {
    
16.     return stack->top == -1;
    
17. }
    
18. 
    
19. bool isStackFull(Stack *stack) {
    
20.     return stack->top == stack->size - 1;
    
21. }
    
22. 
    
23. void push(Stack *stack, TreeNode *node) {
    
24.     if (isStackFull(stack)) return;
    
25.     stack->array[++stack->top] = node;
    
26. }
    
27. 
    
28. TreeNode *pop(Stack *stack) {
    
29.     if (isStackEmpty(stack)) return NULL;
    
30.     return stack->array[stack->top--];
    
31. }

复制代码

先序遍历非递归算法：

1. void preorderTraversal(TreeNode *root) {
   
2.     if (root == NULL) return;
   
3.     Stack *stack = createStack(100); // 根据实际情况调整栈大小
   
4.     TreeNode *node = root;
   
5. 
   
6.     while (node != NULL || !isStackEmpty(stack)) {
   
7.         while (node != NULL) {
   
8.             printf("%d ", node->val);
   
9.             push(stack, node);
   
10.             node = node->left;
    
11.         }
    
12.         node = pop(stack);
    
13.         node = node->right;
    
14.     }
    
15. 
    
16.     free(stack->array);
    
17.     free(stack);
    
18. }

复制代码

中序遍历非递归算法：

1. void inorderTraversal(TreeNode *root) {
   
2.     if (root == NULL) return;
   
3.     Stack *stack = createStack(100); // 根据实际情况调整栈大小
   
4.     TreeNode *node = root;
   
5. 
   
6.     while (node != NULL || !isStackEmpty(stack)) {
   
7.         while (node != NULL) {
   
8.             push(stack, node);
   
9.             node = node->left;
   
10.         }
    
11.         node = pop(stack);
    
12.         printf("%d ", node->val);
    
13.         node = node->right;
    
14.     }
    
15. 
    
16.     free(stack->array);
    
17.     free(stack);
    
18. }

复制代码

后序遍历非递归算法：

1. void postorderTraversal(TreeNode *root) {
   
2.     if (root == NULL) return;
   
3.     Stack *stack = createStack(100); // 根据实际情况调整栈大小
   
4.     Stack *output = createStack(100); // 存储后序遍历结果的栈
   
5.     TreeNode *node = root;
   
6. 
   
7.     while (node != NULL || !isStackEmpty(stack)) {
   
8.         while (node != NULL) {
   
9.             push(output, node);
   
10.             push(stack, node);
    
11.             node = node->right;
    
12.         }
    
13.         node = pop(stack);
    
14.         node = node->left;
    
15.     }
    
16. 
    
17.     while (!isStackEmpty(output)) {
    
18.         printf("%d ", pop(output)->val);
    
19.     }
    
20. 
    
21.     free(stack->array);
    
22.     free(stack);
    
23.     free(output->array);
    
24.     free(output);
    
25. }

复制代码

现在，你可以使用这些非递归算法来分别实现二叉树的先序、中序和后序遍历。这些算法的基本思路是使用一个栈来存储遍历过程中的节点，这样就可以避免使用递归。栈的大小可以根据实际情况调整。当遍历完整棵树时，释放栈所占用的内存。

wuliangtdi

C语言版
先定义一些内容:

1. typedef struct StackNode {
   
2.     void* data;
   
3.     struct StackNode* next;
   
4. } StackNode;
   
5. 
   
6. typedef struct Stack {
   
7.     StackNode* top;
   
8.     int size;
   
9. } Stack;
   
10. 
    
11. Stack* createStack() {
    
12.     Stack* stack = (Stack*)malloc(sizeof(Stack));
    
13.     stack->top = NULL;
    
14.     stack->size = 0;
    
15.     return stack;
    
16. }
    
17. 
    
18. void destroyStack(Stack* stack) {
    
19.     if (stack == NULL) return;
    
20.     while (!isEmpty(stack)) {
    
21.         StackNode* node = stack->top;
    
22.         stack->top = stack->top->next;
    
23.         free(node);
    
24.         stack->size--;
    
25.     }
    
26.     free(stack);
    
27. }
    
28. 
    
29. bool isEmpty(Stack* stack) {
    
30.     return stack->top == NULL;
    
31. }
    
32. 
    
33. void push(Stack* stack, void* data) {
    
34.     StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    
35.     node->data = data;
    
36.     node->next = stack->top;
    
37.     stack->top = node;
    
38.     stack->size++;
    
39. }
    
40. 
    
41. void* pop(Stack* stack) {
    
42.     if (isEmpty(stack)) return NULL;
    
43.     StackNode* node = stack->top;
    
44.     void* data = node->data;
    
45.     stack->top = stack->top->next;
    
46.     free(node);
    
47.     stack->size--;
    
48.     return data;
    
49. }
    

复制代码

前序遍历:

1. void preorderTraversal(TreeNode* root) {
   
2.     if (root == NULL) return;
   
3. 
   
4.     Stack* stack = createStack();
   
5.     push(stack, root);
   
6. 
   
7.     while (!isEmpty(stack)) {
   
8.         TreeNode* node = (TreeNode*)pop(stack);
   
9.         printf("%d ", node->val);
   
10. 
    
11.         if (node->right != NULL) push(stack, node->right);
    
12.         if (node->left != NULL) push(stack, node->left);
    
13.     }
    
14. 
    
15.     destroyStack(stack);
    
16. }
    

复制代码

中序遍历:

1. void inorderTraversal(TreeNode* root) {
   
2.     if (root == NULL) return;
   
3. 
   
4.     Stack* stack = createStack();
   
5.     TreeNode* node = root;
   
6. 
   
7.     while (!isEmpty(stack) || node != NULL) {
   
8.         if (node != NULL) {
   
9.             push(stack, node);
   
10.             node = node->left;
    
11.         } else {
    
12.             node = (TreeNode*)pop(stack);
    
13.             printf("%d ", node->val);
    
14.             node = node->right;
    
15.         }
    
16.     }
    
17. 
    
18.     destroyStack(stack);
    
19. }
    

复制代码

后序遍历:

1. void postorderTraversal(TreeNode* root) {
   
2.     if (root == NULL) return;
   
3. 
   
4.     Stack* stack1 = createStack();
   
5.     Stack* stack2 = createStack();
   
6. 
   
7.     push(stack1, root);
   
8. 
   
9.     while (!isEmpty(stack1)) {
   
10.         TreeNode* node = (TreeNode*)pop(stack1);
    
11.         push(stack2, node);
    
12. 
    
13.         if (node->left != NULL) push(stack1, node->left);
    
14.         if (node->right != NULL) push(stack1, node->right);
    
15.     }
    
16. 
    
17.     while (!isEmpty(stack2)) {
    
18.         TreeNode* node = (TreeNode*)pop(stack2);
    
19.         printf("%d ", node->val);
    
20.     }
    
21. 
    
22.     destroyStack(stack1);
    
23.     destroyStack(stack2);
    
24. }
    

复制代码

wuliangtdi

java版:
先定义一些内容

1. public class TreeNode {
   
2.     int val;
   
3.     TreeNode left;
   
4.     TreeNode right;
   
5.    
   
6.     public TreeNode(int val) {
   
7.         this.val = val;
   
8.         left = null;
   
9.         right = null;
   
10.     }
    
11. }
    
12. //实现泛型栈
    
13. public class Stack<T> {
    
14.     private Node<T> top;
    
15.     private int size;
    
16. 
    
17.     public Stack() {
    
18.         top = null;
    
19.         size = 0;
    
20.     }
    
21. 
    
22.     public void push(T data) {
    
23.         Node<T> node = new Node<>(data);
    
24.         node.next = top;
    
25.         top = node;
    
26.         size++;
    
27.     }
    
28. 
    
29.     public T pop() {
    
30.         if (isEmpty()) return null;
    
31.         T data = top.data;
    
32.         top = top.next;
    
33.         size--;
    
34.         return data;
    
35.     }
    
36. 
    
37.     public T peek() {
    
38.         if (isEmpty()) return null;
    
39.         return top.data;
    
40.     }
    
41. 
    
42.     public boolean isEmpty() {
    
43.         return top == null;
    
44.     }
    
45. 
    
46.     public int size() {
    
47.         return size;
    
48.     }
    
49. 
    
50.     private static class Node<T> {
    
51.         T data;
    
52.         Node<T> next;
    
53. 
    
54.         public Node(T data) {
    
55.             this.data = data;
    
56.             next = null;
    
57.         }
    
58.     }
    
59. }
    
60. 
    

复制代码

先序遍历:

1. public void preorderTraversal(TreeNode root) {
   
2.     if (root == null) return;
   
3.     Stack<TreeNode> stack = new Stack<>();
   
4.     stack.push(root);
   
5. 
   
6.     while (!stack.isEmpty()) {
   
7.         TreeNode node = stack.pop();
   
8.         System.out.print(node.val + " ");
   
9. 
   
10.         if (node.right != null) stack.push(node.right);
    
11.         if (node.left != null) stack.push(node.left);
    
12.     }
    
13. }
    

复制代码

中序遍历:

1. public void inorderTraversal(TreeNode root) {
   
2.     if (root == null) return;
   
3.     Stack<TreeNode> stack = new Stack<>();
   
4.     TreeNode node = root;
   
5. 
   
6.     while (!stack.isEmpty() || node != null) {
   
7.         if (node != null) {
   
8.             stack.push(node);
   
9.             node = node.left;
   
10.         } else {
    
11.             node = stack.pop();
    
12.             System.out.print(node.val + " ");
    
13.             node = node.right;
    
14.         }
    
15.     }
    
16. }
    

复制代码

后序遍历:

1. public void postorderTraversal(TreeNode root) {
   
2.     if (root == null) return;
   
3.     Stack<TreeNode> stack1 = new Stack<>();
   
4.     Stack<TreeNode> stack2 = new Stack<>();
   
5.     stack1.push(root);
   
6. 
   
7.     while (!stack1.isEmpty()) {
   
8.         TreeNode node = stack1.pop();
   
9.         stack2.push(node);
   
10. 
    
11.         if (node.left != null) stack1.push(node.left);
    
12.         if (node.right != null) stack1.push(node.right);
    
13.     }
    
14. 
    
15.     while (!stack2.isEmpty()) {
    
16.         TreeNode node = stack2.pop();
    
17.         System.out.print(node.val + " ");
    
18.     }
    
19. }
    

复制代码