C语言编程,以二叉链表作为二叉树的存储结构,编写以下算法: 1.统计二叉树的叶结点个数。 2.判别两棵树是否相等。 3.交换二叉树每个结点的左孩子和右孩子。 4.设计二叉树的双序遍历算法。
时间: 2024-03-19 21:43:33 浏览: 74
编写一个将二叉树中每个结点的左右孩子交换的算法。
好的,我来分别回答您的问题:
1. 统计二叉树的叶结点个数
统计二叉树的叶结点个数可以采用递归的方式实现。具体算法如下:
```
int count_leaf_node(BiTree T) {
if (T == NULL) {
return 0;
} else if (T->lchild == NULL && T->rchild == NULL) {
return 1;
} else {
return count_leaf_node(T->lchild) + count_leaf_node(T->rchild);
}
}
```
2. 判别两棵树是否相等
判别两棵树是否相等也可以采用递归的方式实现。具体算法如下:
```
int is_same_tree(BiTree T1, BiTree T2) {
if (T1 == NULL && T2 == NULL) {
return 1;
}
if (T1 == NULL || T2 == NULL) {
return 0;
}
if (T1->data != T2->data) {
return 0;
}
return is_same_tree(T1->lchild, T2->lchild) && is_same_tree(T1->rchild, T2->rchild);
}
```
3. 交换二叉树每个结点的左孩子和右孩子
交换二叉树每个结点的左孩子和右孩子可以采用递归的方式实现。具体算法如下:
```
void swap_left_right(BiTree T) {
if (T == NULL) {
return;
}
BiTree temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
swap_left_right(T->lchild);
swap_left_right(T->rchild);
}
```
4. 设计二叉树的双序遍历算法
二叉树的双序遍历算法是指先序遍历和后序遍历的结合。具体算法如下:
```
void double_order(BiTree T) {
if (T == NULL) {
return;
}
printf("%c ", T->data);
double_order(T->lchild);
printf("%c ", T->data);
double_order(T->rchild);
printf("%c ", T->data);
}
```
阅读全文