完成二叉树的链式存储结构的表示及基本操作实现(构造二叉树、先序遍历二叉树、中 序遍历二叉树、后序遍历二叉树、测二叉树高度、统计二叉树结点数、统计二叉树叶子结点 数目)。
时间: 2024-04-29 18:17:31 浏览: 15
二叉树的链式存储结构是通过节点之间的指针来表示二叉树的结构关系。每个节点包含一个数据元素和两个指针,分别指向左子树和右子树。
下面是基本操作的实现:
1. 构造二叉树:可以通过递归的方式构造二叉树。首先创建一个根节点,然后递归地构造左子树和右子树。
2. 先序遍历二叉树:先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。
3. 中序遍历二叉树:先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
4. 后序遍历二叉树:先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
5. 测二叉树高度:可以通过递归的方式计算二叉树的高度。如果二叉树为空,则高度为0;否则,高度等于左子树高度和右子树高度的较大值加1。
6. 统计二叉树结点数:可以通过递归的方式统计二叉树的结点数。如果二叉树为空,则结点数为0;否则,结点数等于左子树结点数加右子树结点数再加1。
7. 统计二叉树叶子结点数目:可以通过递归的方式统计二叉树的叶子结点数目。如果二叉树为空,则叶子结点数目为0;如果二叉树只有一个结点,则叶子结点数目为1;否则,叶子结点数目等于左子树叶子结点数目加右子树叶子结点数目。
相关问题
二叉树的链式存储结构,实现二叉树的建立,先序遍历,后序遍历,中序遍历,统计叶子个数的操作
二叉树的链式存储结构是通过指针实现的,在定义二叉树节点时,除了存储节点的数据域之外,还需要定义两个指针分别指向该节点的左子树和右子树。
以下是二叉树的链式存储结构的 C++ 实现:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
```
接下来,我们实现二叉树的建立、先序遍历、后序遍历、中序遍历和统计叶子个数的操作。
建立二叉树:
```
TreeNode* buildTree() {
int val;
cin >> val;
if (val == -1) { // -1表示空节点
return nullptr;
}
TreeNode* root = new TreeNode(val);
root->left = buildTree();
root->right = buildTree();
return root;
}
```
先序遍历:
```
void preOrder(TreeNode* root) {
if (!root) {
return;
}
cout << root->val << ' ';
preOrder(root->left);
preOrder(root->right);
}
```
后序遍历:
```
void postOrder(TreeNode* root) {
if (!root) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << ' ';
}
```
中序遍历:
```
void inOrder(TreeNode* root) {
if (!root) {
return;
}
inOrder(root->left);
cout << root->val << ' ';
inOrder(root->right);
}
```
统计叶子个数:
```
int countLeaves(TreeNode* root) {
if (!root) {
return 0;
}
if (!root->left && !root->right) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
```
以上就是二叉树的链式存储结构及相关操作的实现。
二叉树的链式存储结构,实现二叉树的建立,先序遍历,后序遍历,中序遍历,统计叶子个数的操作的全部代码
好的,下面是二叉树的链式存储结构,以及实现二叉树的建立,先序遍历,后序遍历,中序遍历,统计叶子个数的全部代码:
```
#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;
}
```
感谢您的提问!