二叉排序树的删除_二叉排序树的删除图示_二叉排序树删除节点

二叉排序树的查找属于动态查找的范畴，根据查找过程中是否对表进行修改，可以把查找分为静态查找和动态查找。动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定的key值，若表中存在其关键字等于key的记录，则查找成功并返回，否则插入关键字等于key的记录。

二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

（1）若它的左子树非空，则左子树上的所有结点的值均小于根节点的值；

（2）若它的右子树非空，则右子树上的所有结点的值均大于根节点的值；

（3）它的左右子树也分别为二叉排序树；

1、二叉排序树的数据结构

typedef struct node
{
	short key;
	struct node *rchild,*lchild;
} BSTNode,*BSTree;

2、二叉排序树的插入和生成

已知一个关键字值为key的节点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可，插入可以用一下方法。

（1）若二叉排序树为空树，则key称为二叉排序树的根;

（2）若二叉排序树非空，则将key与二叉排序树的根比较，如果key值等于根节点，则停止插入；如果key值小于根节点的值，则将key插入左子树；如果key值大于根节点的值，则将key插入右子树；

二叉树的插入算法如下：

void InsertBST(BSTree* bst,short key)
{
    BSTree s;
    if(*bst==NULL)    //递归结束条件;该结点为空时创建结点;
    {
        s=(BSTree)malloc(sizeof(BSTNode));
        s->key=key;
        s->lchild=NULL;
        s->rchild=NULL;
        *bst=s;
    }
&#160;&#160; &#160;else if(key<(*bst)->key)
&#160;&#160; &#160;{
&#160;&#160; &#160;&#160;&#160; &#160;InsertBST(&((*bst)->lchild),key);
&#160;&#160; &#160;}
&#160;&#160; &#160;else if(key>(*bst)->key)
&#160;&#160; &#160;{
&#160;&#160; &#160;&#160;&#160; &#160;InsertBST(&((*bst)->rchild),key);
&#160;&#160; &#160;}
}

/******************
* 根据二叉排序树的插入算法可以创建一颗二叉排序树;
****************************/
void CreateBST(BSTree* bst)
{
&#160;&#160; &#160;char key;
&#160;&#160; &#160;*bst=NULL;
&#160;&#160; &#160;scanf("%c",&key);
&#160;&#160; &#160;while (key!=&#39;?&#39;)&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; //输入字符的结束是&#39;？&#39;;
&#160;&#160; &#160;{
&#160;&#160; &#160;&#160;&#160; &#160;InsertBST(bst,key);
&#160;&#160; &#160;&#160;&#160; &#160;scanf("%c",&key);
&#160;&#160; &#160;}
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25167-1.html