//删除整棵子树有点问题
/*
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 个
这些报错得怎么修改才能让它运行啊？
