写一个基于刚才结点结构体的完全二叉树创建代码
时间: 2024-01-24 15:02:47 浏览: 25
好的,下面是一个基于刚才的结点结构体定义的完全二叉树创建代码,可以根据用户输入的数据构建一棵完全二叉树:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef int TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 队列结构体
typedef struct {
BiTree data[MAX_SIZE];
int front, rear;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}
// 入队
int enQueue(Queue *q, BiTree t) {
if ((q->rear + 1) % MAX_SIZE == q->front) return 0; // 队满
q->data[q->rear] = t;
q->rear = (q->rear + 1) % MAX_SIZE;
return 1;
}
// 出队
int deQueue(Queue *q, BiTree *t) {
if (isEmpty(q)) return 0; // 队空
*t = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return 1;
}
// 创建完全二叉树
void createCompleteBiTree(BiTree *root) {
Queue q;
initQueue(&q);
*root = NULL;
TElemType data;
printf("请输入完全二叉树的结点数据,以 -1 结束:\n");
while (scanf("%d", &data) != EOF && data != -1) {
BiTree node = (BiTree) malloc(sizeof(BiNode));
node->data = data;
node->lchild = node->rchild = NULL;
enQueue(&q, node);
if (*root == NULL) {
*root = node;
} else {
BiTree front;
if (deQueue(&q, &front)) {
if (front->lchild == NULL) {
front->lchild = node;
} else if (front->rchild == NULL) {
front->rchild = node;
}
enQueue(&q, front);
}
}
}
}
// 中序遍历
void inOrderTraverse(BiTree root) {
if (root == NULL) return;
inOrderTraverse(root->lchild);
printf("%d ", root->data);
inOrderTraverse(root->rchild);
}
int main() {
BiTree root;
createCompleteBiTree(&root);
printf("中序遍历结果:\n");
inOrderTraverse(root);
printf("\n");
return 0;
}
```
这个代码使用队列实现了完全二叉树的创建,用户输入数据时按照完全二叉树的顺序插入节点,同时使用队列记录每个节点的位置,便于后续操作。最后使用中序遍历对创建好的完全二叉树进行遍历,输出结果。