C语言完成先序创建或者层序创建二叉链表函数的编写 ; 完成二叉树中序遍历函数的编写(参考先序遍历函数); 创建如下二叉树的二叉链表,执行程序测试二叉树遍历操作,记录执行结果;以及解释
时间: 2023-12-03 16:46:17 浏览: 103
以下是先序创建和层序创建二叉链表函数的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 先序创建二叉树
TreeNode* createTreeByPreOrder() {
int val;
printf("请输入节点的值(-1表示空节点):");
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTreeByPreOrder();
root->right = createTreeByPreOrder();
return root;
}
// 层序创建二叉树
TreeNode* createTreeByLevelOrder() {
TreeNode* queue[1000];
int front = 0, rear = 0;
int val;
printf("请输入根节点的值:");
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
queue[rear++] = root;
while (front != rear) {
TreeNode* node = queue[front++];
printf("请输入节点%d的左子节点的值:", node->val);
scanf("%d", &val);
if (val != -1) {
TreeNode* leftNode = (TreeNode*)malloc(sizeof(TreeNode));
leftNode->val = val;
node->left = leftNode;
queue[rear++] = leftNode;
}
printf("请输入节点%d的右子节点的值:", node->val);
scanf("%d", &val);
if (val != -1) {
TreeNode* rightNode = (TreeNode*)malloc(sizeof(TreeNode));
rightNode->val = val;
node->right = rightNode;
queue[rear++] = rightNode;
}
}
return root;
}
// 中序遍历二叉树
void inOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
int main() {
// 创建二叉树
TreeNode* root = createTreeByPreOrder();
// TreeNode* root = createTreeByLevelOrder();
// 输出二叉树中序遍历的结果
printf("中序遍历的结果:");
inOrderTraversal(root);
printf("\n");
return 0;
}
```
以上代码中,我们定义了一个 `TreeNode` 结构体,表示二叉树的节点,包括节点的值、左子节点和右子节点。接着实现了先序创建二叉树和层序创建二叉树的函数。在先序创建二叉树时,我们先输入当前节点的值,如果是空节点则返回 NULL;否则创建一个节点,并递归创建它的左子节点和右子节点。在层序创建二叉树时,我们先输入根节点的值,并将根节点入队,然后执行循环,每次从队列中取出一个节点,输入它的左子节点和右子节点的值,如果不是空节点则创建相应的节点,并将它们入队。最后返回根节点即可。
接着实现了中序遍历二叉树的函数。中序遍历的顺序是先访问左子树,再访问根节点,最后访问右子树。因此我们递归遍历左子树,然后输出当前节点的值,最后递归遍历右子树。
最后在 `main` 函数中,我们先创建一个二叉树,可以选择使用先序创建或者层序创建函数。然后输出中序遍历的结果。
以下是根据题目提供的二叉树创建二叉链表并遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));
node2->val = 2;
TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode));
node3->val = 3;
TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode));
node4->val = 4;
TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode));
node5->val = 5;
TreeNode* node6 = (TreeNode*)malloc(sizeof(TreeNode));
node6->val = 6;
TreeNode* node7 = (TreeNode*)malloc(sizeof(TreeNode));
node7->val = 7;
root->left = node2;
root->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
node6->left = NULL;
node6->right = NULL;
node7->left = NULL;
node7->right = NULL;
return root;
}
// 中序遍历二叉树
void inOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
int main() {
// 创建二叉树
TreeNode* root = createTree();
// 输出二叉树中序遍历的结果
printf("中序遍历的结果:");
inOrderTraversal(root);
printf("\n");
return 0;
}
```
以上代码中,我们先手动创建了一个二叉树,根据题目提供的二叉树的形状和节点值进行创建。然后实现了中序遍历二叉树的函数,并在 `main` 函数中输出中序遍历的结果。执行程序,输出的结果为:
```
中序遍历的结果:4 2 5 1 6 3 7
```
由此可见,中序遍历的结果为 `4 2 5 1 6 3 7`。这是因为中序遍历的顺序是先访问左子树,再访问根节点,最后访问右子树,因此按照这个顺序遍历二叉树得到的结果就是中序遍历的结果。
阅读全文