二叉排序树又名二叉查找树，不同于普通的二叉树，该形式可以使二叉树有序，使其左孩子一定小于该节点值，右孩子一定大于该节点值，于是其中序遍历便是一个递增的数列 。同时故其查找效率为O(lgN)即二叉树的高度 。
下面首先介绍下BST树的查找算法 。
BST树查找很简单，首先根节点，如果比该节点值大从其右孩子中查找，如果比其小则从其左孩子中查找 。直到找到或者该节点为空为止 。

文章插图
下面是查找的代码实现
public boolean findNode(int aim) {/*二叉排序树的查找时间复杂度为O(lgn)*/TreeNode current = root;while (current != null && current.value != aim) {if (current.value > aim)current = current.left;else if (current.value < aim)current = current.right;else if(current.value=http://www.kingceram.com/post/=aim)return true;}return false;}
下面介绍插入节点 。插入节点其实首先也得进行查找，查找该插入的节点放在什么位置 。
首先如果该插入节点大于该节点root，则对其右孩子进行查找，如果小于root则对其左孩子进行查找 。直到找到某节点其左孩子或者右孩子为空，则插入 。

文章插图
public void insert(int aim){TreeNode node=new TreeNode();//新建插入的节点node.value=http://www.kingceram.com/post/aim;TreeNode current=root;TreeNode father=null;boolean isLeftNode=false;if(current==null)//根节点为空current=node;else{while(current!=null){father=current;if (current.value> aim){ isLeftNode=true;current = current.left;}else{current = current.right;isLeftNode=false;}}if(isLeftNode)father.left=node;else father.right=node;}}
其实有了插入方法，也就可以顺手写出创建BST的方法，直接上代码
public TreeNode build(int[] aim){TreeNode root=new TreeNode();root.value=http://www.kingceram.com/post/aim[0];this.root=root;for(int i=1;i
下面介绍BST最难的删除节点 。
删除的节点分三种情况
1、该节点为叶子节点 。这种情况直接删除即可
2、该节点拥有左孩子或者拥有右孩子（只拥有一个） 。这种情况删除该节点，并让节点与其为空的左孩子或者右孩子连接即可
3、该节点左孩子与右孩子都不为空 。这时候要考虑用什么节点替代该删除的节点，是左孩子还是右孩子 。
本文采用了利用该节点右孩子的最小值来替代该节点 。当然也可以用其左孩子的最大值来替代 。

文章插图
public void delete(int aim){TreeNode current=root;TreeNode father=null;boolean isLeftNode=false;while(current!=null&¤t.value!=aim){father=current;if (current.value > aim){isLeftNode=true;current = current.left;}else{current = current.right;isLeftNode=false;}}if(current.left==null&¤t.right==null){//情况1if(current==root)root=null;else if(isLeftNode)father.left=null;else father.right=null;}else if(current.left!=null&¤t.right==null){//情况2if(current==root)root=current.left;else if(isLeftNode)father.left=current.left;else father.right=current.left;}else if(current.left==null&¤t.right!=null){if(current==root)root=current.right;else if(isLeftNode)father.left=current.right;else father.right=current.right;}else if(current.left!=null&¤t.right!=null){//情况3*TreeNode next=getNextNode(current);//获取后继节点（右孩子上的最小节点）if(current==root)root=next;else if(isLeftNode)father.left=next;else father.right=next;next.left=current.left;}}public TreeNode getNextNode(TreeNode root){//获取其右孩子的最小节点TreeNode del=root;TreeNode current=root.right;TreeNode nextfather=null;TreeNode next=null;while(current!=null){nextfather=next;next=current;current=current.left;}if(next!=del.right){//该最小节点一定没有左孩子但是可能有右孩子 。如果有要将其右孩子变为被删除节点右孩子的左孩子，见下图示 。nextfather.left=next.right;next.right=del.right;}return next;}

• 上一页
• 1
• 2
• 下一页

• BST 二叉查找树｜搜索及插入操作
• 数据结构与算法_BST树_BST树的定义及删除操作
• dataStructure_交换排序:简单选择排序SelectionSort/堆
• 黄梅花树能栽在庭院里吗？
• 【课程设计】基于决策树算法的学生成绩分析
• 透彻_Prim普里姆算法和Dijkstra迪杰斯特拉算法_最小生成树和最短路径
• 无需电脑，只需要一台手机 手机连接linux树莓派,使用手机连接树莓派
• 个性化购买力分析及在搜索排序上应用
• 树莓派Pico入手
• 招财树生长周期？