include <stdio.h>

include<stdlib.h>

include<stdbool.h>

 typedef char TElemType;
typedef struct BiTree {
	TElemType Data;
	struct BiTree* LChild, * RChild;
}BiTNode, * BiTree;

bool Search(BiTree T, TElemType key, BiTree f, BiTree& p)
{
	if (!T) { p = f; return false; }
	else {
		if (T->Data == key) { p = T; return true; }
		else if (T->Data < key)Search(T->RChild, key, T, p);
		else Search(T->LChild, key, T, p);
	}

}

bool Insert(BiTree& T, TElemType Item)
{
	BiTree p;
	if (!Search(T, Item, NULL, p)) {
		BiTree NewPTree = (BiTree)malloc(sizeof(BiTNode));
		NewPTree->Data = Item;
		NewPTree->LChild = NewPTree->RChild = NULL;
		if (!p) {
			T = NewPTree;
		}
		else {
			if (Item < p->Data)p->LChild = NewPTree;
			else p->RChild = NewPTree;
		}
	}
	else return false;
}

bool Delete(BiTree& T, TElemType Item)
{
	BiTree p;
	Search(T, Item, NULL, p);
	if (!p->LChild) {
		BiTree q = p;
		p = p->RChild;
		free(q);
	}
	else if (!p->RChild) {
		BiTree q = p;
		p = p->RChild;
		free(q);
	}
	else {
		BiTree s = p->LChild, q = p;
		while (s->RChild) {
			q = s;
			s = s->RChild;
		}
		p->Data = s->Data;
		if (q != p)q->RChild = s->LChild;
		else q->LChild = s->LChild;
	}
}