请用C语言编程:按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
时间: 2024-01-23 11:45:44 浏览: 114
以下是用C语言编写的程序,实现按先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度。
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
int data;
struct TreeNode *lchild;
struct TreeNode *rchild;
}TreeNode, *BiTree;
// 创建二叉树
void createBiTree(BiTree *T){
int data;
scanf("%d", &data);
if(data == -1){
*T = NULL;
}else{
*T = (TreeNode *)malloc(sizeof(TreeNode));
(*T)->data = data;
createBiTree(&((*T)->lchild));
createBiTree(&((*T)->rchild));
}
}
// 统计叶子结点个数
int countLeafNode(BiTree T){
if(!T) return 0;
if(!T->lchild && !T->rchild) return 1;
return countLeafNode(T->lchild) + countLeafNode(T->rchild);
}
// 计算二叉树深度
int getDepth(BiTree T){
int leftDepth, rightDepth;
if(!T) return 0;
leftDepth = getDepth(T->lchild);
rightDepth = getDepth(T->rchild);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
int main(){
BiTree T;
printf("请输入先序遍历序列:\n");
createBiTree(&T);
printf("叶子结点个数:%d\n", countLeafNode(T));
printf("二叉树深度:%d\n", getDepth(T));
return 0;
}
```
程序的运行结果如下:
```
请输入先序遍历序列:
1 2 -1 -1 3 -1 4 -1 -1
叶子结点个数:2
二叉树深度:3
```
以上程序中,createBiTree()函数用于创建二叉树,countLeafNode()函数用于统计二叉树中叶子结点的个数,getDepth()函数用于计算二叉树的深度。主函数中先要输入先序遍历序列来创建二叉树,然后调用countLeafNode()和getDepth()函数来统计叶子结点个数和计算二叉树深度,最后输出结果。
阅读全文