//后序遍历
void postOrder（BSTree *BT）
{
if（BT!= NULL）
{
postOrder（BT->lchild）；
postOrder（BT->rchild）；
printf（"%d",BT->key）；
}
}
//层次法打印树
void dispTree（BSTree *BT）
{
BSTree *stack[maxSize],*p;
int level[maxSize] ,top,n,i,width=4;
if（BT!=NULL）
{
printf（"Display a tree by hollow means.\n"）；
top=1;
stack[top]=BT;//push root point to stack.
level[top][0]=width;
while（top>0）
{
p=stack[top];
n=level[top][0];
for（i=1;i<=n;i++）
printf（" "）；
printf（"%d",p->key）；
for（i=n+1;i<maxWidth;i+=2）
printf（"--"）；
printf（"\n"）；
top--;
if（p->rchild!=NULL）
{
top++;
stack[top]=p->rchild;
level[top][0]=n+width;
level[top] =2;
}
if（p->lchild!=NULL）
{
top++;
stack[top]=p->lchild;
level[top][0]=n+width;
level[top] =1;
}
}
}
}
/* 向二叉排序树中加入一个结点
要改变指针，需要传递指针的指针*/
int InsertNode（BSTree **tree, KeyType key）
{
BSTNode *p= NULL, *parent = NULL;
BSTNode *pNewNode = （BSTNode *）malloc（sizeof（BSTNode））；
if （pNewNode==NULL）
{
return -1;
}
/* 新建结点赋值，特别是左右子结点指针要赋值为NULL */
pNewNode->key = key;
pNewNode->lchild = NULL;
pNewNode->rchild = NULL;
/* 二叉排序树是空树 */
if （*tree==NULL）
{
*tree = pNewNode;
return 0;
}
else
{
p = *tree;
/* 寻找插入位置 */
while （NULL != p）
{
/* key值已在二叉排序树中 */
if （p->key == key）
{
return 0;
}
else
{
parent = p;
p = （p->key < key） p->rchild : p->lchild;
}
}
if （parent->key < key）
{
parent->rchild = pNewNode;
}
else
{
parent->lchild = pNewNode;
}
return 0;
}
}
//删除节点
/* 通过值查找并删除一个结点 */
int delNode（BSTree **tree, KeyType key）
{
BSTNode *p = NULL, *q = NULL, *parent = NULL, *child = NULL;
p = *tree;
/* parent为NULL表示根结点的父亲为NULL */
while （NULL != p）
{
if （p->key == key）
{
break;
}
else
{ parent = p;
p = （p->key < key） p->rchild : p->lchild;
}
}
/* p为NULL时， 表示没有找到结点值为key的结点 */
if （NULL == p）
{
return 0;
}
/* p, q现在都是保存了待删结点指针 */
q = p;
/* 待删结点有两个儿子结点，进行一下转化 */
if （NULL != p->lchild && NULL != p->rchild）
{
//找中序后继，先右拐，然后左走到底
parent = p;
p = p->rchild;
while （NULL != p->lchild）
{
parent = p;
p = p->lchild;
}
/* p中保存了待删结点右子树中最左下的结点指针， parent中就保存了该结点父亲指针 */
child = p->rchild;
}
/* parent保存待删结点的父亲结点指针， child保存了待删结点的儿子结点