java二叉树排序算法,二叉排序树的实现

　　00-1010排序二叉树概念排序二叉树类定义添加节点，遍历查找节点，查找节点的父节点，删除节点

　　00-1010二叉排序树，也叫二叉查找树，也叫二叉查找树。是一种数据结构。对于二叉排序树的任意非叶节点，要求左子节点的值小于当前节点的值，右子节点的值大于当前节点的值。按中间顺序遍历二叉排序树，结果从小到大排序。

目录

公共类binarySortTree { class Node { int value；节点向左；节点右移；公共节点(int value){ this . value=value；} public void display(){ system . out . print(this . value )；} }节点根；}

　　00-1010排序二叉树添加节点非常简单。不管用递归还是循环，思路都是一样的。这里，我用递归来解释。

　　每添加一个节点，判断value(添加节点的值)和root的值的关系：如果root.value值，则该节点要添加到root的右边子树中。如果右边子树为空，直接加：root . right=new node(value)；如果右边的子树不为空，那么递归进入右边的子树(设root.right为root)。如果root.value=value，则该节点应该添加到root的左子树中。如果左子树为空，直接加：root . left=new node(value)；如果左子树不为空，那么递归进入右子树(make root.left root)。代码如下：

　　//添加一个节点//这个方法可以调用类内部方法的私有void add (node root，int value){//添加一个值大于根节点的节点，将if (valueroot.value)添加到根节点的右子树{//根节点的右子树为空，直接添加if(root . right==null){ root . right=new node。}//根节点的右子树不为空。递归插入else{ add(root.right，value)到右边的子树中；} }//添加节点的值小于等于根节点的值，节点要添加到左子树else{ //左子树为空，直接添加if(root . left==null){ root . left=new node(value)；}//左子树不为空，递归添加else{ add(root.left，value)到左子树；} } }//这个方法在类内外都可以调用public void add(int value){//当前树是空树if(root==null){ root=newnode(value)；返回；} add(根，值)；}

排序二叉树概念

因为二叉排序树中顺序遍历的结果是排序的，所以这里只提供中顺序遍历。

　　代码如下：

　　//中序遍历树private void in pre order(node root){ if(root==null)return；in pre order(root . left)；root . display()；inPrevOrder(root . right)；} public void inprevorder(){ system . out . print(中序遍历：)；inPrevOrder

　　(root); }

查找节点

该方法是查找value在二叉树中对应的位置，是为删除节点提供的方法。

/** * 通过value查找二叉树中的节点 * @param root 被查找树的根节点 * @param value 要查找的值 * @return 返回查找到的节点 */ private Node searchNode(Node root, int value){ //被查找树为null，要查找节点不存在 if(root == null) return null; //找到了，返回节点 else if(root.value == value){ return root; } //该节点不是要查找节点，继续查找 else{ //该节点的值大于value，往该节点的左子树递归查找 if(root.value > value){ return searchNode(root.left, value); } //该节点的值小于value,往该节点的右子树递归查找 else{ return searchNode(root.right, value); } } }

查找某一节点的父节点

该方法是查找二叉树中一个节点的父节点，也是为删除节点提供的方法。

 /** * 查找某节点的父节点，并返回 * @param root 被查找树的根节点 * @param node 要查找的节点 * @return 返回被查找节点的父节点 */ private Node searchParentNode(Node root, Node node){ //被查找树为null或者根节点就是要查找的节点，那么要查找节点的父节点不存在 if(root == null root == node){ return null; } else if(root.left != null && root.left == node root.right != null && root.right == node){ return root; } else{ if(root.value > node.value){ return searchParentNode(root.left, node); } else{ return searchParentNode(root.right, node); } } }

删除节点

删除节点是排序二叉树中最麻烦的方法，因为它有很多种情况。

　　方法如下：

第一种情况：删除的节点是叶子节点(1)需求先去找到要删除的结点targetNode

 

　　(2)找到targetNode的父结点parent

　　(3)确定targetNode是parent的左子结点还是右子结点 3.1如果targetNode是parent的左子结点:parent.left = null; 3.2如果targetNode是parent的右子结点:parent.right = null; 第二种情况:删除只有一颗子树的节点(1)需求先去找到要删除的结点targetNode

　　(2)找到targetNode的父结点parent

　　(3)确定targetNode的子结点是左子结点还是右子结点

　　(4)确定targetNode是parent的左子结点还是右子结点

　　(5)如果targetNode有左子结点 5.1如果targetNode是parent的左子结点parent.left = targetNode.left; 5.2如果targetNode是parent的右子结点parent.right = targetNode.left;(6)如果targetNode有右子结点 6.1如果targetNode是 parent 的左子结点parent.left = targetNode.right; 6.2如果targetNode是parent 的右子结点parent.right = targetNode.right 第三种情况：删除的节点有左右两个子树(1)需求先去找到要删除的结点targetNode

　　(2)在右子树找到最小的节点，用一个temp保存这个节点的值，然后删除这个最小节点(该最小节点一定是满足第一种情况的)

　　(3)targetNode.value = temp

　　

除了以上情况，还要考虑要删除的节点就是根节点的情况(此时它的父节点为null)，下面会在代码中展示，代码如下：

public void remove(int vlaue){ //找到要删除的节点 Node targetNode = searchNode(root,vlaue); //要删除节点不存在 if(targetNode == null) return; //找到要删除节点的父节点 Node targetNodeParent = searchParentNode(root,targetNode); //要删除节点为叶子节点 if(targetNode.left == null && targetNode.right == null){ //要删除的节点就是根节点 if(targetNodeParent == null){ root = null; } else{ //要删除节点是其父节点的左节点 if(targetNodeParent.left == targetNode){ targetNodeParent.left = null; } else{ targetNodeParent.right = null; } } } //要删除节点只有一个左子树 else if(targetNode.left != null && targetNode.right == null){ //要删除的节点就是根节点 if(targetNodeParent == null) { root = root.left; } //要删除节点是其父节点的左节点 else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){ targetNodeParent.left = targetNode.left; } //要删除节点是其父节点的右节点 else{ targetNodeParent.right = targetNode.left; } } //要删除节点只有一个右子树 else if(targetNode.right != null && targetNode.left == null){ //要删除的节点就是根节点 if(targetNodeParent == null) { root = root.right; return; } //要删除节点是其父节点的左节点 else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){ targetNodeParent.left = targetNode.right; } //要删除节点是其父节点的右节点 else{ targetNodeParent.right = targetNode.right; } } //要删除节点右左右都有节点 else{ //找到右子树最小的节点 Node minNode = targetNode.right; while(minNode.left != null){ minNode = minNode.left; } int temp = minNode.value; //找到右子树上最小节点的父节点 Node minNodeParent = searchParentNode(targetNode.right,minNode); //右子树根节点就是最小节点 if(minNodeParent == null){ targetNode.right = minNode.right; } else{ //要删除节点是其父节点的左节点 minNodeParent.left = minNode.right; } targetNode.value = temp; } }

到此这篇关于Java超详细讲解排序二叉树的文章就介绍到这了,更多相关Java排序二叉树内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。