java二叉树删除,二叉树查找算法java
00-1010定义添加节点查询节点删除节点
00-1010二叉查找树(ADT)是一棵二叉树，对于树种有某个节点X，它的左节点都小于X，右节点都大于X，下面是匹配
必需的二叉查找树：
00-1010 1.定义节点类3360
类节点{ int val节点向左；节点右移；public Node(int val){ this . val=val；}}2.插入元素
我们使用递归方法：
1.判断是否与根节点相同，如果相同，则不需要操作。
2.如果它小于根元素，则向左看。如果左节点不存在，将其作为左节点插入。
3.如果它比根元素大，就向右看。如果右侧节点不存在，请将其作为右侧节点插入。
代码实现如下：
节点根；/* * * Add element * @ param val */public void Add(intval){ if(root==null){ root=new node(val)；返回；} addNode(val，root)；} private void addNode(int val，Node root){ if(root==null root . val==val){ return；} if(root . val val){ if(root . left==null){ root . left=新节点(val)；}else { addNode(val，root . left)；} } else { if(root . right==null){ root . right=new Node(val)；}else { addNode(val，root . right)；} } }
00-1010我们使用递归方法：
1.判断是否与根节点相同，如果相同则返回true。
2.如果它小于根元素，则向左看。如果左节点为空，将返回false，表示它不存在。
3.如果它比根元素大，就向右看。如果右节点为空，将返回false，表示它不存在。
代码实现如下：3360
/* * *确定指定值是否存在* @param val指定值* @return true -有false -没有*/public boolean find vale(intval){ return is exit(root，val)；} private boolean isExit(Node node，int val){ if(node==null){返回false} if(node . val==val){ return true；} else if(node . val val){ return is exit(node . left，val)；}else { return isExit(node.right，val)；} }
00-1010判断删除元素时的条件：
1.被删除的元素没有叶节点，可以直接删除。比如删除值为1的节点，虽然平衡性不是很好，但还是符合二叉查找树的特点。
2.被删除的元素只有一个节点。删除该元素，并将指针指向其子节点，例如值为4的节点3360。
3.被删除的元素有左右节点。从右边的节点中找出比这个节点大的最小的节点作为新节点A，比如删除节点值为2的节点3360。
代码实现如下：3360
/* * *删除元素* 1。被删除的元素
有叶子节点，直接删除 * 2.删除的元素只有一个节点，删除元素并将指针指向其子节点 * 3.删除的元素有两个节点，从右节点中找出大于该元素的最小值，作为新的节点 * @param val */ public void deleteElement(int val){ deleteElement(null,root,val,true); } /** * 删除元素 * @param prev 父节点 * @param root 当前节点 * @param val 删除值 * @param isright 是否是右节点 */ private void deleteElement(Node prev,Node root,int val,boolean isright){ if(root.val==val){ //删除的元素没有叶子节点，直接删除 if(root.left==null && root.right==null){ changeValue(prev,null,isright); }else if(root.left!=null && root.right!=null){ //3.删除的元素有两个节点，从右节点中找出大于该元素的最小值，作为新的节点 changeValue(prev,new Node(findMinGt(root,root.right,true)),isright); if(prev==null){ //对于头结点的删除特殊处理 prev=this.root; prev.left=root.left; prev.right=root.right; return; } if(isright){ prev.right.right=root.right; prev.right.left=root.left; }else { prev.left.right=root.right; prev.left.left=root.left; } }//删除的元素只有一个节点，删除元素并将指针指向其子节点 else if(root.left!=null){ changeValue(prev,root.left,isright); }else { changeValue(prev,root.right,isright); } return; } if(root.val>val){ deleteElement(root,root.left,val,false); }else{ deleteElement(root,root.right,val,true); } } //改变元素值 private void changeValue(Node prev,Node value,boolean isright){ if(prev==null){ root=value; return; } if(isright){ prev.right=value; }else { prev.left=value; } } //寻找大于根节点的最小值 private int findMinGt(Node prev,Node root,boolean isRight){ if(root.left==null && root.right==null){ changeValue(prev,null,isRight); return root.val; } if(root.left==null){ changeValue(prev,null,isRight); return root.val; } return findMinGt(root,root.left,false); }到此这篇关于Java实现二叉查找树的增删查详解的文章就介绍到这了,更多相关Java二叉查找树增删查内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。