用c语言实现:建立二叉树并输出下列二叉树的(1)结点个数;(2)叶子结点个数;(3)深度;(4)先序序列、中序序列和后序序列。
时间: 2023-12-08 07:08:55 浏览: 73
好的,下面是用C语言实现建立二叉树并输出相关信息的代码:
```c
#include <stdio.h>
#include <stdlib.h>
/*二叉树的结构体*/
typedef struct TreeNode {
int data; // 存放数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode, *TreeNodePtr;
/*建立二叉树*/
TreeNodePtr createTree() {
int data;
TreeNodePtr root;
scanf("%d", &data);
if (data == -1) {
root = NULL;
} else {
root = (TreeNodePtr)malloc(sizeof(TreeNode));
root->data = data;
root->left = createTree();
root->right = createTree();
}
return root;
}
/*计算二叉树结点个数*/
int countNode(TreeNodePtr root) {
if (root == NULL) {
return 0;
} else {
return countNode(root->left) + countNode(root->right) + 1;
}
}
/*计算二叉树叶子结点个数*/
int countLeaf(TreeNodePtr root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return countLeaf(root->left) + countLeaf(root->right);
}
}
/*计算二叉树深度*/
int getDepth(TreeNodePtr root) {
if (root == NULL) {
return 0;
} else {
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
}
/*先序遍历二叉树*/
void preOrder(TreeNodePtr root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
/*中序遍历二叉树*/
void inOrder(TreeNodePtr root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
/*后序遍历二叉树*/
void postOrder(TreeNodePtr root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
int main() {
TreeNodePtr root;
int nodeCount, leafCount, depth;
printf("请输入二叉树的先序遍历序列(以-1表示空节点):\n");
root = createTree();
nodeCount = countNode(root);
printf("结点个数为:%d\n", nodeCount);
leafCount = countLeaf(root);
printf("叶子结点个数为:%d\n", leafCount);
depth = getDepth(root);
printf("深度为:%d\n", depth);
printf("先序遍历序列为:");
preOrder(root);
printf("\n");
printf("中序遍历序列为:");
inOrder(root);
printf("\n");
printf("后序遍历序列为:");
postOrder(root);
printf("\n");
return 0;
}
```
使用方法:
- 编译运行上面的代码
- 输入二叉树的先序遍历序列(以-1表示空节点)
- 输出相关信息,包括结点个数、叶子结点个数、深度、先序序列、中序序列和后序序列
希望能够帮到你!
阅读全文