[已解决]二叉树问题

白痴爱面包

实现以下两种要求
1.设计算法以输出每个结点到根结点之间的路径上的所有结点的值。
2.设计算法将一棵以顺序存储方式存储在数组A[]中的二叉树（已转换为完全二叉树，补充的虚拟结点为值为’#’）转换为二叉链表存储形式。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-17 23:23:37

1、设计算法以输出每个结点到根结点之间的路径上的所有结点的值。
以下是一个C语言实现的递归算法，用于输出二叉树中每个结点到根结点之间的路径上的所有结点的值：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct TreeNode {
   
5.     char val;
   
6.     struct TreeNode *left;
   
7.     struct TreeNode *right;
   
8. } TreeNode;
   
9. 
   
10. void printArray(char arr[], int n) {
    
11.     for (int i = 0; i < n; i++) {
    
12.         printf("%c -> ", arr[i]);
    
13.     }
    
14.     printf("根结点\n");
    
15. }
    
16. 
    
17. void printPathsRecur(TreeNode *node, char path[], int pathLen) {
    
18.     if (node == NULL) {
    
19.         return;
    
20.     }
    
21. 
    
22.     path[pathLen] = node->val;
    
23.     pathLen++;
    
24. 
    
25.     if (node->left == NULL && node->right == NULL) {
    
26.         printArray(path, pathLen);
    
27.     } else {
    
28.         printPathsRecur(node->left, path, pathLen);
    
29.         printPathsRecur(node->right, path, pathLen);
    
30.     }
    
31. }
    
32. 
    
33. void printPaths(TreeNode *node) {
    
34.     char path[1000];
    
35.     int pathLen = 0;
    
36.     printPathsRecur(node, path, pathLen);
    
37. }
    
38. 
    
39. int main() {
    
40.     // 创建一个简单的二叉树
    
41.     TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    
42.     root->val = 'A';
    
43.     root->left = (TreeNode *)malloc(sizeof(TreeNode));
    
44.     root->left->val = 'B';
    
45.     root->left->left = NULL;
    
46.     root->left->right = NULL;
    
47.     root->right = (TreeNode *)malloc(sizeof(TreeNode));
    
48.     root->right->val = 'C';
    
49.     root->right->left = NULL;
    
50.     root->right->right = NULL;
    
51. 
    
52.     printPaths(root);
    
53.     return 0;
    
54. }
    

复制代码

2、设计算法将一棵以顺序存储方式存储在数组A[]中的二叉树（已转换为完全二叉树，补充的虚拟结点为值为'#'）转换为二叉链表存储形式。
以下是一个C语言实现的算法，用于将顺序存储的二叉树转换为链式存储的二叉树：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct TreeNode {
   
5.     char val;
   
6.     struct TreeNode *left;
   
7.     struct TreeNode *right;
   
8. } TreeNode;
   
9. 
   
10. TreeNode *buildBinaryTree(const char A[], int index, int size) {
    
11.     if (index >= size || A[index] == '#') {
    
12.         return NULL;
    
13.     }
    
14. 
    
15.     TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    
16.     node->val = A[index];
    
17.     node->left = buildBinaryTree(A, 2 * index + 1, size);
    
18.     node->right = buildBinaryTree(A, 2 * index + 2, size);
    
19. 
    
20.     return node;
    
21. }
    
22. 
    
23. void printPreOrder(TreeNode *node) {
    
24.     if (node == NULL) {
    
25.         return;
    
26.     }
    
27. 
    
28.     printf("%c ", node->val);
    
29.     printPreOrder(node->left);
    
30.     printPreOrder(node->right);
    
31. }
    
32. 
    
33. int main() {
    
34.     char A[] = {'A', 'B', 'C', 'D', '#', 'E', 'F'};
    
35.     int size = sizeof(A) / sizeof(char);
    
36.     TreeNode *root = buildBinaryTree(A, 0, size);
    
37. 
    
38.     printf("前序遍历链式存储的二叉树：\n");
    
39.     printPreOrder(root);
    
40.     printf("\n");
    
41. 
    
42.     return 0;
    
43. }
    

复制代码

这个代码首先实现了一个名为`buildBinaryTree`的递归函数，它根据给定的顺序存储二叉树数组和当前索引创建一个新的二叉树结点，然后递归创建左子树和右子树。当遇到虚拟结点（值为`#`）时，返回NULL。函数`printPreOrder`则用于输出链式存储二叉树的前序遍历结果。

