m0_71659698 2022-12-17 18:02 采纳率: 100%

# 数据结构二叉树修改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 {//双向链表
int length;
};
/*

*/
DList* initDList() {
DList* p;
p = (DList*)malloc(sizeof(DList));//双向链表数据，不是双向链表中节点数据
//设置p成员
p->p_end = (DNode*)malloc(sizeof(DNode));
p->length = 0;
p->p_end->next = NULL;
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) {
while (p1 != pList->p_end) {
displayCategory(p1->data);
p1 = p1->next;
}
}
/*

int sub(int, int) {}
*/
//函数指针做另一个函数的参数，实参是函数名，作用是选择执行哪个函数
void displayList(DList* pList, void (*fn)(Category*)) {
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* 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);
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;
}
//使用递归查找，链表节点是按树节点生成的顺序提供的。
/*

*/
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;
}
//查找违背树的逻辑性的节点
DNode* p1, * p2, * pHead;

while (p1 != list->p_end) {
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指向最近产生的节点
//遍历链表节点
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);
}
/*

*/
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";
printf("=============displayList(pList);================\n");
displayList(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);
//某个函数名做另一个函数的参数，作用是选择执行哪个函数
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”的操作 - 失败。

• 写回答

• 系统已结题 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错误怎么办