#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define maxlen 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/* 二叉树的二叉链表结点结构定义 */
typedef struct Node /* 结点结构 */
{
int data; /* 结点数据 */
struct BiTNode* lchild, * rchild; /* 左右孩子指针 */
} Node, * Tree;
int search_tree(Tree T, int key, Tree father, Tree* get)
{
if (!T)
{
*get = father;
return 0;
}
else if(T->data == key)
{
*get = T;
return 1;
}
else if(T->data >key)
{
search_tree(T->lchild, key, T, get);
}
else
{
search_tree(T->rchild, key, T, get);
}
}
int insert(Tree* T, int value)
{
Tree p, s;
if (!search_tree(*T, value, NULL, &p))
{
s = (Tree)malloc(sizeof(Node));
s->lchild = NULL;
s->rchild = NULL;
s->data = value;
if (!p)
{
*T = s;
}
else if(value>p->data)
{
p->rchild = s;
}
else
{
p->lchild = s;
}
return 1;
}
else
{
return 0;
}
}
int delete_node(Tree *T, int key)
{
if (!*T)
{
return 0;
}
else
{
if ((*T)->data == key)
{
delet(T);
}
else if((*T)->data > key)
{
delete_node(&(*T)->lchild, key);
}
else
{
delete_node(&(*T)->rchild, key);
}
return 1;
}
}
int insert1(Tree* T, int value)
{
Tree p, s;
if (*T == NULL) //根节点
{
*T= (Tree)malloc(sizeof(Node));
(*T)->data = value;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
}
else if(value < (*T)->data)
{
if ((*T)->lchild == NULL) //如果没有左孩子，直接将值赋给左孩子
{
p = (Tree)malloc(sizeof(Node)); //这已经给他的左右孩子分配了内存地址，所以要将他的左右孩子只想NULL
p->lchild = NULL;
p->rchild = NULL;
p->data = value;
(*T)->lchild = p;
return 1;
}
else
{
insert1(&((*T)->lchild), value);
}
}
else if(value > (*T)->data)
{
if ((*T)->rchild == NULL) //如果没有左孩子，直接将值赋给左孩子
{
s = (Tree)malloc(sizeof(Node));
//这已经给他的左右孩子分配了内存地址，所以要将他的左右孩子只想NULL
s->lchild = NULL;
s->rchild = NULL;
s->data = value;
(*T)->rchild = s;
return 1;
}
else
{
insert1(&((*T)->rchild), value);
}
}
else
{
return 0;
}
return 1;
}
int delet(Tree* T)
{
Tree q, s;
if ((*T)->lchild == NULL && (*T)->rchild == NULL)
{
*T = NULL;
free(*T);
}
else if((*T)->lchild == NULL)
{
q = *T;
*T = (*T)->rchild;
free(q);
}
else if ((*T)->rchild == NULL)
{
q = *T;
*T = (*T)->lchild;
free(q);
}
else
{
q = *T;
s = q->lchild;
while (s->rchild)
{
q = s; //指向最终s的父母节点
s = s->rchild;
}
(*T)->data = s->data;
if(q!=*T) //若T节点左子节点没有子右节点
q->rchild = s->lchild;
else
{
q->lchild = s->lchild;
}
free(s);
}
return 1;
}
int in_see(Tree T)
{
if (!T)
{
return 0;
}
in_see(T->lchild);
printf("%d ", T->data);
in_see(T->rchild);
return 1;
}
int main(void)
{
int i;
int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
Tree T = NULL;
for (i = 0;i < 10;i++)
{
insert(&T, a[i]);
}
in_see(T);
printf("\n");
delete_node(&T, 93);
in_see(T);
printf("\n");
delete_node(&T, 47);
in_see(T);
printf("\n");
return 0;
}
|
