建立二叉树,并实现二叉树的遍历以及求根结点到指定结点的路径。 功能要求: 1)建立二叉树存储结构; 2)对二叉树进行先序、中序、后序、层序遍历,并输出对应遍历序列; 3)求根结点到指定结点的路径。 界面要求:程序运行后,给出菜单项的内容和输入提示: 1.建立二叉树存储结构 2.求二叉树的先序遍历序列 3.求二叉树的中序遍历序列 4.求二叉树的后序遍历序列 5.求二叉树的层序遍历序列 6.求根结点到指定结点的路径 0.退出 请选择0-5:
时间: 2024-03-06 13:49:02 浏览: 74
建立二叉树并求指定结点路径
好的,下面是一份可以实现上述功能要求和界面要求的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
// 定义二叉树结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建新节点
struct TreeNode* createNode(int val) {
struct TreeNode* newNode = (struct TreeNode*) malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 建立二叉树
struct TreeNode* createTree() {
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
return root;
}
// 先序遍历
void preOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 中序遍历
void inOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
// 后序遍历
void postOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->val);
}
// 层序遍历
void levelOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct TreeNode* queue[MAXSIZE];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
struct TreeNode* node = queue[front++];
printf("%d ", node->val);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}
// 求指定结点到根的路径
int findPath(struct TreeNode* root, int val, int path[]) {
if (root == NULL) {
return 0;
}
if (root->val == val) {
path[0] = root->val;
return 1;
}
int left = findPath(root->left, val, path);
int right = findPath(root->right, val, path);
if (left || right) {
path[left + right] = root->val;
return left + right + 1;
}
return 0;
}
// 主函数
int main() {
int choice, val, len;
int path[MAXSIZE];
struct TreeNode* root = createTree();
while (1) {
printf("1.建立二叉树存储结构\n");
printf("2.求二叉树的先序遍历序列\n");
printf("3.求二叉树的中序遍历序列\n");
printf("4.求二叉树的后序遍历序列\n");
printf("5.求二叉树的层序遍历序列\n");
printf("6.求根结点到指定结点的路径\n");
printf("0.退出\n");
printf("请选择0-6:");
scanf("%d", &choice);
switch (choice) {
case 0:
return 0;
case 1:
printf("二叉树存储结构已建立!\n");
break;
case 2:
printf("先序遍历序列为:");
preOrderTraversal(root);
printf("\n");
break;
case 3:
printf("中序遍历序列为:");
inOrderTraversal(root);
printf("\n");
break;
case 4:
printf("后序遍历序列为:");
postOrderTraversal(root);
printf("\n");
break;
case 5:
printf("层序遍历序列为:");
levelOrderTraversal(root);
printf("\n");
break;
case 6:
printf("请输入要求路径的结点值:");
scanf("%d", &val);
len = findPath(root, val, path);
printf("路径为:");
for (int i = len - 1; i >= 0; i--) {
printf("%d ", path[i]);
}
printf("\n");
break;
default:
printf("输入错误,请重新选择!\n");
break;
}
}
return 0;
}
```
以上代码中,我们通过不断循环菜单,让用户选择需要执行的操作。在 `main` 函数中,我们可以看到包括建立二叉树、求先序、中序、后序遍历、层序遍历、求路径在内的所有操作。我们可以根据自己的需要选择不同的操作。
希望这份代码可以帮助到你!
阅读全文