Java排序二叉树怎么定义

这篇文章主要介绍了Java排序二叉树怎么定义的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇Java排序二叉树怎么定义文章都会有所收获，下面我们一起来看看吧。

排序二叉树概念

• 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。

• 对于二叉排序树的任何一个非叶子节点， 要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

• 对二叉排序树进行中序遍历，结果就是按从小到大排序的。

排序二叉树类的定义

public class binarySortTree {    class Node{        int value;        Node left;        Node right;        public Node(int value){            this.value = value;        }        public void display(){            System.out.print(this.value + " ");        }    }    Node root;}

添加节点

排序二叉树添加节点的十分简单，无论使用递归还是循环，思路都一样，这里我用递归的方式讲解。

1. 每次添加一个节点时，判断value(添加节点的值)与root的值的大小关系： 若root.value < value， 说明该节点应该添加在root的右子树上。如果右子树为空，直接添加：root.right = new Node(value)；如果右子树不为空，那么递归进右子树(令root.right为root)。

2. 若root.value >= value， 说明该节点应该添加在root的左子树上。如果左子树为空，直接添加：root.left = new Node(value)；如果左子树不为空，那么递归进右子树(令root.left为root)。

代码如下：

//添加节点//此方法可以类内部方法的调用    private void add(Node root,int value){        //添加节点的值大于根节点的值，该节点添加到根节点的右子树上        if(value > root.value){            //根节点的右子树为空，直接添加            if(root.right == null){                root.right = new Node(value);            }            //根节点右子树不为空，递归往右子树插            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 = new Node(value);            return;        }        add(root, value);    }

中序遍历

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

代码如下：

//中序遍历树    private  void inPrevOrder(Node root){        if(root == null) return;        inPrevOrder(root.left);        root.display();        inPrevOrder(root.right);    }    public void inPrevOrder(){        System.out.print("中序遍历：");        inPrevOrder(root);    }

查找节点

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

    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);            }        }    }

查找某一节点的父节点

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

     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排序二叉树怎么定义”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注编程网行业资讯频道。