小鱼儿&ADT树
我勒个去啊,竟然前天的写的树。竟然有很多逻辑错误。现在写的这个ADT树已经修改好了。
但功能可能没有那么全。
但其实已经够了、掌握这几种其他都好写了。
感觉现在对数据结构和指针掌握的还可以、这里要感谢网上的高手hellovfp对我帮助。没有要我误入歧途。
现在通过自己的自学,自己感觉进步蛮快的、。。。。。。
代码
程序代码:
tree.h #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define SIZE sizeof(int)//这里本来是保存数据的大小 因为这样的结构方式可以针对任何数据 typedef int (*pFun)(void *date1,void *date2);//函数指针 typedef struct tagTreeNode { struct tagTreeNode* pLeft; struct tagTreeNode* pRight; struct tagTreeNode* parent; void *date; }Node,*pNode; typedef struct tagTree { int treeNum; pNode root; }Tree,*pTree; int isNull(void *p); int isLeft(pNode node,pNode parent); static pNode CreateNode(pNode parent,void *date); int CreateTree(pTree tree); int AddTreeNode(pTree tree,void *date,pFun Compare); int DeleTreeNode(pTree tree,void *deleIt,pFun Compare); int isToLeft(pNode node,void *date); int isToRight(pNode node,void *date); void inOreder(pNode node); void PreOrder(pNode node); void PostOrder(pNode node); int DeleDate(pNode node,pTree tree); tree.cpp #include "tree.h" int isNull(void *p) { if(!p) return 1; else return 0; } //1 代表左边 2 代表右边 int isLeft(pNode node,pNode parent) { if(isNull(node)||isNull(parent)) return 0; if(node==parent->pLeft) return 1; else return 2; } static pNode CreateNode(pNode parent,void *date) { pNode nowPtr; nowPtr=(pNode)malloc(sizeof(Node)); if(isNull(nowPtr)) return NULL; nowPtr->date=malloc(sizeof(int)); if(isNull(nowPtr->date)) return 0; memcpy(nowPtr->date,date,sizeof(int)); printf("--%d--",*(int *)date); nowPtr->parent=parent; nowPtr->pLeft=NULL; nowPtr->pRight=NULL; return nowPtr; } int isToLeft(pNode node,void *date) { if(isNull(node)||isNull(date)) return 0; if(*(int *)date<*(int *)node->date) return 1; else return 0; } int isToRight(pNode node,void *date) { if(isNull(node)||isNull(date)) return 0; if(*(int *)date>*(int *)node->date) return 1; else return 0; } int CreateTree(pTree tree) { if(isNull(tree)) return 0; tree->root=NULL; tree->treeNum=0; return 1; } int AddTreeNode(pTree tree,void *date,pFun Compare) { pNode nowPtr; pNode prePtr; pNode temp; int flag=0;//判断左右的方向 if(isNull(tree)||isNull(date)||isNull(Compare)) return 0; if(isNull(tree->root)) { if(isNull(nowPtr=CreateNode(NULL,date))) { puts("root is error"); exit(1); } else { tree->root=nowPtr; tree->treeNum++; } } else { nowPtr=tree->root; prePtr=NULL; while(!isNull(nowPtr)) { if(Compare(date,nowPtr->date)==1)//当date小于对应节点的数据时候 就转向左节点. { prePtr=nowPtr; nowPtr=nowPtr->pLeft; flag=1; } else if(Compare(date,nowPtr->date)==2)//大于 { prePtr=nowPtr; nowPtr=nowPtr->pRight; flag=2; } else return 0; ///这里屏蔽了重复的数字 } if(flag==1) { if(temp=CreateNode(prePtr,date)) { prePtr->pLeft=temp; tree->treeNum++; } else return 0; } else if(flag==2) { if(temp=CreateNode(prePtr,date)) { prePtr->pRight=temp; tree->treeNum++; } else return 0; } } return 1; } //三种遍历方式。递归真是个神奇的东西。这么短就可以实现。要是非递归要多少代码啊。 //给我一个非递归代码。呵呵 void inOreder(pNode node) { if(!isNull(node)) { inOreder(node->pLeft); printf("%3d",*(int *)node->date); inOreder(node->pRight); } } void PreOrder(pNode node) { if(!isNull(node)) { printf("%3d",*(int *)node->date); inOreder(node->pLeft); inOreder(node->pRight); } } void PostOrder(pNode node) { if(!isNull(node)) { inOreder(node->pLeft); inOreder(node->pRight); printf("%3d",*(int *)node->date); } } int DeleTreeNode(pTree tree,void *deleIt,pFun Compare) { int flag; pNode nowPtr=tree->root; pNode prePtr=NULL; if(isNull(tree->root)||isNull(deleIt)||isNull(Compare)||isNull(tree->root)) return 0; while(!isNull(nowPtr)) { if(Compare(deleIt,nowPtr->date)) { //进行删除处理 flag=DeleDate(nowPtr,tree); if(flag) { tree->treeNum--; return 1; } else return 0; } if(isToLeft(nowPtr,deleIt)) nowPtr=nowPtr->pLeft; else if(isToRight(nowPtr,deleIt)) nowPtr=nowPtr->pRight; } return 0; } //处理方式:上一个节点,其实释放的是下一个的某个子节点。 //代码那么长只是要保留那些要释放点的一些信息。 int DeleDate(pNode node,pTree tree) { pNode temp; if(isNull(node)) return 0; if(isNull((node)->pLeft)&&!isNull((node)->pRight))//当要删除的节点是只有一个做子右节点时候的处理方法。 { temp=node->pRight; /*node->date=(node)->pRight->date;*/ /*memcpy(node->date,temp->date,sizeof(int));*/ *(int*)node->date=*(int*)node->pRight->date; node->pLeft=temp->pLeft; node->pRight=temp->pRight; if(!isNull(temp->pLeft)) temp->pLeft->parent=node; if(!isNull(temp->pRight)) temp->pRight->parent=node; free(temp->date); free(temp); } else if(isNull(node->pRight)&&!isNull(node->pLeft))//当要删除的节点只有一个子左节点的时候 { temp=node->pLeft; /*node->date=temp->date;*/ memcpy(node->date,temp->date,sizeof(int)); /**(int*)node->date=*(int*)temp->date;*/ printf("%d",*(int*)node->date); node->pLeft=temp->pLeft; node->pRight=temp->pRight; if(!isNull(temp->pLeft)) temp->pLeft->parent=node; if(!isNull(temp->pRight)) temp->pRight->parent=node; free(temp->date); free(temp); } else if(isNull((node)->pLeft)&&isNull((node)->pRight))//没有一个子节点 { if(node->parent->pLeft==node) { node->parent->pLeft=NULL; free(node); } else { node->parent->pRight=NULL; free(node); } } else//有连个子节点。。。。这里是难点。。。。因为左边的一定是比右边的小。。。 //所以要把子右节点移到子做节点的右子页那里。。看不明白 自己琢磨,也可以看c plus----这本书。 { if(node->parent!=NULL) { if(node->parent->pLeft==node) { node->parent->pLeft=node->pLeft; temp=node->pLeft; while(temp->pRight) { temp=temp->pRight; } temp->pRight=node->pRight; free(node->date); free(node); } else { node->parent->pRight=node->pLeft; temp=node->pLeft; while(temp->pRight) { temp=temp->pRight; } temp->pRight=node->pRight; free(node->date); free(node); } } else { temp=node->pLeft; temp->parent=NULL; while(temp->pRight) { temp=temp->pRight; } temp->pRight=node->pRight; tree->root=node->pLeft; free(node->date); free(node); } } return 1; } main.cpp #include "tree.h" int _Compar(void *date1,void *date2) { int i,k; i=*(int*)date1; k=*(int *)date2; if(i==k) return 0; else if(i<k) return 1; else return 2; } int some(void *date1,void *date2) { if(*(int *)date1==*(int *)date2) return 1; else return 0; } void main() { Tree tree; int i; int da; int s[]={3,1,4,45,6,2,8,4,99}; CreateTree(&tree); for(i=0;i<9;i++) { da=s[i]; AddTreeNode(&tree,&da,_Compar); } printf("\n节点个数 %d\n",tree.treeNum); puts("中跟"); inOreder(tree.root); puts(""); puts("删除以后"); int date=6; DeleTreeNode(&tree,&date,some); inOreder(tree.root); printf("\n节点个数 %d\n",tree.treeNum); puts("后跟"); PostOrder(tree.root); puts(""); puts("前根"); PreOrder(tree.root); }