m0_71659698 2022-12-17 18:02 采纳率: 100%
浏览 10
已结题

数据结构二叉树修改BUG


//删除整棵子树有点问题
/*
left                        长子
left的parent                双亲
right                        下一个兄弟
right的parent                是上一个兄弟
p=p1->parent;
if(p->left == p1) p就是p1的双亲
if(p->right == p1) p就是p1的上一个兄弟
*/
#include "stdlib.h"
#include "string.h"
#include"stdio.h"
#define MAX 1500
struct Category {//类别节点
    int cate_id, parent_cid,
        cate_level, show_status, sort;
    char name[40];
};
struct Tree {//树节点
    Tree* left;
    Tree* right;
    Tree* parent;
    Category* data;
};
struct DNode {  //双向链表节点
    DNode* prev;
    DNode* next;
    Category* data;//T *data;
};
struct DList {//双向链表
    DNode* p_head, * p_end;
    int length;
};
/*
功能:双向链表的初始化
返回值:双向链表指针
*/
DList* initDList() {
    DList* p;
    p = (DList*)malloc(sizeof(DList));//双向链表数据,不是双向链表中节点数据
    //设置p成员
    p->p_head = (DNode*)malloc(sizeof(DNode));
    p->p_end = (DNode*)malloc(sizeof(DNode));
    p->length = 0;
    //设置p->p_head表头节点的成员
    p->p_head->prev = NULL;
    p->p_head->next = p->p_end;
    //设置p->p_head表尾节点的成员
    p->p_end->next = NULL;
    p->p_end->prev = p->p_head;
    return p;
}
//以下三个函数是同一类型的函数
/*
功能:
参数:
作者:
时间:
*/
void displayCategory(Category* p) {
    printf("%d\t%s\t%d\t%d\t%d\t%d\n", p->cate_id, p->name, p->parent_cid, p->cate_level, p->show_status, p->sort);
}
void displayCategoryName(Category* p) {
    printf("%s\n", p->name);
}
void displayCategoryIdName(Category* p) {
    printf("%d.%s\n", p->cate_id, p->name);
}
void displayList(DList* pList) {
    DNode* p1 = pList->p_head->next;
    while (p1 != pList->p_end) {
        displayCategory(p1->data);
        p1 = p1->next;
    }
}
/*
以下两个函数是同一类型的函数()
int add(int, int) {}
int sub(int, int) {}
*/
//函数指针做另一个函数的参数,实参是函数名,作用是选择执行哪个函数
void displayList(DList* pList, void (*fn)(Category*)) {
    DNode* p1 = pList->p_head->next;
    while (p1 != pList->p_end) {
        fn(p1->data);
        p1 = p1->next;
    }
}
/*
功能:构建成绩节点
*/
Category* newCategory(int cate_id, char* name, int parent_cid, int cate_level, int show_status, int sort) {
    Category* p;
    p = (Category*)malloc(sizeof(Category));
    if (p == NULL)return NULL;
    p->cate_id = cate_id;
    strcpy_s(p->name, name);
    p->parent_cid = parent_cid;
    p->cate_level = cate_level;
    p->show_status = show_status;
    p->sort = sort;
    return p;
}
Category* newCategory() {
    Category* p;
    p = (Category*)malloc(sizeof(Category));
    if (p == NULL)return NULL;
    return p;
}
/*
构建链表节点
*/
DNode* newDNode(int cate_id, char* name, int parent_cid, int cate_level, int show_status, int sort) {
    DNode* pDNode;
    Category* p_cate;
    //申请struct Score,初始化成绩数据
    p_cate = newCategory(cate_id, name, parent_cid, cate_level, show_status, sort);

    //申请struct DNode<struct Score*>
    pDNode = (DNode*)malloc(sizeof(DNode));
    if (p_cate != NULL && pDNode != NULL) {
        //初始化链表节点
        pDNode->prev = pDNode->next = NULL;
        pDNode->data = p_cate;
    }
    return pDNode;
}
DNode* newDNode() {
    DNode* pDNode;

    //申请struct DNode<struct Score*>
    pDNode = (DNode*)malloc(sizeof(DNode));

    pDNode->prev = pDNode->next = NULL;
    pDNode->data = NULL;
    return pDNode;
}
/*
功能:链表节点插入
参数:
pList:链表指针
p1:插入位置(p1之前)
p2:待插节点
*/
void insertNode(DList* pList, DNode* p1, DNode* p2) {

    if (p1 == NULL || p1->prev == NULL) {
        printf("插入位置设置错误!\n");
        return;
    }
    if (p2 == NULL) {
        printf("待插节点不能为空!\n");
    }
    p2->next = p1;
    p2->prev = p1->prev;
    p1->prev->next = p2;
    p1->prev = p2;
    pList->length++;
}
/*
功能:读取文件中类别数据放入到链表中
入口参数:
fileName:文件名
cate_level:类别层次
返回值:新生成的双向链表的指针

*/
DList* readFile(char* fileName) {
    DList* p_list;
    p_list = initDList();
    FILE* fp2 = fopen(fileName, "r");

    if (fp2 == NULL) {
        printf("文件读打开失败!");
        return p_list;
    }
    DNode* p_new;
    Category* p;
    char str[100];
    fgets(str, 100, fp2);
    int i = 0;
    while (!feof(fp2)) {
        p = newCategory();
        fscanf(fp2, "%d\t%s\t%d\t%d\t%d\t%d\n",
            &p->cate_id, p->name, &p->parent_cid, &p->cate_level, &p->show_status, &p->sort);
#ifdef debug
        displayCategory(p);
#endif
        p_new = newDNode();
        p_new->data = p;
        insertNode(p_list, p_list->p_end, p_new);
#ifdef debug
        if (++i == MAX)
            break;
#endif
    }
    fclose(fp2);
    printf("===========end of readFile==========\n");
    return p_list;
}
Tree* newTreeNode() {
    Tree* p = (Tree*)malloc(sizeof(Tree));
    p->parent = NULL;
    p->left = NULL;
    p->right = NULL;
    p->data = NULL;
    return p;
}
Tree* newTreeNode(Category* data) {
    Tree* p = (Tree*)malloc(sizeof(Tree));
    p->parent = NULL;
    p->left = NULL;
    p->right = NULL;
    p->data = data;
    return p;
}
Tree* newTreeNode(Tree* left, Tree* parent, Tree* right, Category* data) {
    Tree* p = (Tree*)malloc(sizeof(Tree));
    p->parent = parent;
    p->left = left;
    p->right = right;
    p->data = data;
    return p;
}
Tree* initTree() {
    Tree* root = newTreeNode();
    root->data = (Category*)malloc(sizeof(Category));
    root->data->cate_id = 0;
    return root;
}
//使用递归查找,链表节点是按树节点生成的顺序提供的。
/*
功能:在root为根的树中,查找节点,条件:节点->data->cate_id==cid
入口参数:root指向树
入口参数:cid树中节点的类别ID
返回:树节点指针
*/
Tree* findByCID(Tree* root, int cid) {
    Tree* p = root, * pLeft, * pRight;
    if (root == NULL)return NULL;
    if (p->data->cate_id == cid) return p;
    pLeft = findByCID(root->left, cid);
    pRight = findByCID(root->right, cid);
    if (pLeft)return pLeft;
    else return pRight;
}
//查找违背树的逻辑性的节点
void findBadNodes(DList* list) {
    DNode* p1, * p2, * pHead;

    pHead = list->p_head->next;
    p1 = pHead->next;//第二个节点

    while (p1 != list->p_end) {
        p2 = pHead;
        int pid = p1->data->parent_cid;
        while (pid > 0 && p2 != p1) {
            if (p2->data->cate_id == pid) {
                break;
            }
            p2 = p2->next;
        }
        if (p2 == p1) {
            printf("****"); displayCategoryIdName(p1->data);
        }
        p1 = p1->next;
    }
}
/*
功能:根据链表数据构建树
*/
void createTree(Tree* root, DList* list) {
    DNode* pDNode;
    Tree* pTreeNode, * pTree = NULL;//工作指针pTree指向最近产生的节点
    //遍历链表节点
    pDNode = list->p_head->next;//pDNode指向头节点
    while (pDNode != list->p_end) {
#ifdef debug
        displayCategoryName(pDNode->data);
#endif
        //创建树节点--用链表中数据
        pTreeNode = newTreeNode(pDNode->data);
        //找pTreeNode双亲节点
        int parent_cid = pDNode->data->parent_cid;

        if (pTree && pTree->data->parent_cid == parent_cid) {//遇到兄弟
            pTree->right = pTreeNode;
            pTreeNode->parent = pTree;
        }
        else {//长子节点
            pTree = findByCID(root, parent_cid);//没遇到兄弟,找双亲
            if (pTree->left == NULL) {//无长子
                pTree->left = pTreeNode;
                pTreeNode->parent = pTree;
            }
            else {//有长子,找左子树的右链尾,插入新节点pTreeNode
                pTree = pTree->left;//从长子开始,长子是兄弟链的头节点
                while (pTree->right) {
                    pTree = pTree->right;
                }
                pTree->right = pTreeNode;//退出循环的时候,pTree指向尾节点
                pTreeNode->parent = pTree;
            }
        }
        pTree = pTreeNode;//下次可能会用到(遇到兄弟)
        pDNode = pDNode->next;
    }
}
void displayTree(Tree* root, int indent, int indent0) {
    if (root == NULL)return;//1.递归出口

    if (root->data->cate_id > 0) {
        printf("%*s", indent, "");
        displayCategoryIdName(root->data);
    }
    displayTree(root->left, indent + indent0, indent0);
    displayTree(root->right, indent, indent0);
}
/*
显示根节点和根的左子树所有节点
*/
void displayRootAndLeft(Tree* root, int indent, int indent0) {
    if (root == NULL)return;

    if (root->data->cate_id > 0) {
        printf("%*s", indent, "");
        displayCategoryIdName(root->data);
    }
    displayTree(root->left, indent + indent0, indent0);
}
void insertTreeNode(Tree* root, Category* p) {
    //1.查找p节点的双亲节点
    Tree* pParent = findByCID(root, p->parent_cid);
    Tree* pNode;
    Tree* newNode = NULL;
    if (pParent) {
        newNode = newTreeNode(p);
    }
    else {
        return;
    }
    if (pParent && pParent->left == NULL) {//作为长子
        pParent->left = newNode;
        newNode->parent = pParent;
    }
    else {//作为兄弟,放在右链尾节点的后面
        pNode = pParent->left;//右链首
        while (pNode->right) {
            pNode = pNode->right;
        }
        //pNode就是右链尾节点
        pNode->right = newNode;
        newNode->parent = pNode;
    }
}
void insertTreeNode(Tree* root, char* data) {
    Category* p = newCategory();
    scanf(data, "%d\t%s\t%d\t%d\t%d\t%d\n",
        &p->cate_id, p->name, &p->parent_cid, &p->cate_level, &p->show_status, &p->sort);
    insertTreeNode(root, p);
}
/*
功能:在根为root树中,删除node节点
*/
void deleteTreeNode(Tree* root, Tree* node) {
    if (node == NULL) {
        printf("node节点是空节点,不能删除\n");
        return;
    }
    if (node == root) {
        printf("node节点是树根节点,不能删除\n");
        return;
    }
    if (node->left) {
        printf("node节点有子节点,不能删除\n");
        return;
    }
    if (node->parent->left == node) {//node->left==null
        printf("正在删除长子节点\n");
        if (node->right == NULL) {//node->right==null,node是叶子节点
            printf("正在删除长子节点是叶子节点\n");
            node->parent->left = NULL;
        }
        else {//非叶子节点(有兄弟)
            printf("正在删除长子节点是兄弟的节点\n");
            node->right->parent = node->parent;
            node->parent->left = node->right;
        }
        delete node;
        return;
    }
    if (node->parent->right == node) {
        printf("正在删除兄弟节点\n");
        if (node->right == NULL) {
            printf("正在删除最小兄弟节点\n");
            node->parent->right = NULL;
        }
        else {
            printf("正在删除中间兄弟节点\n");
            node->parent->right = node->right;
            node->right->parent = node->parent;
        }
        delete node;
        return;
    }
}
//删除整棵子树?有无必要,如何删除(递归后续)
void deleteTree(Tree* root, Tree* node) {
    if (node == NULL) {
        //printf("node节点是空节点,不能删除\n");
        return;
    }
    deleteTree(root, node->left);
    deleteTree(root, node->right);
    delete node;
}
void deleteTreeAll(Tree* root, Tree* node) {
    if (node == NULL) {
        //printf("node节点是空节点,不能删除\n");
        return;
    }
    Tree* left = node->left;
    deleteTreeNode(root, node);
    deleteTree(root, node->left);
}
int main() {
    DList* pList;
    char C[17] = "pms_category.txt";
    pList = readFile(C);
    printf("=============displayList(pList);================\n");
    displayList(pList);
    printf("=============findBadNodes(pList);================\n");
    findBadNodes(pList);
    Tree* root = initTree();
    printf("=============createTree(root, pList);================\n");
    createTree(root, pList);
    Tree* subRoot = findByCID(root, 37);
    displayRootAndLeft(subRoot, 0, 4);
    char L [23] = "1424 手提音箱    37    3    1    0";
    char M[30] = "1425    带屏手提音箱1    1424    3    1    0";
    char N[30] = "1426    带屏手提音箱2    1424    3    1    0";
    char O [30] = "1427    带屏手提音箱3    1424    3    1    0";
    char P[30] = "1428    带屏手提音箱3    1425    3    1    0";
    displayRootAndLeft(subRoot, 0, 4);
    insertTreeNode(root, M);
    insertTreeNode(root,N);
    insertTreeNode(root,O );
    insertTreeNode(root,P );
    displayRootAndLeft(subRoot, 0, 4);
    printf("=============删除测试开始================\n");
    deleteTreeNode(root, NULL);
    deleteTreeNode(root, root);
    deleteTreeNode(root, findByCID(root, 1424));
    deleteTreeNode(root, findByCID(root, 1427));
    deleteTreeNode(root, findByCID(root, 1426));
    deleteTreeNode(root, findByCID(root, 1425));
    deleteTreeAll(root, findByCID(root, 1424));
    displayRootAndLeft(subRoot, 0, 4);
    findBadNodes(pList);
    //某个函数名做另一个函数的参数,作用是选择执行哪个函数
    printf("=====displayList(pList,displayCategoryName);====\n");
    displayList(pList, displayCategoryName);
    printf("====displayList(pList,displayCategory);====\n");
    displayList(pList, displayCategory);
    printf("====Tree * root = initTree(); createTree(root, pList);====\n");
    Tree * root = initTree(); createTree(root, pList);
    displayCategory(root->left->data);
    displayCategory(root->left->right->data);
    displayCategory(root->left->left->data);
    displayCategory(root->left->left->right->data);
    printf("====displayTree(root, -4, 4);====\n");
    displayTree(root, -4, 4);
    printf("====displayTree(root->left, 0, 4);====\n");
    displayTree(root->left, 0, 4);
    Tree* p;
    printf("====p = findByCID(root, 22);displayTree(p, 0, 4);====\n");
    p = findByCID(root, 22); 
    displayTree(p, 0, 4);
    printf("====p = findByCID(root,1); displayTree0(p, 0, 4);====\n");
    p =findByCID(root,1); 
    displayTree(p, 0, 4);

    getchar();
}

