32二叉排序树的定义、查找、插入和删除

1、 二叉排序树的定义

2、 二叉排序树的查找：二叉排序树的查找时从根结点开始，沿某一个分支逐层向下进行比较的过程。若相等，则查找成功；若不等，则当根节点的关键字大于给定关键字值时，在根结点的左子树中查找，否则在根结点的右子树中查找。二叉树非递归查找算法如下： BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){ //查找函数返回指向关键字值为key的结点指针，若不存在，返回NULL P=NULL; //p指向被查找结点的双亲，用于插入和删除操作 While(T!=NULL&&key!=T->data){ P=T; If(keydata) T=T->lchild; Else T=T->rchild; } Return T; } 3、 二叉排序树的插入

描述代码如下： Int BST_Insert(Bitree &T,KeyType k){ //在二叉排序树T中插入一个关键字为k的结点 If(TNULL){ //原树为空，新插入的记录为根节点 T=(BiTree)malloc(sizeof(BSTNode)); T->key=k; T->lchild=T->rchild=NULL; Return 1; //返回1，表示成功 } Else if(kT->key) //树中存在相同关键字的结点 Return 0; Else if(kkey) //插入到T的左子树中 Return BST_Insert(T->lchild,k); Else //插入到T的右子树中 Return BST_Insert(T->rchild,k); }

4、 二叉排序树的构造

Void Creat_BST(BiTree &T,KeyType str[],int n){ //用关键字数组str[]建立一个二叉排序树 T=NULL; //初始化时bt为空树 Int i=0; While(i