用C语言完成二叉树二叉链表结构的定义,用递归算法实现二叉链表创建二叉树,并实现先序、中序和后序遍历算法,实现二叉树求结点个数,求树的高度,求叶子结点数、交换二叉树左右子树的算法。
时间: 2023-06-03 07:07:14 浏览: 158
常用的数据结构的算法,包括二叉树的三种递归和非递归算法,染色问题,八皇后问题,深度广度遍历,约瑟夫环,数值转换,树的高度和叶子节
好的,我可以回答您的问题。以下是 C 语言完成二叉树二叉链表结构的定义以及递归算法实现二叉链表创建二叉树的代码。
```
// 定义二叉树结点结构体
typedef struct BiTreeNode {
int data; // 数据域
struct BiTreeNode *lchild; // 左子节点指针
struct BiTreeNode *rchild; // 右子节点指针
} BiTreeNode, *BiTree;
// 递归创建二叉树
void createBiTree(BiTree *T) {
int data;
scanf("%d", &data); // 输入结点数据
if (data == -1) { // 如果数据为-1,表示该节点为空节点
*T = NULL;
return;
}
*T = (BiTreeNode *)malloc(sizeof(BiTreeNode)); // 创建新节点
(*T)->data = data; // 将数据域赋值
createBiTree(&(*T)->lchild); // 递归创建左子树
createBiTree(&(*T)->rchild); // 递归创建右子树
}
// 先序遍历
void preOrder(BiTree T) {
if (T) { // 如果结点不为空
printf("%d ", T->data); // 输出结点数据
preOrder(T->lchild); // 遍历左子树
preOrder(T->rchild); // 遍历右子树
}
}
// 中序遍历
void inOrder(BiTree T) {
if (T) { // 如果结点不为空
inOrder(T->lchild); // 遍历左子树
printf("%d ", T->data); // 输出结点数据
inOrder(T->rchild); // 遍历右子树
}
}
// 后序遍历
void postOrder(BiTree T) {
if (T) { // 如果结点不为空
postOrder(T->lchild); // 遍历左子树
postOrder(T->rchild); // 遍历右子树
printf("%d ", T->data); // 输出结点数据
}
}
// 求结点个数
int countNodes(BiTree T) {
if (T == NULL) { // 如果树为空,返回0
return 0;
} else { // 如果树不为空,返回左子树结点数加上右子树结点数再加1
return countNodes(T->lchild) + countNodes(T->rchild) + 1;
}
}
// 求树的高度
int getTreeHeight(BiTree T) {
int hl, hr;
if (T == NULL) { // 如果树为空,返回0
return 0;
} else { // 如果树不为空,返回左右子树高度较大者再加1
hl = getTreeHeight(T->lchild);
hr = getTreeHeight(T->rchild);
return hl > hr ? hl + 1 : hr + 1;
}
}
// 求叶子结点数
int getLeafCount(BiTree T) {
if (T == NULL) { // 如果树为空,返回0
return 0;
} else if (T->lchild == NULL && T->rchild == NULL) { // 如果当前结点为叶子结点,返回1
return 1;
} else { // 如果当前结点不是叶子结点,返回左右子树叶子结点数之和
return getLeafCount(T->lchild) + getLeafCount(T->rchild);
}
}
// 交换二叉树左右子树
void swapBiTree(BiTree T) {
BiTreeNode *tmp;
if (T == NULL) { // 如果树为空,直接返回
return;
} else { // 如果树不为空,递归交换左右子树
tmp = T->lchild;
T->lchild = T->rchild;
T->rchild = tmp;
swapBiTree(T->lchild);
swapBiTree(T->rchild);
}
}
```
以上是题目所要求的C语言代码,您可以根据需要进行修改和测试。请注意,该代码仅为算法实现示例,并非生产环境可用代码。同时,如您的问题是关于以上CSDN ChitGPT所能回答的技术问题,我会根据我的功能给出尽可能准确的回答。
阅读全文