《数据结构》课程授课教案（讲稿）第九章 查找 第三节 动态查找

课程名称：数据结构第16周，第16讲次摘要第九章查找授课题目（章、节）第三节动态查找【目的要求】通过本讲课程的学习，掌握二叉排序树类的设计，二叉排序树的查找、插入、删除算法。【重点】掌握二叉排序树的查找、插入和删除算法。【难点】二叉排序树的插入和删除算法。内容【本讲课程的引入】上一次课我们讨论了静态查找，这一次课我们要学习的是动态查找，动态查找除了包括静态查找的要求之外，还包括在查找过程中插入不存在的数据元素和删除已存在的数据元素的要求。所以对于动态查找的结构主要是二叉树结构和树结构。我们主要讨论二叉排序树。【本讲课程的内容】第三节动态查找典型的动态表一二叉排序树1.二叉排序树的基本概念一或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。2.二叉排序树结点类public class BiTreeNode(private BiTreeNode leftChild:private BiTreeNode rightChild;private BiTreeNode parent:private int data;public BiTreeNodeOfleftChild = null;rightChild = null;public BiTreeNode(intitem)(leftChild = null:rightChild = null:data = item;publicBiTreeNode(intitem,BiTreeNodeleft,BiTreeNoderight)fdata = item;leftChild = left:rightChild = right;

课程名称：数据结构 第 16 周，第 16 讲次 摘 要 授课题目（章、节） 第九章 查找 第三节 动态查找 【目的要求】通过本讲课程的学习，掌握二叉排序树类的设计，二叉排序树的查找、插入、删除算法。 【重 点】掌握二叉排序树的查找、插入和删除算法。 【难 点】二叉排序树的插入和删除算法。 内 容 【本讲课程的引入】上一次课我们讨论了静态查找，这一次课我们要学习的是动态查找， 动态查找除了包括静态查找的要求之外，还包括在查找过程中插入不存在的数据元素和删 除已存在的数据元素的要求。所以对于动态查找的结构主要是二叉树结构和树结构。我们 主要讨论二叉排序树。 【本讲课程的内容】 第三节 动态查找 典型的动态表———二叉排序树 1.二叉排序树的基本概念 -或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 2.二叉排序树结点类 public class BiTreeNode{ private BiTreeNode leftChild; private BiTreeNode rightChild; private BiTreeNode parent; private int data; public BiTreeNode(){ leftChild = null; rightChild = null; } public BiTreeNode(int item){ leftChild = null; rightChild = null; data = item; } public BiTreeNode(int item, BiTreeNode left, BiTreeNode right){ data = item; leftChild = left; rightChild = right; }

public void setParent(BiTreeNodeparent)this.parent = parent;public BiTreeNode getParent O(return parent;1public void setLeftChild(BiTreeNode left){leftChild = left;子public void setRightChild(BiTreeNode right)(rightChild = right;Hpublic void setData(int data) (this. data = data;1public BiTreeNodegetLeft O{return leftChild;1public BiTreeNode getRightO(return rightChild:}public int getDataOfreturn data;1二叉排序树类public class BiSearchTreefprivate BiTreeNode root;public BiSearchTreeOfroot = null;1public void setRoot(BiTreeNode t) (root = t;1public BiTreeNode getRoot ((return root;1public BiTreeNode getLeft (BiTreeNode current) (return current != null ? current.getLeftO : null;1public BiTreeNode getRight(BiTreeNode current)(return current != null ? current.getRightO : null:13.二叉排序树的查找算法：

public void setParent(BiTreeNode parent){ this.parent = parent; } public BiTreeNode getParent(){ return parent; } public void setLeftChild(BiTreeNode left){ leftChild = left; } public void setRightChild(BiTreeNode right){ rightChild = right; } public void setData(int data){ this.data = data; } public BiTreeNode getLeft(){ return leftChild; } public BiTreeNode getRight(){ return rightChild; } public int getData(){ return data; } } 二叉排序树类 public class BiSearchTree{ private BiTreeNode root; public BiSearchTree(){ root = null; } public void setRoot(BiTreeNode t){ root = t; } public BiTreeNode getRoot(){ return root; } public BiTreeNode getLeft(BiTreeNode current){ return current != null ? current.getLeft() : null; } public BiTreeNode getRight(BiTreeNode current){ return current != null ? current.getRight() : null; } 3.二叉排序树的查找算法 ：

publicBiTreeNode find(intitem)if(root != null)(BiTreeNodetemp=root;while(temp != null)(if(temp.getData()== item)return temp;if(temp.getData()ptr.getData()(if(ptr.getRight()--null)(BiTreeNodetemp=newBiTreeNode（item）：//生成新结点temp.setParent（ptr）；//把ptr结点设为temp结点的父结点ptr.setRightChild（temp）：//把temp结点设为ptr结点的右孩子结点else insert(ptr.getRightO,item)://在右子树递归子return;1(2)删除删除操作的要求是：首先查找数据元素是否在二叉排序树中存在，若不存在则结束：若存在则按下面四种情况分别进行不同的删除操作。这四种情况是：（1）要删除结点无孩子结点：（2）要删除结点只有左孩子结点；（3）要删除结点只有右孩子结点：（4）要删除结点有左右孩子结点。对于上述四种不同情况，相应的删除方法是：（1）要册删除结点无孩子结点时，直接删除该结点。（2）要删除结点只有左孩子结点时，删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点。（3）要删除结点只有右孩子结点时，删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点

public BiTreeNode find(int item){ if(root != null){ BiTreeNode temp = root; while(temp != null){ if(temp.getData() == item) return temp; if(temp.getData() ptr.getData()){ if(ptr.getRight() == null){ BiTreeNode temp = new BiTreeNode(item); //生成新结点 temp.setParent(ptr); //把 ptr 结点设为 temp 结点的父结点 ptr.setRightChild(temp); //把 temp 结点设为 ptr 结点的右孩子结点 } else insert(ptr.getRight(), item); //在右子树递归 } return; } (2)删除 删除操作的要求是：首先查找数据元素是否在二叉排序树中存在，若不存在则结束；若存 在则按下面四种情况分别进行不同的删除操作。这四种情况是 ： （1）要删除结点无孩子结点； （2）要删除结点只有左孩子结点； （3）要删除结点只有右孩子结点； （4）要删除结点有左右孩子结点。 对于上述四种不同情况，相应的删除方法是： （1）要删除结点无孩子结点时，直接删除该结点。 （2）要删除结点只有左孩子结点时，删除该结点且使被删除结点的双亲结点指向被删除结 点的左孩子结点。 （3）要删除结点只有右孩子结点时，删除该结点且使被删除结点的双亲结点指向被删除结 点的右孩子结点

（4）要删除结点有左右孩子结点时，分如下三步完成：首先寻找数据元素值大于要删除结点数据元素关键字的最小值（是其右子树的最左孩子结点），然后把右子树的最左结点的数据元素值拷贝到要删除的结点上：最后删除右子树的最左结点。public void delete(BiTreeNode ptr, int item)(if(ptr|=null)(if(itemptr.getData(）//在右子树递归delete(ptr.getRightO,item);else if(ptr.getLeftO=null&ptr.getRightO!=null){//要删除结点寻找到，并且要删除结点左右子树均存在的情况BiTreeNode min;min=ptr.getRight（：//取当前结点的右孩子结点while(min.getLeft (O!=null)min=min.getLeftO：//min取到最左孩子结点ptr.setData（min.getDataO）：//把min的数据值赋给ptr结点delete(ptr.getRightO,min.getDataO);//在ptr结点的右子树中递归删除min结点小else(//要删除结点寻找到，并且要删除结点只有右子树的情况if(ptr.getLeftO == null &&ptr.getRightO != null)(if(ptr.getParentO==null){root=ptr.getRightO;1elsefif (ptr.getParentO.getRightO==ptr)(ptr.getParentO.setRightChild(ptr.getRight())://让ptr双亲的右孩子指针指向ptr的右孩子结点1elsefptr.getParentO.setLeftChild(ptr.getRightO)://让ptr双亲的左孩子指针指向ptr的右孩子结点1ptr.getRightO.setParent(ptr.getParentO);//让ptr右孩子的双亲指向ptr的双亲结点于1elseif(ptr.getRightO==null&&ptr.getLeftO！=null)(//删除结点只有左子树if (ptr. getParent ()==null) (root=ptr.getLeftO1elsetif(ptr.getParent(.getRightO==ptr)(

（4）要删除结点有左右孩子结点时，分如下三步完成：首先寻找数据元素值大于要删除结 点数据元素关键字的最小值（是其右子树的最左孩子结点） ，然后把右子树的最左结点的 数据元素值拷贝到要删除的结点上；最后删除右子树的最左结点。 public void delete(BiTreeNode ptr, int item){ if(ptr != null){ if(item ptr.getData())//在右子树递归 delete(ptr.getRight(), item); else if(ptr.getLeft() != null && ptr.getRight() != null){ //要删除结点寻找到，并且要删除结点左右子树均存在的情况 BiTreeNode min; min = ptr.getRight();//取当前结点的右孩子结点 while(min.getLeft() != null) min = min.getLeft(); //min 取到最左孩子结点 ptr.setData(min.getData());//把 min 的数据值赋给 ptr 结点 delete(ptr.getRight(), min.getData()); //在 ptr 结点的右子树中递归删除 min 结点 } else{//要删除结点寻找到，并且要删除结点只有右子树的情况 if(ptr.getLeft() == null && ptr.getRight() != null){ if(ptr.getParent()==null){ root=ptr.getRight(); } else{ if (ptr.getParent().getRight()==ptr){ ptr.getParent().setRightChild(ptr.getRight()); //让 ptr 双亲的右孩子指针指向 ptr 的右孩子结点 } else{ ptr.getParent().setLeftChild(ptr.getRight()); //让 ptr 双亲的左孩子指针指向 ptr 的右孩子结点 } ptr.getRight().setParent(ptr.getParent()); //让 ptr 右孩子的双亲指向 ptr 的双亲结点 } } else if(ptr.getRight() == null && ptr.getLeft() != null){//删除结点只有左 子树 if(ptr.getParent()==null){ root=ptr.getLeft(); } else{ if (ptr.getParent().getRight()==ptr){

ptr.getParentO.setRightChild(ptr.getLeftO);//让ptr双亲的右孩子指针指向ptr的左孩子结点1elsefptr.getParentO.setLeftChild(ptr.getLeftO)://让ptr双亲的左孩子指针指向ptr的左孩子结点1ptr.getLeft(.setParent(ptr.getParentO)//让ptr左孩子的双亲指向ptr的双亲结点子else(//要删除结点寻找到，并且要删除结点为叶结点的情况BiTreeNode p=ptr.getParent();if (p==null) troot=null;1elseif（p.getLeft(==ptr）//若要删除结点在双亲的左孩子上p.setLeftChild(nul1）：//把双亲的左孩子置空else//若要删除结点在双亲的右孩子上p.setRightChild(null)；//把双亲的右孩子置空111将线性表构造成二叉排序树的优点：①查找过程与顺序结构有序表中的折半查找相似，查找效率高：②中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）：③如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。5.二叉排序树的查找分析1）二叉排序树上查找某关键字等于结点值的过程，其实就是走了一条从根到该结点的路径。（与折半查找类似）比较的关键字次数=此结点的层次数；最多的比较次数一树的深度（或高度）2）一棵二叉排序树的平均查找长度为：17ASL=二n,.Cn1折半查找查找长度为n的有序表，其判定树是唯一的，而含有n个结点的二叉排序树却不唯一。对于含有相同一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也不相同

ptr.getParent().setRightChild(ptr.getLeft()); //让 ptr 双亲的右孩子指针指向 ptr 的左孩子结点 } else{ ptr.getParent().setLeftChild(ptr.getLeft()); //让 ptr 双亲的左孩子指针指向 ptr 的左孩子结点 } ptr.getLeft().setParent(ptr.getParent()); //让 ptr 左孩子的双亲指向 ptr 的双亲结点 } } else{//要删除结点寻找到，并且要删除结点为叶结点的情况 BiTreeNode p = ptr.getParent(); if(p==null){ root=null; } else if(p.getLeft() == ptr) //若要删除结点在双亲的左孩子上 p.setLeftChild(null); //把双亲的左孩子置空 else //若要删除结点在双亲的右孩子上 p.setRightChild(null); //把双亲的右孩子置空 } } } } 将线性表构造成二叉排序树的优点： ① 查找过程与顺序结构有序表中的折半查找相似，查找效率高； ② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； ③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除 时只需修改指针而不需移动元素。 5.二叉排序树的查找分析 1) 二叉排序树上查找某关键字等于结点值的过程，其实就是走了一条从根到该结点的路 径。（与折半查找类似） 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度） 2) 一棵二叉排序树的平均查找长度为： 折半查找查找长度为 n 的有序表，其判定树是唯一的，而含有 n 个结点的二叉排序树 却不唯一。对于含有相同一组结点的表，由于结点插入的先后次序不同，所构成的二叉排 序树的形态和深度也不相同

【本讲课程的小结】二叉排序树是动态查找中比较基本的一种结构，希望大家回去好好复习，要求掌握二叉排序树的查找、插入和删除算法。【本讲课程的作业】设计递归结构的二叉排序树查找成员函数

【本讲课程的小结】二叉排序树是动态查找中比较基本的一种结构，希望大家回去好好复 习，要求掌握二叉排序树的查找、插入和删除算法。 【本讲课程的作业】 设计递归结构的二叉排序树查找成员函数