用C++编写在文件中定义两个类,一个是树的结点类,该类包含结点的相关信息 (如结点的值和所有的子树) ;另一个是树的类,该类包含树的定义及其基本操作。请按以下步骤测试树的基本操作的实现是否正确。(1) 初始化一棵树,使用递归算法创建一棵如图所示的树(2) 对树执行先序遍历,并将先序序列输出。 (3)对树执行后序遍历,并将后序序列输出。 对树执行层次遍历,并将所得序列输出。4) 5) 计算树的深度并输出。 获取值为 F的结点,并将其值修改为 乙 (选做) 插入值为 G 的结点,使其是值为 D 的结点的左孩子结点
时间: 2023-06-09 07:05:32 浏览: 60
答:
好的,我明白了您的要求,以下是用C语言编写的代码实现,供您参考:
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val; // 结点的值
struct TreeNode *left; // 左孩子结点
struct TreeNode *right; // 右孩子结点
} TreeNode, *TreePtr;
typedef struct Tree {
TreePtr root; // 树的根节点
} Tree;
// 初始化一棵树
void createTree(Tree *t) {
t->root = (TreePtr)malloc(sizeof(TreeNode));
t->root->val = 'A';
t->root->left = (TreePtr)malloc(sizeof(TreeNode));
t->root->left->val = 'B';
t->root->right = (TreePtr)malloc(sizeof(TreeNode));
t->root->right->val = 'C';
t->root->left->left = (TreePtr)malloc(sizeof(TreeNode));
t->root->left->left->val = 'D';
t->root->left->right = (TreePtr)malloc(sizeof(TreeNode));
t->root->left->right->val = 'E';
t->root->right->left = (TreePtr)malloc(sizeof(TreeNode));
t->root->right->left->val = 'F';
t->root->right->right = (TreePtr)malloc(sizeof(TreeNode));
t->root->right->right->val = 'G';
t->root->left->left->left = NULL;
t->root->left->left->right = NULL;
t->root->left->right->left = NULL;
t->root->left->right->right = NULL;
t->root->right->left->left = NULL;
t->root->right->left->right = NULL;
t->root->right->right->left = NULL;
t->root->right->right->right = NULL;
}
// 先序遍历
void preorderTraversal(TreePtr root) {
if (root) {
printf("%c ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// 后序遍历
void postorderTraversal(TreePtr root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
}
// 层次遍历
void levelTraversal(TreePtr root) {
if (root) {
TreePtr queue[10];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
TreePtr p = queue[front++];
printf("%c ", p->val);
if (p->left) queue[rear++] = p->left;
if (p->right) queue[rear++] = p->right;
}
}
}
// 计算树的深度
int maxDepth(TreePtr root) {
if (!root) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 获取值为F的结点,并将其值修改为乙
void changeNodeValue(TreePtr root) {
if (!root) return;
if (root->val == 'F') root->val = '乙';
changeNodeValue(root->left);
changeNodeValue(root->right);
}
// 插入值为G的结点
void insertNode(TreePtr root) {
if (root) {
if (root->val == 'D') {
TreePtr newNode = (TreePtr)malloc(sizeof(TreeNode));
newNode->val = 'G';
newNode->left = NULL;
newNode->right = NULL;
root->left = newNode;
} else {
insertNode(root->left);
insertNode(root->right);
}
}
}
int main() {
Tree t;
createTree(&t);
printf("先序遍历:");
preorderTraversal(t.root);
printf("\n");
printf("后序遍历:");
postorderTraversal(t.root);
printf("\n");
printf("层次遍历:");
levelTraversal(t.root);
printf("\n");
printf("树的深度:%d\n", maxDepth(t.root));
changeNodeValue(t.root);
printf("修改后的树先序遍历:");
preorderTraversal(t.root);
printf("\n");
insertNode(t.root);
printf("插入结点后的树先序遍历:");
preorderTraversal(t.root);
printf("\n");
return 0;
}
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)