第六章-二叉树的应用.ppt

《第六章-二叉树的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1二叉搜索树6.1.1二叉搜索树的定义二叉搜索树(binanysearchingtree)又称二叉排序树(binarysortingtree)，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树。(1)若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字；(3)左、右子树本身又各是一棵二叉搜索树二叉搜索树的定义1广东建设职业技术学院计算机系6.1二叉搜索树6.1.1二叉搜索树的定义12,15,18

2、,23,26,30,52,63,74二叉搜索树的定义3052152374121826632广东建设职业技术学院计算机系6.1二叉搜索树6.1.2二叉搜索树的运算概述(1)从二叉搜索树中查找等于给定值x的元素，若查找成功则返回结点值域的地址，否则返回空指针。ElemType*Find(structBTreeNode*BST,ElemTypex);(2)从二叉搜索树中查找等于给定值x的元素，若查找成功则用x的值更新（即修改）该结点值并返回1表示更新成功，否则不做修改并返回0表示更新失败。intUpdate(structBTreeNode

3、*BST,ElemTypex);(3)向二叉搜索树插入一个元素x，使得插入后仍是一棵二叉搜索树。voidInsert(structBTreeNode**BST,ElemTypex);(4)从二叉搜索树中删除等于给定值x的结点，若删除成功则返回1，否则返回0。intDelete(structBTreeNode**BST,ElemTypex);二叉搜索树的运算概述3广东建设职业技术学院计算机系6.1二叉搜索树6.1.3二叉搜索树的运算ElemType*Find(structBTreeNode*BST,ElemTypex){if(BST=

4、=NULL)returnNULL;else{if(x==BST->data)return&(BST->data);elseif(xdata)returnFind(BST->left,x);elsereturnFind(BST->right,x);}}二叉搜索树的查找4广东建设职业技术学院计算机系6.1二叉搜索树6.1.3二叉搜索树的运算ElemType*Find1(structBTreeNode*BST,ElemTypex){while(BST!=NULL){if(x==BST->data)return&(BST->da

5、ta);elseif(xdata)BST=BST->left;elseBST=BST->right;}returnNULL;}二叉搜索树的查找5广东建设职业技术学院计算机系6.1二叉搜索树6.1.3二叉搜索树的运算voidInsert(structBTreeNode**BST,ElemTypex){if(*BST==NULL){structBTreeNode*p;p=malloc(sizeof(structBTreeNode));p->data=x;p->left=p->right=NULL;*BST=p;}elseif

6、(x<(*BST)->data)Insert(&((*BST)->left),x);elseInsert(&((*BST)->right),x);}二叉搜索树的插入6广东建设职业技术学院计算机系6.1二叉搜索树6.1.3二叉搜索树的运算voidInsert1(structBTreeNode**BST,ElemTypex){structBTreeNode*p,*t=*BST,*parent=NULL;while(t!=NULL){parent=t;if(xdata)t=t->left;elset=t->right;}p=mal

7、loc(sizeof(structBTreeNode));p->data=x;p->left=p->right=NULL;if(parent==NULL)*BST=p;elseif(xdata)parent->left=p;elseparent->right=p;}二叉搜索树的插入7广东建设职业技术学院计算机系6.1二叉搜索树6.1.3二叉搜索树的运算voidCreateBSTree(structBTreeNode**BST,ElemTypea[],intn){inti;*BST=NULL;for(i=0;i

8、i++)Insert1(BST,a[i]);}二叉搜索树的建立8广东建设职业技术学院计算机系6.1二叉搜索树6.1.3二叉搜索树的运算例{10，18，3，8，12，2，7，3}二叉搜索树的建立101018101831018381018