我看 严蔚敏 的数据结构中,说到二叉搜索树插入的问题
其代码:
[code=c]
Status InsertBst(BiTree& T, ElemType e){
    if (!SearchBST( T,e.key,NULL,p){
         s = (BiTree) malloc (sizeof (BiTNode));
         s->data = e; s->lchild = s->rchild = NULL;
         if(!p) T = s;
         else if LT(e.key,p->data.key) p->lchild = s;
         else  p->rchild = s;
         return TRUE;
         }
     else return FALSE;
}
[/code]
为何这里需要储存parent的信息呢? 直接利用当前结点,也可以做插入.
如,
[code=c]
void insert(BiTreeNode*& root, int key)
{
     if(root == NULL)
     {
         BiTreeNode* newnode = new BiTreeNode;
         newnode->data = key;
         newnode->lchild = newnode->rchild = NULL;
         root = newnode;
     }
     else if(key > root->data)
         insert(root->rchild,key);
     else
         insert(root->lchild,key);
}
[/code]

感觉上不需这个parent也行吧?而且它找到插入位置后,还将key跟parent的data再作一次对比..
为何不直接把插入位置指向新结点呢?