[데이터 구조] - 이 진 트 리 찾기, 삽입, 삭제

1、 정의: 이 진 트 리 는 빈 나무 나 성질 을 가 진 이 진 트 리 입 니 다.          (1) 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 값 은 뿌리 노드 의 값 보다 작 습 니 다.          (2) 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 이 (또는) 뿌리 노드 의 값 보다 크다.          (3) 그의 좌우 서브 트 리 도 각각 이 진 트 리 이다.
2. 두 갈래 정렬 트 리 검색, 삽입, 삭제 실현 알고리즘

#include 
#include
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;//           

int Search(BiTree T, int k, BiTree f, BiTree *p)
{
	if (!T)
	{
		*p = f;
		return false;
	}
	if (k == T->data)
	{
		*p = T;
		return true;
	}
	else if (k < T->data)
	{
		return Search(T->lchild, k, T, p);
	}
	else
		return Search(T->rchild, k, T, p);

}

int Insert(BiTree &T, int i)
{
	
	if (!T)
	{
		T = (BiTree)malloc(sizeof(BiTNode));// T    
		T->data = i;//     
		T->lchild =T->rchild = NULL;
	}
		if (i == T->data)
			return 0;
		else if (i < T->data)
			Insert(T->lchild, i);
		else
			Insert(T->rchild, i);
		return true;
	
	
}
int  Delete(BiTree &p)
{
	BiTree q, s;
	if (p->rchild == NULL)
	{
		q = p;
		p = p->lchild;//       ，        ， free    
		free(q);
	}

	if (p->lchild == NULL)
	{
		q = p;
		p = p->rchild;       ，        ， free    
		free(q);
	}

	else//           
	{
		q = p;
		s = p->lchild;//          q，        s
		while (s->rchild)//                
		{
			q = s;
			s = s->rchild;
		}
		p->data = s->data;
		if (q != p)
		{
			q->lchild = p->rchild;//     
		}
		else
			q->lchild = s->lchild;//     
		free(s);
	}
	return true;
}

int DeleteT(BiTree &T,int d)
{
	if (!T)
		printf("     ");
	else
	{
		if (d == (T)->data)
		{
			return Delete(T);
		}
		else if (d < (T)->data)
			return DeleteT((T)->lchild, d);
		else
			return DeleteT((T)->rchild, d);
	}
}

void InOrder(BiTree T)
{
	if (T)
	{
		InOrder(T->lchild);
		printf("%d ", T->data);
		InOrder(T->rchild);
	}
}

int main()
{
	int a,j,i=10;
	BiTree T = NULL,f,p;
	printf("    :");
	while (i--)
	{
		scanf_s("%d", &a);
		Insert(T, a);
	}
	printf("      (    ):");
	InOrder(T);
	printf("
");

	while (1)
	{
		printf("         :");
		scanf_s("%d", &a);
		if (Search(T, a, NULL, &p))
			printf("   
");
		else
		{
			printf("   
");
			printf("            ( :1/ :0)");
			scanf_s("%d", &j);
			if (j == 0)
				return 0;
			else
				Insert(T, a);
			printf("       :");
			InOrder(T);
			printf("
");
		}
		printf("          ?( :1/ :0):");
		scanf_s("%d",&j);
		if (j == 1)
		{
			printf("         :");
			scanf_s("%d", &a);
			DeleteT(T, a);
			printf("       :");
			InOrder(T);
			printf("
");
		}
	}

}