上数据结构及算法 | Java数据结构——BST二叉搜索树( 二 ) _bst

2、删除元素的三种情况：该节点没有孩子节点、有一个孩子节点和有两个孩子节点，因为假如待删除节点还有孩子，我们不能把该节点及该节点的所有孩子一起删除了，而是只能删除这个节点的这一个元素，所以我们需要区分不同情况来不同的处理。
非递归实现如下：
public void non_remove(T data){if(this.root == null){return;}// 1. 先搜索BST树，找到待删除的节点BSTNode node = this.root;BSTNode parent = null;//记录当前父节点while(node != data){if(node.getData().compareTo(data) > 0){parent = node;node = node.getLeft();}else if(node.getData().compareTo(data) < 0){parent = node;node = node.getRight();}else{break;}}if(node == null){//表示BST树中没有值为data的节点return;}// 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，直接删除前驱if(node.getLeft() != null && node.getRight() != null){//两个孩子节点BSTNode old = node;parent = node;node = parent.getLeft();//node记录父节点的左孩子节点while(node.getRight() != null) {//node的右孩子节点不为空parent = node;node = node.getRight();//继续找右孩子节点}//将找到的前驱结点放在父节点的位置，删除前驱结点old.setData(node.getData());}// 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）BSTNode child = node.getLeft();if(child == null){//左边为空时，child就指向右孩子嘛child = node.getRight();}if(parent == null){this.root = child;//当前父节点为空，其root节点直接指向他的孩子}}
3、二叉搜索树查找元素
其实查找也就是相当于遍历了，而遍历在前面的增加删除操作中均有涉及；
设待查找元素为data，找到返回true，找不到返回false，查找过程如下：
（1）从根节点开始比较，根节点为空，找不到元素返回false；
（2）比根节点小的话，与左孩子进行比较（小于父节点就向左比）；
（3）比根节点大的话，与右孩子进行比较（大于父节点就向右比）；
（4）如果与根节点大小相同的话就是找到这个元素了吖，返回true嘛！
非递归实现如下：
public boolean non_query(T data){BSTNode node = this.root;while(node != data) {if (node.getData().compareTo(data) > 0) {node = node.getLeft();} else if (node.getData().compareTo(data) < 0) {node = node.getRight();} else {return true; //找到返回true}}return false;//找不到data值，返回false}
三、四种遍历方式
4、前序遍历
前序遍历就是先访问父节点，再访问左孩子、再访问右孩子；
如上图中的数值前序遍历的输出顺序就是：58 23 12 18 35 47 82 69 74 87 95
递归实现：
/** 前序遍历BST树的API接口*/public void preOrder(){System.out.print("前序遍历：");preOrder(this.root);System.out.println();}/*** 前序遍历BST树的递归操作 VLR*/private void preOrder(BSTNode root) {if(root != null){System.out.print(root.getData() + " ");preOrder(root.getLeft());preOrder(root.getRight());}}
5、中序遍历
中序遍历就是先访问左孩子，再访问父节点，再访问右孩子；
上图中的数值中序遍历的输出顺序就是：12 18 23 35 47 58 69 74 82 87 95
可以发现，中序遍历之后数是按照从小到大的顺序排列的。
递归实现：
//中序遍历public void inOrder(){System.out.print("中序遍历：");inOrder(this.root);System.out.println();}public void inOrder(BSTNode root){if(root != null){inOrder(root.getLeft());System.out.print(root.getData() + "");inOrder(root.getRight());}}
6、后序遍历
后序遍历就是先访问左孩子，再访问右孩子，再访问父节点；
上图中的数值经过后序遍历输出是：18 12 47 35 23 74 69 95 87 82 58
递归实现：

上 数据结构及算法 | Java数据结构——BST二叉搜索树( 二 )

上数据结构及算法 | Java数据结构——BST二叉搜索树( 二 )