二叉树的链式存储结构,实现二叉树的建立,先序遍历,后序遍历,中序遍历,统计叶子个数的操作的全部代码
时间: 2023-12-01 11:55:00 浏览: 73
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
5星 · 资源好评率100%
好的,下面是二叉树的链式存储结构,以及实现二叉树的建立,先序遍历,后序遍历,中序遍历,统计叶子个数的全部代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的结点
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 二叉树的链式存储结构
typedef struct BinaryTree {
TreeNode *root; // 根节点指针
int count; // 叶子节点个数
} BinaryTree;
// 创建一个新的节点
TreeNode *NewNode(int val) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 建立二叉树
void CreateBinaryTree(TreeNode **root) {
int val;
scanf("%d", &val);
if (val != -1) {
*root = NewNode(val);
CreateBinaryTree(&((*root)->left));
CreateBinaryTree(&((*root)->right));
}
}
// 二叉树先序遍历
void PreorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
PreorderTraversal(root->left);
PreorderTraversal(root->right);
}
// 二叉树中序遍历
void InorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
InorderTraversal(root->left);
printf("%d ", root->val);
InorderTraversal(root->right);
}
// 二叉树后序遍历
void PostorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
PostorderTraversal(root->left);
PostorderTraversal(root->right);
printf("%d ", root->val);
}
// 统计叶子节点个数
void CountLeafNode(TreeNode *root, int *count) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
(*count)++;
}
CountLeafNode(root->left, count);
CountLeafNode(root->right, count);
}
int main() {
BinaryTree binaryTree;
binaryTree.root = NULL;
binaryTree.count = 0;
printf("请输入二叉树的节点,-1表示空节点:\n");
CreateBinaryTree(&(binaryTree.root));
printf("先序遍历结果为:");
PreorderTraversal(binaryTree.root);
printf("\n中序遍历结果为:");
InorderTraversal(binaryTree.root);
printf("\n后序遍历结果为:");
PostorderTraversal(binaryTree.root);
CountLeafNode(binaryTree.root, &(binaryTree.count));
printf("\n叶子节点个数为:%d\n", binaryTree.count);
return 0;
}
```
感谢您的提问!
阅读全文