常用的数据结构和算法 (7).ppt

《常用的数据结构和算法 (7).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深入java编程专业教程理论讲解部分Ver3.1第026课算法及数据结构概述：树的查询结点的删除树的遍历重点：难点：结点的删除树的遍历树的查询结点的删除第026课算法及数据结构6.4二叉树的查询102131516如图,该树便是一棵搜索二叉树.下面我们要讨论如何查询到5所在的结点.首先我们要访问根结点,判断根结点是否是要查询的目标.5<10,所以根结点不是查询目标且目标可能在.其左子树内6二叉树第026课算法及数据结构102131516然后,对根的左子树进行检查.判断该子树根结点是否是要查询的目标.2<5,则5可能在该

2、子树的右子树中.6.4二叉树的查询6二叉树第026课算法及数据结构102131516判断,该子树的根结点是否是要查找目标.查找成功,返回该结点.若查找到最后为空结点,其后再没有子树则判定树中无该结点,给出失败提示..6.4二叉树的查询6二叉树第026课算法及数据结构privateNodegetNode(intkey)throwsException{Noderesult=root;while(result.key!=key){if(key

3、ult=result.right;}if(result==null){thrownewException("Can'tfindvalueby"+key);}}returnresult;}这是插入结点代码的实现其中subtreeRoot是要查询子树的根newNode是要插入的结点目标结点在当前结点的左子树目标结点在当前结点的右子树查询到最终子树没有目标结点查到目标结点6.4二叉树的查询6二叉树第026课算法及数据结构6.5二叉树的删除树的结点删除的操作相对繁琐一些.102131516如图,设我们将删除2这个结点.由于要

4、删除的结点下有两棵子树而父结点只能接收一棵子树,所以有必要对其子树的结构做一些调整.6二叉树第026课算法及数据结构102131516查询的第一步首先要掌握目标结点(被删除结点)及其父结点.其过程与查询类似,但要注意保留其父结点的引用.6.5二叉树的删除6二叉树第026课算法及数据结构102131516获得目标结点及其父结点后要判断目标结点是其父结点的左子树还是右子树.现2是10的左子树.然后按照如下步骤进行.6.5二叉树的删除6二叉树第026课算法及数据结构102131516将目标结点的左子树添加到其父结点的左子树

5、中.6.5二叉树的删除6二叉树第026课算法及数据结构102131516将目标结点的右子树加入到其自己的左子树中6.5二叉树的删除6二叉树第026课算法及数据结构10131516删除目标结点6.5二叉树的删除6二叉树第026课算法及数据结构10131516整理后为这是当目标结点为其父结点的左子树时的操作.下面介绍,当目标结点为其父结点的右子树时的操作6.5二叉树的删除6二叉树第026课算法及数据结构1021311216如图,设我们将删除13这个结点.查询等操作相同.以获得目标结点及其父结点6.5二叉树的删除6二叉树第

6、026课算法及数据结构1021311216现已知目标结点与其父结点且目标结点为其父结点的右子树6.5二叉树的删除6二叉树第026课算法及数据结构1021311216首先将目标结点的右子树添加到其父结点的右子树中.6.5二叉树的删除6二叉树第026课算法及数据结构1021311216然后将目标结点的左子树添加到其自身的左子树中.6.5二叉树的删除6二叉树第026课算法及数据结构10211216最后删除目标结点6.5二叉树的删除6二叉树第026课算法及数据结构10211216整理后为6.5二叉树的删除6二叉树第026课算

7、法及数据结构publicvoiddelete(intkey)throwsException{Nodecurrent=root;Nodeparent=null;while(current.key!=key){parent=current;if(key

8、arent.left==current){parent.left=current.left;insertNode(parent,current.right);current=null;}else{parent.right=current.right;insertNode(parent,current.left);current=null;}}这