以二叉链表作为二叉树的存储结构,请用 C 语言请分别编写以下算法: (1)从键盘输入数据,按前序次序建立一棵二叉树,以'#'表示空; (2)统计二叉树中左右子树高度相同的结点个数。 typedef char elemtype ; typedef struct node ( elemtype data ; struct node * Ichild ,* rchild ;} bittree ;//二叉链表 请使用以定义和基本操作完成如下两个函数定义。 bittree * create ();//先序遍历次序建立一棵二叉树 int equaldepth ( bittree * root )// root 指向二叉树根结点,返回结点个数
时间: 2024-03-17 08:41:33 浏览: 16
以下是对应的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef char elemtype;
typedef struct node {
elemtype data;
struct node *lchild, *rchild;
} bittree;
// 先序遍历建立二叉树
bittree* create() {
elemtype data;
scanf("%c", &data);
if (data == '#') {
return NULL;
}
bittree *root = (bittree*)malloc(sizeof(bittree));
root->data = data;
root->lchild = create();
root->rchild = create();
return root;
}
// 获取二叉树的深度
int get_depth(bittree *root) {
if (root == NULL) {
return 0;
}
int left_depth = get_depth(root->lchild);
int right_depth = get_depth(root->rchild);
return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}
// 统计二叉树中左右子树高度相同的结点个数
int equaldepth(bittree *root) {
if (root == NULL) {
return 0;
}
int left_depth = get_depth(root->lchild);
int right_depth = get_depth(root->rchild);
int count = 0;
if (left_depth == right_depth) {
count = 1;
}
return count + equaldepth(root->lchild) + equaldepth(root->rchild);
}
int main() {
printf("请输入先序遍历序列,以 '#' 表示空节点:\n");
bittree *root = create();
int count = equaldepth(root);
printf("左右子树高度相同的结点个数为: %d\n", count);
return 0;
}
```
这里的 `create()` 函数使用了递归的方式,按照先序遍历的顺序从键盘输入数据来构建二叉树。`equaldepth()` 函数则是递归地获取每个节点的左子树和右子树的深度,如果深度相等,则说明该节点符合条件,加入计数器中。最后返回计数器的值即可。