小鱼儿&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);
}
