常用数据结构和算法7

深入java编程专业教程理论讲解部分Ver3.11第026课算法及数据结构概述：

树的查询结点的删除树的遍历重点：难点：

结点的删除树的遍历

树的查询结点的删除2第026课算法及数据结构6.4二叉树的查询102131516如图,该树便是一棵搜索二叉树.下面我们要讨论如何查询到5所在的结点.首先我们要访问根结点,判断根结点是否是要查询的目标.5<10,所以根结点不是查询目标且目标可能在.其左子树内6二叉树3第026课算法及数据结构102131516然后,对根的左子树进行检查.判断该子树根结点是否是要查询的目标.2<5,则5可能在该子树的右子树中.6.4二叉树的查询6二叉树4第026课算法及数据结构102131516判断,该子树的根结点是否是要查找目标.查找成功,返回该结点.若查找到最后为空结点,其后再没有子树则判定树中无该结点,给出失败提示..6.4二叉树的查询6二叉树5第026课算法及数据结构privateNodegetNode(intkey) throwsException{Noderesult=root;while(result.key!=key){ if(key<result.key){ result=result.left; }else{ result=result.right; } if(result==null){ thrownewException("Can'tfindvalueby"+key); }}returnresult;}这是插入结点代码的实现其中subtreeRoot是要查询子树的根newNode是要插入的结点目标结点在当前结点的左子树目标结点在当前结点的右子树查询到最终子树没有目标结点查到目标结点6.4二叉树的查询6二叉树6第026课算法及数据结构6.5二叉树的删除树的结点删除的操作相对繁琐一些.102131516如图,设我们将删除2这个结点.由于要删除的结点下有两棵子树而父结点只能接收一棵子树,所以有必要对其子树的结构做一些调整.6二叉树7第026课算法及数据结构102131516查询的第一步首先要掌握目标结点(被删除结点)及其父结点.其过程与查询类似,但要注意保留其父结点的引用.6.5二叉树的删除6二叉树8第026课算法及数据结构102131516获得目标结点及其父结点后要判断目标结点是其父结点的左子树还是右子树.现2是10的左子树.然后按照如下步骤进行.6.5二叉树的删除6二叉树9第026课算法及数据结构102131516将目标结点的左子树添加到其父结点的左子树中.6.5二叉树的删除6二叉树10第026课算法及数据结构102131516将目标结点的右子树加入到其自己的左子树中6.5二叉树的删除6二叉树11第026课算法及数据结构10131516删除目标结点6.5二叉树的删除6二叉树12第026课算法及数据结构10131516整理后为这是当目标结点为其父结点的左子树时的操作.下面介绍,当目标结点为其父结点的右子树时的操作6.5二叉树的删除6二叉树13第026课算法及数据结构1021311216如图,设我们将删除13这个结点.查询等操作相同.以获得目标结点及其父结点6.5二叉树的删除6二叉树14第026课算法及数据结构1021311216现已知目标结点与其父结点且目标结点为其父结点的右子树6.5二叉树的删除6二叉树15第026课算法及数据结构1021311216首先将目标结点的右子树添加到其父结点的右子树中.6.5二叉树的删除6二叉树16第026课算法及数据结构1021311216然后将目标结点的左子树添加到其自身的左子树中.6.5二叉树的删除6二叉树17第026课算法及数据结构10211216最后删除目标结点6.5二叉树的删除6二叉树18第026课算法及数据结构10211216整理后为6.5二叉树的删除6二叉树19第026课算法及数据结构publicvoiddelete(intkey)throwsException{Nodecurrent=root;Nodeparent=null;while(current.key!=key){parent=current;if(key<current.key){current=current.left;}else{current=current.right;}if(current==null){thrownewException( "delete:Can'tfindvalueby"+key);}}if(parent.left==current){parent.left=current.left;insertNode(parent,current.right);current=null;}else{parent.right=current.right;insertNode(parent,current.left);current=null;}}这是插入结点代码的实现其中subtreeRoot是要查询子树的根newNode是要插入的结点查询目标结点及其父结点目标结点在其父结点的左子树目标结点在其父结点的右子树6.5二叉树的删除6二叉树20第026课算法及数据结构6.6二叉树的遍历二叉树的遍历分为:前序遍历中序遍历后序遍历.前序遍历:按照先访问根结点,然后分别访问其左子树右子树.其子树的访 问顺序仍然按照该规则进行.中序遍历:按照先访问左子树,然后分别访问根结点.最后访问其右子树.其 子树的访问顺序仍然按照该规则进行.后序遍历:按照先分别访问其左子树右子树,最后访问其根结点.其子树的 访问顺序仍然按照该规则进行.6二叉树21第026课算法及数据结构这里主要介绍一下前序遍历的递归方法.其余遍历类似.publicvoidpreOrder(NodesubtreeRoot){ if(subtreeRoot!=null){ System.out.print(""+subtreeRoot+""); preOrder(subtreeRoot.left); preOrder(subtreeRoot.right); }}6.6二叉树的遍历6二叉树22第026课算法及数据结构这里主要介绍一下前序遍历的递归方法.其余遍历类似.publicvoidpreOrder(NodesubtreeRoot){ if(subtreeRoot!=null){ System.out.print(""+subtreeRoot+""); preOrder(subtreeRoot.left); preOrder(subtreeRoot.right); }}将访问结点输出访问其左子树访问其右子树关于二叉树其完整代码参见MyTrea.java6.6二叉树的遍历6二叉树23小结：

树的查询树的删除