返回信息流大话数据结构中的二叉排序树插入有些疑问：
Status InsertBST(BiTree *T,int key)
{
//当二叉排序树T中不存在关键字等于key的数据元素时，插入e并返回TRUE，否则返回FALSE
BiTreep p;
BiTreep s;
if(!SearchBST(*T,key,NULL,&p))
{
s = (BiTreep)malloc(sizeof(BiTreenode));
s->data=key;
s->left=s->right=NULL;
if(!p)
rt=s; //被插的树还是空树，被插节点*s做为根节点
else if(key<p->data))
p->left=s; //被插节点*s为左孩子
else
p->right=s; //被插节点*s为右孩子
return TRUE;
}
else
return FALSE; //树中已有关键字相同的节点，不再插入
}
我现在的理解是如果二叉排序树中不存在要插入的key，那样双指针p就指向了最后一个结点，那么插入的时候，就插在了最后一个结点的左或者右树上，这样的话如果插入的值小于根节点，但是却插入到了右子树，这样不符合排序树的规则，请各位帮忙解释下，谢谢！
这是一条镜像帖。来源：北邮人论坛 / cpp / #77884同步于 2014/3/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
二叉排序树的插入
guoisvictor
2014/3/28镜像同步4 回复
订阅后，新回复会通过你的通知中心匿名送达。
4 条回复
1. 如果不存在key, p指向的是一个叶节点, 不一定是最右的叶节点, 没有违反BST
2. 这段代码的问题在于如果非要用!p做判断是否为空树, p应该被声明成指针
p已经声明为指针了，因为BItree就是指针
【 在 Areosome 的大作中提到: 】
: 1. 如果不存在key, p指向的是一个叶节点, 不一定是最右的叶节点, 没有违反BST
: 2. 这段代码的问题在于如果非要用!p做判断是否为空树, p应该被声明成指针
这代码写得真是够丑的......
如果这是书上的原文，强烈建议你还是换本书看吧，这种代码看多了害人...
【 在 guoisvictor 的大作中提到: 】
: p已经声明为指针了，因为BItree就是指针
就是大话数据结构这本书
【 在 Areosome 的大作中提到: 】
: 这代码写得真是够丑的......
: 如果这是书上的原文，强烈建议你还是换本书看吧，这种代码看多了害人...