数据结构二叉查找树,java创建二叉树数据结构

　　00-1010 1.搜索树的概念2。简单实现二叉查找树2.1查找2.2插入2.3删除2.4修改3。二叉查找树的表现

　　00-1010二叉查找树是一种特殊的二叉树，也称为二叉查找树和二叉排序树。它有几个特点：

　　如果左子树存在，则左子树的每个节点的值都小于根节点的值。如果右子树存在，则右子树的每个节点的值都大于根节点的值。按照中间顺序遍历二叉查找树，得到的序列依次递增。二叉查找树的左右子树都是二分搜索法树。二叉查找树的节点值不能重复。

　　00-1010让我们简单地实现下面的搜索树，所以我们不会使用泛型。二叉查找树的基本结构：

　　public class BinarySearchTree { static class Node { public int val；公共节点左；公共节点权限；public Node(int val){ this . val=val；} }公共节点根；//其他方法}

　　00-1010二叉查找树最擅长搜索。根据二叉查找树的定义，左子树的元素小于根，右子树的元素大于根，所以我们只需要比较根节点和目标元素的值就可以实现搜索功能。

　　等于根目标元素，表示已经找到。根元素比目标元素大，请转到左边的子树查找它。根元素小于目标元素。在右边的子树中寻找它。如果左右子树都找不到，那就是找不到。请参考实施代码：

　　公共节点搜索(int key){ Node cur=this . root；而(cur！=null) {//根等于目标元素，表示已经找到。if (cur.val==key)返回cur//根大于目标元素。去左边的子树找。else if (cur.val键)cur=cur.left//根小于目标元素。在右边的子树中寻找它。else cur=cur.right}//此时cur=null，左右子树都找不到，所以找不到。返回cur}

　　00-1010您需要在二叉查找树中插入一个元素。首先，你得找到一个合适的插入位置。你是怎么找到它的？其实搜索树就是用来找一个空位，以及如何把目标节点插入这个位置。

　　等于根插入元素，则插入元素不能等于搜索树中的元素，插入失败。根比插入的元素大，在左边的子树中寻找它。根小于插入的元素。在右边的子树中寻找它。找到的节点是空的，所以这个位置就是我们要找的空缺。

　　当你查找到一个职位空缺时，你无法获得该职位空缺的上一个职位，所以你需要在每次查找时保存上次搜索到的职位。

　　找到位置后，将目标节点插入该位置。

　　请参考实施代码：

　　public boolean insert(int val) {//节点为空，直接插入if(root==null){ root=new node(val)；返回true} Node cur=this.root//当前搜索位置节点parent=null//查找最后一个位置while (cur！=null){ parent=cur；if(val cur . val)cur=cur . right；else if(val cur . val)cur=cur . left；否则返回false}//开始插入，找到空位之前的位置，比插入的元素小。空位在右边，插入右边if(val parent . val){ parent . right=new node(v

　　al); } else { //比插入元素大，空位在左边，插入左边 parent.left = new Node(val); } return true; }

2.3删除

删除是搜索树基本操作中最麻烦的一个操作，需要考虑多种情况。

　　不妨设需要删除的结点为cur，cur的父结点为parent，搜索树的根结点为root。首先需要删除结点，那就得找到结点，所以第一步是找结点，思路与查找的思路一模一样。

　　第二步那就是删除了，删除结点大概有下面几种情况：

　　情况1：cur.left == null

　　 cur == root，让root = cur.right; cur != root且parent.left == cur，让parent.left = cur.right; cur != root且parent.right == cur，让parent.right = cur.right。情况2：cur.right == null

　　 cur == null，让root = cur.left; cur != root且parent.left == cur，让parent.left = cur.left; cur != root且parent.right == cur，让parent.right = cur.left。情况3：cur.left != null && cur.right != null

　　方案1：找到cur右子树中最小的元素target，然后将该元素的值覆盖到cur处（可以理解为交换），此时等价于删除target处的结点，即该结点的父结点为preTarget。

　　因为target为cur右子树最小的一个结点，所以target.left == null，此时preTarget.left == target，所以删除时按照上面的情况1去进行删除。

　　但是还有一种特殊情况，那就是cur.right就是最小结点，此时preTarget==cur，即preTarget.right == target，这时删除时要将 preTarget.right = target.right。

　　方案2：找到cur左子树中最大的元素target，然后将该元素的值覆盖到cur处（可以理解为交换），此时等价于删除target处的结点，即该结点的父结点为preTarget。

　　因为target为cur左子树最大的一个结点，所以target.right == null，此时preTarget.right == target，所以删除时按照上面的情况2去进行删除。

　　但是还有一种特殊情况，那就是cur.left就是左子树最大结点，此时preTarget==cur，即preTarget.left == target，这时删除时要将 preTarget.left = target.left。

　　参考实现代码：

 public void remove(int key) { Node cur = root; Node parent = null; while (cur != null) { if(cur.val == key) { //这里开始删除 removeNode(cur,parent); break; }else if(cur.val < key) { parent = cur; cur = cur.right; }else { parent = cur; cur = cur.left; } } }

removeNode方法（方案1）：

 public void removeNode(Node cur,Node parent) { if(cur.left == null) { if(cur == root) { root = cur.right; }else if(cur == parent.left) { parent.left = cur.right; }else { parent.right = cur.right; } }else if(cur.right == null) { if(cur == root) { root = cur.left; }else if(cur == parent.left) { parent.left = cur.left; }else { parent.right = cur.left; } }else { Node preTarget = cur ; Node target = cur.right; while (target.left != null) { preTarget = target; target = target.left; } cur.val = target.val; if (target == preTarget.left) { preTarget.left = target.right; } else { preTarget.right = target.right; } } }

removeNode方法（方案2）：

 public void removeNode(Node cur,Node parent) { if(cur.left == null) { if(cur == root) { root = cur.right; }else if(cur == parent.left) { parent.left = cur.right; }else { parent.right = cur.right; } }else if(cur.right == null) { if(cur == root) { root = cur.left; }else if(cur == parent.left) { parent.left = cur.left; }else { parent.right = cur.left; } }else { Node preTarget = cur ; Node target = cur.left; while (target.right != null) { preTarget = target; target = target.right; } cur.val = target.val; if (target == preTarget.left) { preTarget.left = target.left; } else { preTarget.right = target.left; } } }

2.4修改

搜索树的修改可以基于删除和插入，先删除目标元素，然后再插入修改元素。

　　参考实现代码：

 public void set(int key, int val) { remove(key); insert(val); }

3.二叉搜索树的性能

在平衡二叉树的情况下（左右子树高度差不超过1），假设有n个结点，此时时间复杂度为二叉树的高度，即 O ( l o g 2 n ) O(log_2n) O(log2n)，但是这只是例行情况，最不理想的情况就是二叉树化为单分支树，时间复杂为 O ( n ) O(n) O(n)。

　　为了解决这个问题，后面引申出AVL树，红黑树，其中TreeMap与TreeSet的底层就是红黑树。具体红黑树是什么，这里就不多说了。

　　本文到底了，你学会了吗？

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

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