数据结构__二叉搜索树
(1)二叉搜索树定义 /**树节点定义**/ typedef struct BitNode { int data; struct BitNode *lChild,*rChild; }BiTNode,*BiTree; /***二叉树的搜索**/ //递归查找二叉树T中的Key是否存在,用指针f指向T的双亲,若查找成功则指针p指向该数据元素节点 //若失败,则指针指向路径上访问的最后一个节点,并返回false,也就是插入数据的位置 bool searchBST(BiTree T,int Key,BiTree f,BiTree *p) { if(!T) { *p = f; return false; } else if(Key== T->data) { *p = T; return true; } else { return searchBST(Key } } /* 插入节点 */ bool insertBST(BiTree *T,int Key) { BiTree p,s; if(!searchBST(*T,NULL,&p))//找插入位置p { s = (BiTree) new BiTNode; s->data = Key; s->lChild = s->rChild = NULL; if(!p)//如果插入的事第一个节点 *T = s; else if(Key< p->data) p->lChild =s; else p->rChild =s; return true; } else return false; } //查找删除节点的位置 bool deleteBST(BiTree *T,int Key) { if(!*T) return false; else { if(Key==(*T)->data) return Delete(T); else if(Key<(*T)->data) return DeleteBST(&(*T)->lChild,Key); else return DeleteBST(&(*T)->rChild,Key); } } //具体删除节点操作 //分两种情况考虑,一种情况,就是删除的节点 只有左子树或者右子树,或者啥都没有 这种操作是一样的 //另外一种情况是左右子树都有,当我们找到删除节点的时候,要从其右子树找到一个值最小的节点和当前节点的值交换,然后再删除这个节点 因为这样可以满足删除该节点的二叉树依然是二叉排序树 bool Delete(BiTree * p) { BiTree q,s; if((*p)->rChild==NULL) { q = *p; p = (*p)->lChild; delete q; } else if((*p)->lChild==NULL) { q = *p; p = (*p)->lChild ; delete q; } else { q=*p; s = p->rChild; while(s->lChild) { q= s; s = s->lChild; } (*p)->data = s->data;//值的替换 if(q!=*p) q->rChild = s->lChild; else q->lChild =s->lChild; delete s; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |