当前位置: 代码迷 >> C语言 >> [求助]二叉树的建立与删除的问题
  详细解决方案

[求助]二叉树的建立与删除的问题

热度:329   发布时间:2006-05-12 13:23:00.0
[求助]二叉树的建立与删除的问题

看了一天实在是晕了,这个到底哪里出错了啊,谁能帮我看看吗,好像是删除的部分不对劲



#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <time.h>

#define test 41

#define num 5

struct node {

int data;

struct node *right;

struct node *left;

};

struct node *insert(struct node *root, int n);

struct node *creat(struct node *root, int n);

int del(struct node **root, int n);

void Print(struct node *root);

static struct node *root = NULL;

int main(int argc, char* argv[])

{

int iBack = 0;

root = creat(root, num);

Print(root);

printf("开始删除\n");

iBack = del(&root, test);

if(iBack == 1)

{

printf("树为空\n");

return 0;

}

if(iBack == -1)

{

printf("未找到要删除节点\n");

return 0;

}

Print(root);

return 0;

}

//加入新节点

struct node *insert(struct node *root, int n)

{

struct node *new_p = NULL;

struct node *now_p = NULL;

struct node *old_p = NULL;

int i = 0;

if(root == NULL)

{

new_p = (struct node *)malloc(sizeof(struct node));

new_p -> data = n;

new_p -> right = NULL;

new_p -> left = NULL;

root = new_p;

}

else

{

now_p = root;

new_p = (struct node *)malloc(sizeof(struct node));

new_p -> data = n;

new_p -> right = NULL;

new_p -> left = NULL;

while(now_p != NULL)

{

old_p = now_p;

if(n == now_p -> data)

return (root);

if(n < now_p -> data)

now_p = now_p -> left;

else

now_p = now_p -> right;

}

if(n < old_p -> data)

old_p -> left = new_p;

else

old_p -> right = new_p;

}

return (root);

}

//创建一棵树

struct node *creat(struct node *root, int n)

{

int i = 0, j = 0;

// srand((unsigned)time(NULL));

for(i = 0; i < n; i++)

{

j = rand();

root = insert(root, j);

printf("%d\n", j);

}

return root;

}

//删除节点

int del(struct node **root, int n)

{

struct node *new_p = NULL;

struct node *now_p = NULL;

struct node *old_p = NULL;

if (*root == NULL)

return 1;

now_p = *root;

//要删除节点为root时

if(n == now_p -> data)

{

if((NULL == now_p -> left) && (NULL == now_p -> right))

{

free(now_p);

return 0;

}

if(NULL == now_p -> left)

{

now_p = now_p -> right;

free(now_p);

return 0;

}

if(NULL == now_p -> right)

{

now_p = now_p -> left;

free(now_p);

return 0;

}

else

{

new_p = now_p -> right;

now_p = now_p -> left;

while(now_p -> right != NULL)

{

now_p = now_p -> right;

}

now_p -> right = new_p;

return 0;

}

}

//要删除节点不为root时,寻找要删除节点

while(n != now_p -> data)

{

old_p = now_p;

if(n < now_p -> data)

now_p = now_p -> left;

else

now_p = now_p -> right;

if(NULL == now_p)

return (-1);

}

//找到要删除节点,开始删除

if((NULL == now_p -> left) && (NULL == now_p -> right))

{

if(n < old_p -> data)

old_p -> left = NULL;

else

old_p -> right = NULL;

free(now_p);

return 0;

}

if(NULL == now_p -> left)

{

if(n < old_p -> data)

old_p -> left = now_p -> right;

else

old_p -> right = now_p -> right;

free(now_p);

return 0;

}

if(NULL == now_p -> right)

{

if(n < old_p -> data)

old_p -> left = now_p -> left;

else

old_p -> right = now_p -> left;

free(now_p);

return 0;

}

if(n < old_p -> data)

{

old_p -> left = now_p -> left;

}

else

{

old_p -> right = now_p -> left;

}

new_p = now_p -> right;

now_p = now_p -> left;

while(now_p -> right != NULL)

{

now_p = now_p -> right;

}

now_p -> right = new_p;

return 0;

}

void Print(struct node *root)

{

if(root == NULL)

return;

Print(root -> left);

printf("%d\n", root -> data);

Print(root -> right);

}

搜索更多相关的解决方案: 二叉树  删除  

----------------解决方案--------------------------------------------------------

这么长呢,再发一遍

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define test 41
#define num 5

struct node {
int data;
struct node *right;
struct node *left;
};

struct node *insert(struct node *root, int n);
struct node *creat(struct node *root, int n);
int del(struct node **root, int n);
void Print(struct node *root);

static struct node *root = NULL;

int main(int argc, char* argv[])
{
int iBack = 0;
root = creat(root, num);
Print(root);

printf("开始删除\n");
iBack = del(&root, test);
if(iBack == 1)
{
printf("树为空\n");
return 0;
}

if(iBack == -1)
{
printf("未找到要删除节点\n");
return 0;
}
Print(root);
return 0;
}
//加入新节点
struct node *insert(struct node *root, int n)
{
struct node *new_p = NULL;
struct node *now_p = NULL;
struct node *old_p = NULL;
int i = 0;
if(root == NULL)
{
new_p = (struct node *)malloc(sizeof(struct node));
new_p -> data = n;
new_p -> right = NULL;
new_p -> left = NULL;
root = new_p;
}
else
{
now_p = root;
new_p = (struct node *)malloc(sizeof(struct node));
new_p -> data = n;
new_p -> right = NULL;
new_p -> left = NULL;

while(now_p != NULL)
{
old_p = now_p;
if(n == now_p -> data)
return (root);
if(n < now_p -> data)
now_p = now_p -> left;
else
now_p = now_p -> right;
}
if(n < old_p -> data)
old_p -> left = new_p;
else
old_p -> right = new_p;
}
return (root);
}
//创建一棵树
struct node *creat(struct node *root, int n)
{
int i = 0, j = 0;
// srand((unsigned)time(NULL));
for(i = 0; i < n; i++)
{
j = rand();
root = insert(root, j);
printf("%d\n", j);
}
return root;
}
//删除节点
int del(struct node **root, int n)
{
struct node *new_p = NULL;
struct node *now_p = NULL;
struct node *old_p = NULL;

if (*root == NULL)
return 1;

now_p = *root;
//要删除节点为root时
if(n == now_p -> data)
{
if((NULL == now_p -> left) && (NULL == now_p -> right))
{
free(now_p);
return 0;
}
if(NULL == now_p -> left)
{
now_p = now_p -> right;
free(now_p);
return 0;
}
if(NULL == now_p -> right)
{
now_p = now_p -> left;
free(now_p);
return 0;
}
else
{
new_p = now_p -> right;
now_p = now_p -> left;
while(now_p -> right != NULL)
{
now_p = now_p -> right;
}
now_p -> right = new_p;
return 0;
}
}
//要删除节点不为root时,寻找要删除节点
while(n != now_p -> data)
{
old_p = now_p;
if(n < now_p -> data)
now_p = now_p -> left;
else
now_p = now_p -> right;
if(NULL == now_p)
return (-1);
}
//找到要删除节点,开始删除
if((NULL == now_p -> left) && (NULL == now_p -> right))
{
if(n < old_p -> data)
old_p -> left = NULL;
else
old_p -> right = NULL;
free(now_p);
return 0;
}
if(NULL == now_p -> left)
{
if(n < old_p -> data)
old_p -> left = now_p -> right;
else
old_p -> right = now_p -> right;
free(now_p);
return 0;
}
if(NULL == now_p -> right)
{
if(n < old_p -> data)
old_p -> left = now_p -> left;
else
old_p -> right = now_p -> left;
free(now_p);
return 0;
}

if(n < old_p -> data)
{
old_p -> left = now_p -> left;
}
else
{
old_p -> right = now_p -> left;
}
new_p = now_p -> right;
now_p = now_p -> left;
while(now_p -> right != NULL)
{
now_p = now_p -> right;
}
now_p -> right = new_p;
return 0;
}

void Print(struct node *root)
{
if(root == NULL)
return;
Print(root -> left);
printf("%d\n", root -> data);
Print(root -> right);
}


----------------解决方案--------------------------------------------------------
  相关解决方案