#include?
#include?

typedef?struct?node
{
????int?key;
????struct?node?*lchild*rchild;
}BSTNode;

//二叉排序樹插入操作遞歸算法
BSTNode?*InsertBST1（BSTNode?*T?int?key）
{
????BSTNode?*p?*q?=?T;

????//p為待插入的新結點
????p?=?（BSTNode?*）malloc（sizeof（BSTNode））;
????p->key?=?key;
????p->lchild?=?p->rchild?=?NULL;

????if（T?==?NULL）?//原樹為空
????????T?=?p;?//新插入的結點為新的根

????//原樹非空時將新結點p作為q的左孩子或右孩子插入
????else
????{
????????if（key?==?q->key）
????????????return?T;

????????if（key?key）
????????{
????????????if（q->lchild?==NULL）
????????????????q->lchild?=?p;
????????????else
????????????????InsertBST1（q->lchild?key）;
????????}

????????if（key?>?q->key）
????????{
????????????if（q->rchild?==NULL）
????????????????q->rchild?=?p;
????????????else
????????????????InsertBST1（q->rchild?key）;
????????}
????}
????return?T;
}

////二叉排序樹插入操作非遞歸算法
BSTNode?*InsertBST2（BSTNode?*T?int?key）
{
????BSTNode?*f?*p?=?T;

????//查找插入位置
????while（p）
????{
????????if（key?==?p->key）
????????????return?T;//無須插入

????????f?=?p;//記錄訪問的結點
????????if（key?key）
????????????p?=?p->lchild;
????????else
????????????p?=?p->rchild;
????????//若keykey，則在左子樹中查找，否則在右子樹中查找
????}

????//p為待插入的新結點
????p?=?（BSTNode?*）malloc（sizeof（BSTNode））;
????p->key?=?key;
????p->lchild?=?p->rchild?=?NULL;

????if（T?==?NULL）?//原樹為空
????????T?=?p;?//新插入的結點為新的根

????//原樹非空時將新結點q作為p的左孩子或右孩子插入
????else
????{
????????if（key?key）
????????????f->lchild?=?p;
????????else?f->rchild?=?p;
????}

????return?T;
}

//二叉排序樹刪除操作
void?DelBST（BSTNode?*Tint?key）
{
????BSTNode?*p?=?T?*f?*q?*s;
????while（p）
????{
????????if（p->key?==?key）?break;?//找到關鍵字為key的結點
????????f=p;//記下關鍵字key節點的父節點
????????p=（key?key）??p->lchild?:?p->rchild;//分別在*p的左、右子樹中查找
????}
????if（!p）?return;//二叉排序樹中無關鍵字為key的結點
????if（p->lchild?==?NULL?&&?p->rchild?==?NULL）//p無左子樹無右子樹
????{
????????if（p?==?T）?T?=?NULL;//刪除的是根節點
????????else
????????????if（p?==?f->lchild）
????????????????f->lchild?=?NULL;
????????????else
????????????????f->rchild?=?NULL;
????}
????else?if（p->lchild?==?NULL?&&?p->rchild?!=?NULL）//p無左子樹有右子樹
????{
????????if（f->lchild?==?p）
????????????f->lchild?=?p->rchild;
????????else
????????????f->rchild?=?p->rchild;
????}
????else?if（p->rchild?==?NULL?&&?p->lchild?!=?NULL）//p有左子樹無右子樹
????{
??