数据结构实验(3)-二叉树的应用

题目描述

二叉树是一种重要的数据结构，在实际的计算机中有许多重要的用途。本实验需要采用二叉链表的方式对二叉树进行存储，并且提供二叉树的创建、遍历、计算以及处理的功能。

源代码

⑧说了，上代码

注意：本次的代码需要用C++编译

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define OK 1
#define ERROR 0
#define BITREENUM 10

typedef int status;
typedef int TElemntType;

typedef struct Node{
    TElemntType data;
    struct Node *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree QElemType;

typedef struct queueNode {
    QElemType data;
    struct queueNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front; // 队头指针
    QueuePtr rear; // 队尾指针
} LinkQueue;

void intro();
void menu(char &func, int &num);
status create(BiTree &bt);
status traverseTreePreOrder(BiTree bt);
status traverseTreeInOrder(BiTree bt);
status traverseTreePostOrder(BiTree bt);
status traverseTreeLevelOrder(BiTree bt);
int nodeCount(BiTree bt);
int leafCount(BiTree bt);
int heightCount(BiTree bt);
int widthCount(BiTree bt);
status copy(BiTree &oldTree, BiTree &newTree);
status destroy(BiTree &bt);
status initQueue(LinkQueue &Q);
status enQueue(LinkQueue &Q, QElemType e);
status deQueue(LinkQueue &Q, QElemType &e);

int main() {
    // 介绍程序
    intro();

    // 定义数组和变量
    int num;
    char func;
    BiTree bts[BITREENUM + 1] = {NULL}; // 符合人类输入习惯，从1-10

    // 进入主循环
    do{
        menu(func, num);
        switch (func) {
            case 'a':
                printf("\n请按照先序遍历输入，中间用空格隔开，无节点的使用-1表示，如1 -1 -1或者6 4 2 3 -1 -1 -1 -1 5 1 -1 -1 7 -1 -1\n");
                printf("注意：本程序不会检查二叉树是否合法，如果输入非法二叉树，会一直卡在这里，请确保输入的二叉树完整且正确\n");
                create(bts[num]);
                getchar();
                break;
            case 'b':
                if(bts[num] == NULL){
                    printf("该树为空树\n");
                } else{
                    printf("前序遍历：");
                    traverseTreePreOrder(bts[num]);
                    printf("\n中序遍历：");
                    traverseTreeInOrder(bts[num]);
                    printf("\n后序遍历：");
                    traverseTreePostOrder(bts[num]);
                    printf("\n层序遍历：");
                    traverseTreeLevelOrder(bts[num]);
                    printf("\n\n");
                }
                break;
            case 'c':
                if(bts[num] == NULL){
                    printf("该树为空树\n");
                }else{
                    printf("节点数：%d \n",nodeCount(bts[num]));
                    nodeCount(bts[num]);
                    printf("叶子数：%d \n", leafCount(bts[num]));
                    leafCount(bts[num]);
                    printf("高度：%d \n", heightCount(bts[num]));
                    heightCount(bts[num]);
                    printf("宽度：%d \n", widthCount(bts[num]));
                    widthCount(bts[num]);
                }
                break;
            case 'd':
                printf("您选择复制第 %d 颗二叉树，请问您打算把它复制到哪个位置？请输入(1-%d)的数字\n", num, BITREENUM);
                int target;
                scanf("%d", &target);
                getchar();
                copy(bts[num], bts[target]);
                break;
            case 'e':
                destroy(bts[num]);
                bts[num] = NULL;
                break;
            case 'Q':
                exit(OK);
            default:
                printf("输入无效，请重新输入：\n");
                break;
        }
    }while (func != 'Q');

    return 0;
}

void intro() {
    // 本函数用于展示程序一开始的页面，以及使用说明
    printf("**********************************\n");
    printf("*                                *\n");
    printf("*          二叉树运算器            *\n");
    printf("*                                *\n");
    printf("**********************************\n\n");
    printf("本运算器可以实现二叉树的创建、遍历、计算和处理\n");
    printf("\n\n");
}

void menu(char &func, int &num) {
    // 用于展示菜单
    printf("\n请选择需要进行的功能：\n");
    printf("a\t创建二叉树\n");
    printf("b\t遍历二叉树（先序、中序、后序、层序遍历\n");
    printf("c\t二叉树的计算（二叉树的结点数、叶子数、高度、宽度等）\n");
    printf("d\t复制二叉树\n");
    printf("e\t销毁二叉树\n");
    printf("Q\t退出系统\n");
    printf("请输入您想做的功能的序号，并按回车键：\n");
    // 获取输入
    scanf("%c", &func);
    getchar();
    // 获取序号
    printf("本系统可以创建和处理多个二叉树，因此在每次运算前需要输入待处理的数的序号(1-%d)\n",BITREENUM);
    printf("请输入树的序号，推荐从1开始：\n");
    scanf("%d", &num);
    getchar();
}


status create(BiTree &bt){
    // 创建二叉树
    int ch;
    scanf("%d", &ch);
//    printf("%d",ch);
    if(ch == -1){
        bt = NULL;
    } else{
        if(!(bt = (BiTree) malloc(sizeof(BiTNode)))){
            exit(OVERFLOW);
        }
        bt->data = ch;
        create(bt->lchild);
        create(bt->rchild);
    }
    return OK;
}

status traverseTreePreOrder(BiTree bt){
    // 前序遍历二叉树
    if(bt){
        printf("%d ",bt->data);
        traverseTreePreOrder(bt->lchild);
        traverseTreePreOrder(bt->rchild);
    }
}

status traverseTreeInOrder(BiTree bt){
    // 前序遍历二叉树
    if(bt){
        traverseTreeInOrder(bt->lchild);
        printf("%d ",bt->data);
        traverseTreeInOrder(bt->rchild);
    }
}
status traverseTreePostOrder(BiTree bt){
    // 前序遍历二叉树
    if(bt){
        traverseTreePostOrder(bt->lchild);
        traverseTreePostOrder(bt->rchild);
        printf("%d ",bt->data);
    }
}

status initQueue(LinkQueue &Q)
{
    Q.front = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.rear = Q.front;
    return OK;
}

status enQueue(LinkQueue &Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}

status deQueue(LinkQueue &Q, QElemType &e)
{
    // 判断是否为空
    if(Q.front == Q.rear) return ERROR;

    // 待删的：尾的next是头，头的next就是待删皿
    QueuePtr needDe = Q.front->next;
    e = needDe->data;
    if(needDe->next == NULL){
        Q.rear = Q.front;
    }
    // 接上并free
    Q.front->next = needDe->next;
    free(needDe);
}

status traverseTreeLevelOrder(BiTree bt){
    // 层次遍历
    // 使用队列来辅助操作
    LinkQueue q;
    BiTree temp;
    initQueue(q);
    // 根节点入队
    enQueue(q, bt);
    // 主循环
    while (q.front != q.rear){
        // 当队列不为空
        deQueue(q, temp);
        printf("%d ", temp->data);
        if(temp->lchild){
            enQueue(q, temp->lchild);
        }
        if(temp->rchild){
            enQueue(q, temp->rchild);
        }
    }
}

int nodeCount(BiTree bt){
    // 统计节点数
    if(bt == NULL){
        return 0;
    }else{
        return 1 + nodeCount(bt->lchild) + nodeCount(bt->rchild);
    }
}

int leafCount(BiTree bt){
    // 统计叶子节点
    int n = 0;
    if(bt != NULL){
        n = leafCount(bt->lchild);
        if(bt->lchild == NULL && bt->rchild == NULL){
            n++;
        }
        n += leafCount(bt->rchild);
    }
    return n;
}

int heightCount(BiTree bt){
    // 统计高度
    if(bt == NULL){
        return 0;
    }else{
        int m = heightCount(bt->lchild);
        int n = heightCount(bt->rchild);
        return (m>n) ? m+1 : n+1 ;
    }
}

int max(int x1, int x2) {
    return x1 > x2 ? x1 : x2;
}

int widthCount(BiTree bt){
    // 统计宽度
    if(bt ==NULL){
        return 0;
    }
    int maxweight = 0;
    if(bt->lchild == NULL && bt->rchild == NULL){
        return 1;
    }else{
        maxweight = max(widthCount(bt->lchild)+ widthCount(bt->rchild), maxweight);
    }
    return maxweight;
}

status copy(BiTree &oldTree, BiTree &newTree){
    // 复制树，将oldTree复制到newTree上
    if(oldTree){
        newTree = (BiTree) malloc(sizeof(BiTNode));
        if(!newTree){
            exit(OVERFLOW);
        }
        newTree->data = oldTree->data;
        newTree->lchild = oldTree->lchild;
        newTree->rchild = oldTree->rchild;
        copy(oldTree->lchild, newTree->lchild);
        copy(oldTree->rchild, newTree->rchild);
    }
}

status destroy(BiTree &bt){
    // 销毁二叉树，采用后序遍历
    if(bt){
        destroy(bt->lchild);
        destroy(bt->rchild);
        free(bt);
    }
}