在`main`函数中，首先创建一个顺序存储的二叉树数组`A`，然后调用`buildBinaryTree`函数将数组转换为链式存储的二叉树。最后，使用`printPreOrder`函数输出链式存储二叉树的前序遍历结果。

跳转到最佳答案楼层

isdkz

1、设计算法以输出每个结点到根结点之间的路径上的所有结点的值。
以下是一个C语言实现的递归算法，用于输出二叉树中每个结点到根结点之间的路径上的所有结点的值：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct TreeNode {
   
5.     char val;
   
6.     struct TreeNode *left;
   
7.     struct TreeNode *right;
   
8. } TreeNode;
   
9. 
   
10. void printArray(char arr[], int n) {
    
11.     for (int i = 0; i < n; i++) {
    
12.         printf("%c -> ", arr[i]);
    
13.     }
    
14.     printf("根结点\n");
    
15. }
    
16. 
    
17. void printPathsRecur(TreeNode *node, char path[], int pathLen) {
    
18.     if (node == NULL) {
    
19.         return;
    
20.     }
    
21. 
    
22.     path[pathLen] = node->val;
    
23.     pathLen++;
    
24. 
    
25.     if (node->left == NULL && node->right == NULL) {
    
26.         printArray(path, pathLen);
    
27.     } else {
    
28.         printPathsRecur(node->left, path, pathLen);
    
29.         printPathsRecur(node->right, path, pathLen);
    
30.     }
    
31. }
    
32. 
    
33. void printPaths(TreeNode *node) {
    
34.     char path[1000];
    
35.     int pathLen = 0;
    
36.     printPathsRecur(node, path, pathLen);
    
37. }
    
38. 
    
39. int main() {
    
40.     // 创建一个简单的二叉树
    
41.     TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    
42.     root->val = 'A';
    
43.     root->left = (TreeNode *)malloc(sizeof(TreeNode));
    
44.     root->left->val = 'B';
    
45.     root->left->left = NULL;
    
46.     root->left->right = NULL;
    
47.     root->right = (TreeNode *)malloc(sizeof(TreeNode));
    
48.     root->right->val = 'C';
    
49.     root->right->left = NULL;
    
50.     root->right->right = NULL;
    
51. 
    
52.     printPaths(root);
    
53.     return 0;
    
54. }
    

复制代码

2、设计算法将一棵以顺序存储方式存储在数组A[]中的二叉树（已转换为完全二叉树，补充的虚拟结点为值为'#'）转换为二叉链表存储形式。
以下是一个C语言实现的算法，用于将顺序存储的二叉树转换为链式存储的二叉树：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct TreeNode {
   
5.     char val;
   
6.     struct TreeNode *left;
   
7.     struct TreeNode *right;
   
8. } TreeNode;
   
9. 
   
10. TreeNode *buildBinaryTree(const char A[], int index, int size) {
    
11.     if (index >= size || A[index] == '#') {
    
12.         return NULL;
    
13.     }
    
14. 
    
15.     TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    
16.     node->val = A[index];
    
17.     node->left = buildBinaryTree(A, 2 * index + 1, size);
    
18.     node->right = buildBinaryTree(A, 2 * index + 2, size);
    
19. 
    
20.     return node;
    
21. }
    
22. 
    
23. void printPreOrder(TreeNode *node) {
    
24.     if (node == NULL) {
    
25.         return;
    
26.     }
    
27. 
    
28.     printf("%c ", node->val);
    
29.     printPreOrder(node->left);
    
30.     printPreOrder(node->right);
    
31. }
    
32. 
    
33. int main() {
    
34.     char A[] = {'A', 'B', 'C', 'D', '#', 'E', 'F'};
    
35.     int size = sizeof(A) / sizeof(char);
    
36.     TreeNode *root = buildBinaryTree(A, 0, size);
    
37. 
    
38.     printf("前序遍历链式存储的二叉树：\n");
    
39.     printPreOrder(root);
    
40.     printf("\n");
    
41. 
    
42.     return 0;
    
43. }
    

复制代码

这个代码首先实现了一个名为`buildBinaryTree`的递归函数，它根据给定的顺序存储二叉树数组和当前索引创建一个新的二叉树结点，然后递归创建左子树和右子树。当遇到虚拟结点（值为`#`）时，返回NULL。函数`printPreOrder`则用于输出链式存储二叉树的前序遍历结果。

在`main`函数中，首先创建一个顺序存储的二叉树数组`A`，然后调用`buildBinaryTree`函数将数组转换为链式存储的二叉树。最后，使用`printPreOrder`函数输出链式存储二叉树的前序遍历结果。