对于编程二叉排序树,实现构建,查找,插入,删除四个操作已编好,解释一...
发布网友
共3个回答
热心网友
typedef struct BiTnode 定义二叉树节点
{
int data; 节点的值
struct BiTnode *lchild,*rchild; 节点的左孩子，节点的右孩子
}BiTnode,*BiTree;
BiTree search_tree(BiTree T,int keyword,BiTree *father) 查找（根据节点的值查找） 返回节点指针
{
BiTree p; 临时指针变量p
*father = NULL; 先设其父亲节点指向空
p = T; p赋值为根节点（从根节点开始查找）
while (p && p->data!=keyword) 如果不是p不指向空且未找到相同值的节点
{
*father = p; 先将父亲指向自己（注意：这里传过来的father是二级指针）
if (keyword < p->data) 如果要找的值小于自己的值
p = p->lchild; 就向自己的左孩子开始找
else
p = p->rchild; 否则向自己的右孩子开始查找
}
return p; 如果找到了则返回节点指针
}
BiTree creat_tree(int count)
{
BiTree T,p; 设置两个临时变量T,p
int i = 1; i = 1;（count是你要创建树的节点的个数)
while (i <= count)
{
if (i == 1) 如果i=1，说明还是空树。
{
p = (BiTnode *)malloc(sizeof(BiTree)); 使p指向新分配的节点
if (!p) 分配未成功
return NULL; 返回NULL
T = p; 分配成功,T=p( 这里实际上T就是根节点)
scanf("%d",&p->data); 输入p指向节点的值
p->lchild = p->rchild = NULL; p的左孩子和右孩子都指向空。
i++;
}
else
{
int temp; 如果不是空树
scanf("%d",&temp); 输入节点的值
search_tree(T,temp,&p); 查找节点要插入的位置。（T是根节点，插入的节点的值， 父亲节点的地址）
if (temp < p->data) 如果插入的值小于父亲节点的值
{
p->lchild = (BiTnode *)malloc(sizeof(BiTnode)); 那么就为父亲节点的左孩子分配一个节点空间，并指向这个空间
if (!p->lchild)
return NULL; 分配不成功，退出
p = p->lchild; 分配成功，p指向自己的左孩子
}
else
{ 如果插入的值大于父亲节点的值
p->rchild = (BiTnode *)malloc(sizeof(BiTnode)); 分配空间
if (!p->rchild)
return NULL; 分配不成功，退出
p = p->rchild; p指向自己的右孩子。
}
p -> data = temp; 新分配的节点的值赋值为插入的值
p -> lchild = p->rchild = NULL; 使其左右节点均为NULL
i++;
}
}
return T; 返回根节点。
}
int insert_tree(BiTree *T,int elem) 插入（根节点，插入的值）返回-1和0,-1代表插入失败，0代表成功
{
BiTree s,p,father;
s = (BiTnode *)malloc(sizeof(BiTnode)); s指向新开辟一个节点
if (!s) 为开辟成功
return -1; 返回值-1
s->data = elem; 新节点的值赋值为插入的值
s->lchild = s->rchild = NULL; 其左右孩子为空
p = search_tree(*T,elem,&father); p赋值为要插入的节点
if (!p) 未开辟成功，返回-1
return -1;
if (father == NULL) 如果父亲节点指向空，说明是空树
*T = s; 让根节点指向s
else if (elem < father->data) 否则如果插入的值小于父亲的值
father->lchild = s; 父亲的左孩子赋值为s
else
father->rchild = s; 否则父亲的右孩子赋值为s.
return 0; 返回0
热心网友
int delete_tree(BiTree *T,int elem) 删除（根节点，删除节点的值） -1表示失败，0表示成功
{
BiTree s,p,q,father;
p = search_tree(*T,elem,&father); p赋值为要删除的节点
if(!p) p为空，返回-1(即没找到删除的节点)
return -1;
if(!p->lchild) 如果删除节点左孩子为空
{
if (father == NULL) 且父亲节点为空（即根节点是要删除的节点，且只有右孩子）
{
*T = p->rchild; 那么根节点就为原先根节点的右孩子
free(p); 释放掉原先根节点
return 0; 返回0
}
if (p == father->lchild) 如果删除的节点是左节点。（ 如果删除节点左孩子为空）
father->lchild = p->rchild; 那么删除节点的父亲的左孩子指向删除节点的右孩子。
else 如果删除节点是右孩子。（ 如果删除节点左孩子为空）
father->rchild = p->rchild; 那么删除节点的父亲的右孩子指向删除节点的右孩子。
free(p); 释放删除节点
return 0; 返回0
}
else
if(!p->rchild) 如果删除节点的右孩子为空
{
if (father == NULL) 情况同上。（这里与上面描述的是删除节点只有一个孩子的情况，左孩子或右孩子为空）
{
*T = p->lchild;
free(p);
return 0;
}
if (p == father->lchild)
father->lchild = p->lchild;
else
father->rchild = p->lchild;
free(p);
return 0;
}
else 如果删除节点的左右孩子都不为空的话。
{
q = p; q赋值为删除节点
s = p->lchild; s赋值指向删除节点的左孩子
while (s->rchild) 当s的右孩子不为空
{
q = s;
s = s->rchild;
} 循环到这里,q为s的父亲,s为删除节点左子树中最右边的孩子（即左子树中最大值的节点）
p->data = s->data; 删除节点的值为s的值
if (q != p) 当删除节点不是s的父亲时
q->rchild = s->lchild; 将s的父亲的右孩子指向s的左孩子
else 如果删除节点是s的父亲时
q->lchild = s->lchild; 将s父亲的左孩子指向s的左孩子
free(s); 释放s
return 0; 返回成功。
}
}
main()
{
}
说明：1，这位先生指针用的不错
2.实际上这里写的是二叉平衡树，即任何节点的左孩子的值都要比它小，任何节点的右孩子的值都要比它大。
3.关于上面的删除，插入，查找操作，你画画图有利于理解。
热心网友
不能这样学习语言啊，永远形不成自己的思想。哎
