用C++写一段代码创建一个二叉树并自定义函数给结点赋值并自定义函数遍历二叉树,自定义函数实现关于二叉树的其他各种操作
时间: 2024-05-12 20:20:21 浏览: 151
下面是一个示例代码,其中给结点赋值的函数为setValue,遍历二叉树的函数为traverse,其他操作包括插入结点、查找结点、删除结点、计算树高等。
```
#include <stdio.h>
#include <stdlib.h>
/* 二叉树结点定义 */
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
/* 创建二叉树 */
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) { /* 输入-1表示空结点 */
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
/* 给结点赋值 */
void setValue(TreeNode* node, int val) {
if (node == NULL) {
return;
}
node->val = val;
}
/* 遍历二叉树 */
void traverse(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
traverse(root->left);
traverse(root->right);
}
/* 插入结点 */
void insertNode(TreeNode* root, int val) {
if (root == NULL) {
return;
}
if (val < root->val) {
if (root->left == NULL) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
root->left = node;
} else {
insertNode(root->left, val);
}
} else {
if (root->right == NULL) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
root->right = node;
} else {
insertNode(root->right, val);
}
}
}
/* 查找结点 */
TreeNode* findNode(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
return root;
} else if (val < root->val) {
return findNode(root->left, val);
} else {
return findNode(root->right, val);
}
}
/* 删除结点 */
TreeNode* deleteNode(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (val < root->val) {
root->left = deleteNode(root->left, val);
} else if (val > root->val) {
root->right = deleteNode(root->right, val);
} else {
if (root->left == NULL && root->right == NULL) { /* 叶子结点 */
free(root);
root = NULL;
} else if (root->left == NULL) { /* 只有右子树 */
TreeNode* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) { /* 只有左子树 */
TreeNode* temp = root;
root = root->left;
free(temp);
} else { /* 左右子树都有 */
TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
}
return root;
}
/* 计算树高 */
int getHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
int main() {
printf("请输入二叉树结点,-1表示空结点:");
TreeNode* root = createTree();
printf("遍历二叉树结果为:");
traverse(root);
printf("\n");
printf("给结点赋值为10\n");
setValue(root, 10);
printf("插入结点5\n");
insertNode(root, 5);
printf("查找结点7\n");
TreeNode* node = findNode(root, 7);
if (node == NULL) {
printf("未找到结点7\n");
} else {
printf("找到结点7,值为%d\n", node->val);
}
printf("删除结点10\n");
root = deleteNode(root, 10);
printf("计算树高为%d\n", getHeight(root));
return 0;
}
```
阅读全文