利用c语言帮我写个代码,有以下要求:1.从键盘输入扩展二叉树的先序遍历序列,构建另一棵二叉树; 2.交换二叉树中所有度为2的结点的左右子树,输出交换后的二叉树中序遍历序列; 3.统计二叉树中左右子树高度相等的结点数。(注意:叶子节点也算高度相等)
时间: 2024-01-23 19:39:00 浏览: 69
好的,我可以帮您编写这个程序。以下是代码:
```
#include<stdio.h>
#include<stdlib.h>
//定义二叉树的结构体
typedef struct BiTNode{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
//扩展先序遍历序列构建二叉树
void CreateBiTree(BiTree *T){
char ch;
scanf("%c", &ch);
if(ch == '#'){
*T = NULL;
}
else{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
}
//交换二叉树中所有度为2的结点的左右子树
void SwapTree(BiTree T){
if(T != NULL){
if(T->lchild != NULL && T->rchild != NULL){
BiTree temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}
SwapTree(T->lchild);
SwapTree(T->rchild);
}
}
//中序遍历二叉树
void InOrderTraverse(BiTree T){
if(T != NULL){
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
}
//计算二叉树中左右子树高度相等的结点数
int EqualHeightNode(BiTree T){
if(T == NULL){
return 0;
}
else{
int lh = EqualHeightNode(T->lchild);
int rh = EqualHeightNode(T->rchild);
if(lh == rh){
return lh + rh + 1;
}
else{
return lh + rh;
}
}
}
int main(){
printf("请输入扩展二叉树的先序遍历序列:\n");
BiTree T;
CreateBiTree(&T);
printf("交换前二叉树中序遍历序列为:");
InOrderTraverse(T);
printf("\n");
SwapTree(T);
printf("交换后二叉树中序遍历序列为:");
InOrderTraverse(T);
printf("\n");
int num = EqualHeightNode(T);
printf("左右子树高度相等的结点数为:%d\n", num);
return 0;
}
```
希望这个代码对您有帮助。如果您有任何问题,请随时问我。
阅读全文