二叉树的基本操作 内容:使用二叉链表存储结构建立一棵二叉树,完成如下功能: 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数用c语言
时间: 2023-11-14 13:18:48 浏览: 106
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
以下是使用二叉链表存储结构构建二叉树的基本操作的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
TreeNode* root = NULL;
int value;
scanf("%d", &value);
if (value != -1) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = value;
root->left = createTree();
root->right = createTree();
}
return root;
}
// 先序遍历二叉树
void preOrder(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
// 中序遍历二叉树
void inOrder(TreeNode* root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
// 后序遍历二叉树
void postOrder(TreeNode* root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
// 求二叉树深度
int getDepth(TreeNode* root) {
if (root == NULL) {
return 0;
} else {
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
}
// 求二叉树叶子结点个数
int getCount(TreeNode* root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return getCount(root->left) + getCount(root->right);
}
}
// 主函数
int main() {
printf("请输入二叉树的先序遍历序列(-1表示空结点):\n");
TreeNode* root = createTree();
printf("先序遍历序列:");
preOrder(root);
printf("\n中序遍历序列:");
inOrder(root);
printf("\n后序遍历序列:");
postOrder(root);
printf("\n二叉树深度:%d\n", getDepth(root));
printf("叶子结点个数:%d\n", getCount(root));
return 0;
}
```
使用方法:输入二叉树的先序遍历序列,-1表示空结点,例如输入:`1 2 -1 -1 3 4 -1 -1 5 -1 -1`,即可获得相应的二叉树先序、中序、后序遍历序列、深度和叶子结点个数。
阅读全文