《特殊二叉树》PPT课件

《《特殊二叉树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章特殊二叉树6.1二叉搜索树6.6.1二叉搜索树的定义二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有如下特征的非空二叉树:若它的左子树非空,则左子树上所有结点的关键字均小于根结点的关键字;若它的右子树非空,则右子树上所有结点的关键字均大于(若允许具有相同关键字的结点存在,则大于等于)根结点的关键字;左、右子树本身又各是一棵二叉搜索树。526330121523741826526330121523741826一棵二叉排序数对该树中序遍历得到一有序序列：12，15，18，23，26，30，52，63，7

2、4非递减序列6.1.3二叉搜索树的运算查找从二叉搜索树中查找其值等于给定值item的结点，其过程为：(1)若二叉搜索树为空，则表明查找失败，应返回假(2)若item等于当前树根结点的值，则表明查找成功，应由引用参数item带回根结点的完整值并返回真(3)若item小于当前树根结点的值，则继续在它的左子树上查找，若item大于当前树根结点的值，则继续它的右子树上查找。boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;else{if(it

3、em==BST->data){item=BST->data;returntrue;}elseif(itemdata)returnFind(BST->left,item);elsereturnFind(BST->right,item);}}进行二叉排序树查找的非递归算法boolFind1(BTreeNode*BST,ElemType&item){while(BST!=NULL){if(item==BST->data){item=BST->data;returntrue;}elseif(item

4、T->data)BST=BST->left;elseBST=BST->right;}returnfalse;}2.二叉排序树的更新二叉排序树的更新算法与查找算法基本相同，区别在于：在更新算法中查找到待更新元素时，应将item的值赋给该元素，而查找算法中则是将该元素的值赋给item带回更新算法中item可为变参，也可为值参，在参数说明前可以加或不加const,而在查找算法中item只可为变参，且不能加常量标识符const3.二叉排序树的插入向二叉搜索树中插入其值为item的结点的过程为:(1)若当前二叉树为空，

5、则由item元素生成的新结点将作为树根结点插入；(2)否则，若item小于当前树根结点的值，则将新结点插入到它的左子树上，若item大于当前树根结点的值，则将新结点插入到它的右子树上。递归算法描述为：voidInsert(BTreeNode*&BST,constElemtype&item){if(BST==NULL){BTreeNode*p=newBTreeNode;p->data=item;p->left=p->right=NULL；BST=p;}elseif(itemdata)Insert(B

6、ST->left,item);elseInsert(BST->right,item);}非递归算法描述为：voidInsert1(BTreeNode*&BST,constElemtype&item){BTNode*t=BST,*parent=NULL;while(t!=NULL){parent=t;if(itemdata)t=t->left;elset=t->right;}BTreeNode*p=newBTreeNode;p->data=item;p->left=p->right=NULL;if(pa

7、rent==NULL)BST=p;elseif(itemdata)parent->left=p;elseparent->right=p;}利用二叉排序树插入算法生成二叉排序树voidCreateBSTree(BTreeNode*&BST,Elemtypea[],intn){BST=NULL;for(inti=0;i

8、38266294(d)38266294(e)3538266294(f)355038266294(f)35502838266294(g)35502855插入35插入50插入28插入554.二叉排序树的删除删除叶子结点将其双亲结点链接到它的指针去掉(即置为空)。LDMS(a)GAFWPLDMS(b)GAWP删除F删除单支结点将后继指针链接到它所在的链接位置。删除MLDMS(b)GAWPLDS(c)GAW