博客

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10

/*
 * 二叉树的层次建立: 借助辅助队列
 * */

// 二叉树的类型定义
typedef struct TNode {
    int data;
    struct TNode* lchild, * rchild;
}BinNode, * BinTree;

// 辅助队列:顺序队
typedef struct QueueNode {
    struct TNode* nodes[MaxSize];
    int front, rear;
}QueueNode, * LinkQueue;


// 队列初始化
void initQueue(LinkQueue lq) {
    lq->front = lq->rear = 0;
}


// 判满
int isFull(LinkQueue lq) {
    if ((lq->rear + 1) % MaxSize == lq->front)return 1;
    else return 0;
}

// 判空
int isEmpty(LinkQueue lq) {
    if (lq->front == lq->rear)return 1;
    return 0;
}

//出队
BinNode* delQueue(LinkQueue lq) {
    if (isEmpty(lq))return NULL;
    BinNode* p = lq->nodes[lq->front];
    lq->front = (lq->front + 1) % MaxSize;
    return p;
}

// 入队
int enQueue(LinkQueue lq, struct TNode* node) {
    if (isFull(lq))return 0;
    lq->nodes[lq->rear++] = node;
    return 1;
}

// 取队头元素
BinNode* getFront(LinkQueue lq) {
    return lq->nodes[lq->front];
}


BinNode* CreateNode(int key) {
    BinNode* node = (BinNode*)malloc(sizeof(BinNode));
    node->data = key;
    node->rchild = node->lchild = NULL;
    return node;
};

// 二叉树的遍历先序遍历
void preOrder(BinTree root) {
    if (root) {
        printf("%d\n", root->data);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}


int main() {

    // 树
    BinTree root = NULL; // 指向二叉树的根节点
    BinNode* pnew; //新结点


    // 队列
    LinkQueue lq = (LinkQueue)malloc(sizeof(QueueNode));
    initQueue(lq);

    int key = 0;
    scanf("%d", &key);
    while (key != -1) {
        pnew = CreateNode(key);
        if (root == NULL){
            enQueue(lq, pnew);// 将新结点入队
            root = pnew; //树根指向根结点
        }
        else {
            enQueue(lq, pnew); // 将新结点入队
            if (getFront(lq)->lchild == NULL)getFront(lq)->lchild = pnew; // 判断对头元素是否有左孩子，如果没有就将新结点加入到对头元素的左孩子中
            else if (getFront(lq)->rchild == NULL) { // 判断对头元素是否有右孩子，如果没有就将新结点加入到对头元素的右孩子中
                getFront(lq)->rchild = pnew;
                delQueue(lq); // 出队操作，表示当前对头元素左右孩子都满了
            }
        }
        scanf("%d", &key);
    }

    preOrder(root);
}