用c语言实现(1)创建二叉树 (2)求二叉树的前序遍历序列 (3)求二叉树的中序遍历序列 (4)求二叉树的后序遍历序列 (5)求二叉树的层次遍历序列 (6)计算二叉树的深度 (7)统计二叉树中叶子结点的个数 (8)判断两棵树是否相等 (9)交换二叉树中每个结点的左孩子和右孩子 (10)复制二叉树
时间: 2023-10-13 20:06:12 浏览: 138
以下是用C语言实现二叉树相关操作的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
void createTree(TreeNode **root) {
int val;
scanf("%d", &val); // 输入节点值
if (val == -1) { // 节点值为-1表示空节点
*root = NULL;
} else {
*root = (TreeNode*)malloc(sizeof(TreeNode)); // 动态分配节点空间
(*root)->val = val; // 设置节点值
createTree(&((*root)->left)); // 递归创建左子树
createTree(&((*root)->right)); // 递归创建右子树
}
}
// 前序遍历二叉树
void preOrder(TreeNode *root) {
if (root) {
printf("%d ", root->val); // 输出节点值
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
}
// 中序遍历二叉树
void inOrder(TreeNode *root) {
if (root) {
inOrder(root->left); // 递归遍历左子树
printf("%d ", root->val); // 输出节点值
inOrder(root->right); // 递归遍历右子树
}
}
// 后序遍历二叉树
void postOrder(TreeNode *root) {
if (root) {
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
printf("%d ", root->val); // 输出节点值
}
}
// 层次遍历二叉树
void levelOrder(TreeNode *root) {
if (!root) return;
TreeNode *queue[1000]; // 定义队列
int head = 0, tail = 0;
queue[tail++] = root; // 根节点入队
while (head < tail) {
TreeNode *node = queue[head++]; // 队首出队
printf("%d ", node->val); // 输出节点值
if (node->left) queue[tail++] = node->left; // 左儿子入队
if (node->right) queue[tail++] = node->right; // 右儿子入队
}
}
// 计算二叉树的深度
int getDepth(TreeNode *root) {
if (!root) return 0;
int leftDepth = getDepth(root->left); // 计算左子树深度
int rightDepth = getDepth(root->right); // 计算右子树深度
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 返回更大的深度并加1
}
// 统计二叉树中叶子结点的个数
int getCount(TreeNode *root) {
if (!root) return 0;
if (!root->left && !root->right) return 1; // 叶子节点个数为1
return getCount(root->left) + getCount(root->right); // 递归统计左右子树叶子节点个数之和
}
// 判断两棵树是否相等
int isEqual(TreeNode *root1, TreeNode *root2) {
if (!root1 && !root2) return 1; // 两个空树相等
if (!root1 || !root2) return 0; // 一个为空树,一个非空树不相等
if (root1->val != root2->val) return 0; // 根节点值不相等不相等
return isEqual(root1->left, root2->left) && isEqual(root1->right, root2->right); // 递归判断左右子树是否相等
}
// 交换二叉树中每个结点的左孩子和右孩子
void swap(TreeNode *root) {
if (root) {
TreeNode *temp = root->left; // 交换左右孩子节点
root->left = root->right;
root->right = temp;
swap(root->left); // 递归交换左子树
swap(root->right); // 递归交换右子树
}
}
// 复制二叉树
TreeNode* copy(TreeNode *root) {
if (!root) return NULL;
TreeNode *newRoot = (TreeNode*)malloc(sizeof(TreeNode)); // 动态分配节点空间
newRoot->val = root->val; // 复制节点值
newRoot->left = copy(root->left); // 递归复制左子树
newRoot->right = copy(root->right); // 递归复制右子树
return newRoot;
}
int main() {
TreeNode *root = NULL;
printf("请输入二叉树的节点值,-1表示空节点:\n");
createTree(&root);
printf("前序遍历序列:");
preOrder(root);
printf("\n中序遍历序列:");
inOrder(root);
printf("\n后序遍历序列:");
postOrder(root);
printf("\n层次遍历序列:");
levelOrder(root);
printf("\n二叉树的深度:%d\n", getDepth(root));
printf("二叉树中叶子结点的个数:%d\n", getCount(root));
TreeNode *root2 = NULL;
printf("请输入第二棵二叉树的节点值,-1表示空节点:\n");
createTree(&root2);
printf("两棵二叉树是否相等:%d\n", isEqual(root, root2));
swap(root);
printf("交换左右孩子后的二叉树:\n");
levelOrder(root);
printf("\n复制后的二叉树:\n");
TreeNode *newRoot = copy(root);
levelOrder(newRoot);
return 0;
}
```
阅读全文