《数据结构》课程设计说明书
                   
二叉平衡树算法实现
班  级
组    别：
二
指导老师：
完成时间：
2019.6.19
组    长：
学    号：
05
组  员 1：
学    号：
33
组  员 2：
学    号：
组  员 3：
学    号：
成    绩：
   

一、
课题设计任务
针对给定的序列建立存储结构，实现各种遍历；实现树的生成，实现数据的查、插入、删除，输出各种遍历。
二、任务分析
1.数据逻辑结构（算法描述）
//中序--递归
void InorderTra(PNode root) {
    if (root) {
        InorderTra(root->leftChild);      //中序遍历左子树
        printf("%d\t", root->keyValue);    //访问根节点
        InorderTra(root->rightChild);      //中序遍历右子数
    }
}
//前序--递归
void PreOrderTra(PNode root) {
    if (root != NULL) {
        printf("%d\t", root->keyValue);    //访问根节点
        PreOrderTra(root->leftChild);      //前序遍历左子树
        PreOrderTra(root->rightChild);    //前序遍历右子数
    }二叉树中序遍历非递归算法
   
}
//后序--递归
void PostOrderTra(PNode root) {
    if (root) {
        PostOrderTra(root->leftChild);      //后序遍历左子树
        PostOrderTra(root->rightChild);    //后序遍历右子树
        printf("%d\t", root->keyValue);    //访问根节点
    }
}
//求树的最大深度
int getDeep(PNode root) {
    if (!root) {
        return 0;
    }
    int leftDeep = getDeep(root->leftChild) + 1;
    int rightDeep = getDeep(root->rightChild) + 1;
    return leftDeep > rightDeep ? leftDeep : rightDeep;
}
//从根节点开始打印出所有层
void printByLevel(PNode root, int deep) {
    for (int i = 0; i < deep; i++) {
        LevelOrderTra(root, i);
    }
    printf("\n");
}
2.关键算法思想
树的生成过程保持左右平衡，插入删除过程中保证树的平衡。
三、概要设计（总体设计）
包括功能模块的划分，各模块的调用关系图，程序总体流程图等。
四、详细设计
1.数据存储结构
树的结构体
typedef struct Node {
    dataType keyValue;            //数据
    int BalanceFactor;            //平衡因子
    struct Node *leftChild, *rightChild;
}*PNode
2.各模块流程图及算法
树的元素插入
int InsertKeyValue(PNode* node, dataType keyValue,bool* higher) {
    if ((*node) == NULL) {                                    //树中不包含此键值，则新建一个节点，
    (*node) = createNode(keyValue);
    *higher=true;
    }
else if ((*node)->keyValue == keyValue) {                //树中已经包含此键值，则不需要插入
        *higher = false;
        return 0;
    }
    else if (keyValue < (*node)->keyValue) {                  //插入到左子树中
        if (!InsertKeyValue(&(*node)->leftChild, keyValue, higher))  //如果左子树中存在该节点
            return 0;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。