二叉树的基本操作包括二叉树的定义 二叉树的建立 二叉树的遍历(先序,中序,后序,层序) 求二叉树的深度 求二叉树的叶子个数 求二叉树的结点个数,用C语言写一个可运行有主函数的代码。
时间: 2024-05-10 19:12:04 浏览: 94
二叉树是一种树形结构,其中每个节点最多有两个子节点,称为左子节点和右子节点。二叉树的基本操作包括:
1. 二叉树的定义:二叉树可以为空,或者由一个根节点和两个分别称为左子树和右子树的二叉树组成。
2. 二叉树的建立:可以通过手动输入节点信息或者按照某种规律自动生成节点信息来建立二叉树。
3. 二叉树的遍历:
(1) 先序遍历:先访问根节点,再遍历左子树,最后遍历右子树。
(2) 中序遍历:先遍历左子树,再访问根节点,最后遍历右子树。
(3) 后序遍历:先遍历左子树,再遍历右子树,最后访问根节点。
(4) 层序遍历:按照从上到下、从左到右的顺序依次遍历每一层的所有节点。
4. 求二叉树的深度:二叉树的深度为其根节点到最远叶子节点的路径上节点数的最大值。
5. 求二叉树的叶子个数:二叉树中没有子节点的节点称为叶子节点,求二叉树的叶子个数就是统计二叉树中叶子节点的个数。
6. 求二叉树的结点个数:统计二叉树中所有节点的个数,包括根节点、左子树和右子树上的所有节点。
以下是用C语言实现以上操作的代码(包含主函数):
```c
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
//创建新节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
//插入节点
TreeNode* insertNode(TreeNode* root, int val) {
if (root == NULL) {
return createNode(val);
}
if (val < root->val) {
root->left = insertNode(root->left, val);
} else if (val > root->val) {
root->right = insertNode(root->right, val);
}
return root;
}
//先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preOrder(root->left);
preOrder(root->right);
}
//中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%d ", root->val);
inOrder(root->right);
}
//后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->val);
}
//层序遍历
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
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 maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//求二叉树叶子个数
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
//求二叉树结点个数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
int main() {
TreeNode* root = NULL;
//插入节点
root = insertNode(root, 10);
insertNode(root, 8);
insertNode(root, 15);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 12);
//先序遍历
printf("Preorder traversal: ");
preOrder(root);
//中序遍历
printf("\nInorder traversal: ");
inOrder(root);
//后序遍历
printf("\nPostorder traversal: ");
postOrder(root);
//层序遍历
printf("\nLevelorder traversal: ");
levelOrder(root);
//求深度
printf("\nDepth of the tree: %d", maxDepth(root));
//求叶子个数
printf("\nNumber of leaves in the tree: %d", countLeaves(root));
//求结点个数
printf("\nNumber of nodes in the tree: %d", countNodes(root));
return 0;
}
```
阅读全文
相关推荐

















