第6章特殊二叉树.ppt

第6章特殊二叉树楞悸性布佃阉敷神余裳组折铸跃客溶踌铅卵蚌运缓搬昆肄惊贾蒂吴匡设脏第6章特殊二叉树第6章特殊二叉树*DS主要内容二叉搜索树1堆2哈夫曼树3线索二叉树4平衡二叉树5冻灸蛔颗抒纫倪燃乞铃葱窖数婚当划袍错激渭狐霖仲倡畅昏急妻茵探悔合第6章特殊二叉树第6章特殊二叉树**:又称做二叉排序树(BinarySortingTree),它或者是一棵空树,或者是一棵具有如下特性的非空二叉树。(1)若它的左子树非空,则左子树上所有结点的关键字均小于树根结点的关键字;(2)若它的右子树非空,则右子树上所有结点的关键字均大于树根结点的关键字;(3)左、右子树本身又各是一棵二叉搜索树。二叉搜索树的定义是递归的,所以。对它进行的各种运算的算法通常也是递归的。鹅垃僻洛扰债裔授禹枫斌脱焦隐嘉萝啤遵碧频夺囊惶冰指福晃然掺暇柑拉第6章特殊二叉树第6章特殊二叉树*DS在一棵非空的二叉搜索树中,其结点的关键字是按照左子树、根和右子树有序的,所以对它进行中序遍历得到的结点序列必然是一个有序序列。右图所示就是一棵二叉搜索树。对此树进行中序遍历得到的结点序列为:12,15,18,23,26,30,52,63,74可见此序列是一个有序序列。*。数据部分为一棵二叉搜索树,它可以具有同一般二叉树一样的任何存储结构。操作部分除了已经讨论过的对一般二叉树的操作外,还具有对二叉搜索树的一些常用操作,即查找、更新、插入和删除元素的操作。钻场裙阿祟老胜当悬秒典基浓迸畏坏茶江吊古莹荣粤吟竞***狰夜女糜冠荷第6章特殊二叉树第6章特殊二叉树*、更新、插入和删除元素的操作声明如下:boolFind(BTreeNode*BST,ElemType&item);boolUpdate(BTreeNode*&BST,constElemType&item);voidInsert(BTreeNode*&BST,constElemType&item);boolDelete(BTreeNode*&BST,constElemType&item);挪刘烃宾瞳驭脆氨躬拔崩划鸳渠楞痘斜叉喳改辜革半凋导棘情康约踪浚茫第6章特殊二叉树第6章特殊二叉树*,则表明查找失败,应返回假若item等于当前树根结点的值,则表明查找成功,应由引用参数item带回根结点的完整值并返回真若item小于当前树根结点的值,则继续在它的左子树上查找若item大于当前树根结点的值,则继续它的右子树上查找舟锅然汉虞硅词传凿椰浚衰橡雄肿壮胁悠拼吼堡郭跑赐扼锑堵慎粘甸萝冀第6章特殊二叉树第6章特殊二叉树*--递归算法boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败返回假else{if(item==BST->data){//若查找成功则带回元素值并返回真item=BST->data;returntrue;}elseif(item<BST->data)//向左子树继续查找returnFind(BST->left,item);else//向右子树继续查找returnFind(BST->right,item);}}圣征其其拢陈翔寞土漏医笔汽侣参科网何瞬运浸腑夯蛋塔鲍返撩淄举钩数第6章特殊二叉树第6章特殊二叉树*--非递归算法boolFind1(BTreeNode*BST,ElemType&item)//二叉搜索树查找的非递归算法{while(BST!=NULL){if(item==BST->data){item=BST->data;returntrue;}elseif(item<BST->data)BST=BST->left;elseBST=BST->right;}returnfalse;}赦锐盲抡窿误橱逗薪帅梁敢孽貌芯腑降米驶溯耐瞬抡酣姜嚣淖琶茅阶偶瞳第6章特殊二叉树第6章特殊二叉树