已启动生成…
1>已启动生成: 项目: Project18, 配置: Debug x64
1>源.cpp
1>D:\Project18\源.cpp(172,14): error C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
1>D:\Project18\源.cpp(185,3): error C4996: 'fscanf': This function or variable may be unsafe. Consider using fscanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
1>D:\Project18\源.cpp(359,2): error C4996: 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
1>D:\Project18\源.cpp(467,9): error C2374: “root”: 重定义;多次初始化
1>D:\Project18\源.cpp(435): message : 参见“root”的声明
1>已完成生成项目“Project18.vcxproj”的操作 - 失败。
生成: 成功 0 个,失败 1 个,最新 0 个,跳过 0 个
这些报错得怎么修改才能让它运行啊?

  • 写回答

1条回答 默认 最新

  • CSDN-Ada助手 CSDN-AI 官方账号 2022-12-17 20:20
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 1月2日
  • 已采纳回答 12月25日
  • 创建了问题 12月17日

悬赏问题

  • ¥15 爬取豆瓣电影相关处理
  • ¥15 手机淘宝抓清除消息接口
  • ¥15 C#无selenium
  • ¥15 LD衰减计算的结果过大
  • ¥15 用机器学习方法帮助保险公司预测哪些是欺诈行为
  • ¥15 计算300m以内的LD衰减
  • ¥15 数据爬取,python
  • ¥15 怎么看 cst中一个面的功率分布图,请说明详细步骤。类似下图
  • ¥15 为什么我的pycharm无法用pyqt6的QtWebEngine
  • ¥15 FOR循环语句显示查询超过300S错误怎么办