二叉树查找树

定义

首先得是一棵二叉树；左子树上的所有节点值均小于根节点值；右子树上的所有节点值均不小于根节点值；左右子树也满足上述条件；

特点：

中序遍历二叉查找树能输出一组有序的节点序列；其中，中序遍历运行时间为Θ(n)。

二叉排序树可以用来进行对数组进行排序（首先把每个节点插入到而叉查找树中构造完整二叉查找树，然后进行中序遍历即可得到有序序列），插入单个节点时间为Θ(lgn),n个节点用时Θ(nlgn),所以二叉排序树排序效率为Θ(nlgn)。

详解

对于二叉查找树，需要掌握一些基本操作（插入、查找、删除）！

1、插入

一定是作为叶子节点插入到二叉树

若当前的二叉查找树为空，则插入的元素为根节点若插入元素值小于根节点值，则将元素插入到左子树中若插入元素值不小于根节点值，则将元素插入到右子树中。

图解：（来自：http://www.cnblogs.com/zhoutaotao/p/4096237.html）

/** * 插入元素 * 若当前的二叉查找树为空，则插入的元素为根节点,插入元素值小于根节点值，则将元素插入到左子树 * 若插入元素值不小于根节点值，则将元素插入到右子树中。 * @param value * @return 插入成功返回TRUE，如该元素已存在则插入失败，返回FALSE */ public boolean insertTreeNode(int value){ TreeNode<Integer> parentNode=null; TreeNode<Integer> newNode=new TreeNode<Integer>(new Integer(value),null,null,null); TreeNode<Integer> currentNode=root; //若当前的二叉查找树为空，则插入的元素为根节点 if(currentNode==null){ root=newNode; return true; } //找到插入位置！ while(currentNode!=null){ parentNode=currentNode; if(value<currentNode.getValue()) currentNode=currentNode.getLeftChild(); else if(value>currentNode.getValue()) currentNode=currentNode.getRightChild(); else return false; //树中存在匹配关键字的节点 } //将新节点插入到指定节点的指定位置（左孩子或者右孩子） if(value<parentNode.getValue()){ parentNode.setLeftChild(newNode); newNode.setParent(parentNode); }else{ parentNode.setRightChild(newNode); newNode.setParent(parentNode); } return true; }

2、查找

从根节点开始查找，若大于根节点，则从进入右子树，反之进入左子树。

代码中顺便捎带查找二叉树中最大最小值：

/** * 查询 * 给定关键字匹配树节点 * @param value * @return 若匹配返回给定关键字的树结点，否则返回null */ public TreeNode<Integer> searchByValue(int value){ TreeNode<Integer> currentNode=root; while(currentNode!=null){ if(currentNode.getValue()!=value){ if(value<currentNode.getValue()) currentNode=currentNode.getLeftChild(); else currentNode=currentNode.getRightChild(); }else{ return currentNode; } } return null; } /** * 获取最小关键字节点 * @param node * @return 最小关键字节点 * @throws Exception */ public TreeNode<Integer> getMinValueNode(TreeNode<Integer> node) throws Exception{ if(node==null){ throw new Exception("空树!"); } TreeNode<Integer> currentNode=node; while(currentNode.getLeftChild()!=null){ currentNode=currentNode.getLeftChild(); } return currentNode; } /** * 获取最大关键字节点 * @param node * @return 最大关键字节点 * @throws Exception */ public TreeNode<Integer> getMaxValueNode(TreeNode<Integer> node) throws Exception{ if(node==null){ throw new Exception("空树!"); } TreeNode<Integer> currentNode=node; while(currentNode.getRightChild()!=null){ currentNode=currentNode.getRightChild(); } return currentNode; }

3、删除

分3中情况处理：假设待删除节点为P http://blog.csdn.net/zyj8170/article/details/7045226/

结点P为叶子节点，没有左右子树，则直接删除结点P只有一个子树（左子树或者右子树），则用子树取代原节点P结点P有两个子树，则用右子树最小的节点（后继节点）取代节点P，再递归删除此最小节点（或者到其左子树中最大节点（前驱）取代节点P，再删除前驱节点）

1. 获取指定节点的后继节点：

/** * 获取指定节点的后继节点 * 后继节点：左子树中的最小值 * @param node * @return * @throws Exception */ public TreeNode<Integer> getSuccessorNode(TreeNode<Integer> node) throws Exception{ TreeNode<Integer> currentNode=node; if(node==null) return null; // 若该结点的右子树不为空，则其后继结点就是右子树中的最小关键字结点 if(currentNode.getRightChild()!=null){ return getMinValueNode(currentNode.getRightChild()); } //右子树为空 TreeNode<Integer> parentNode= currentNode.getParent(); //终止条件！！！如果当前节点为父节点的右子树，则还需要继续回退！ while(parentNode!=null&&currentNode==parentNode.getRightChild()){ currentNode=parentNode; parentNode=parentNode.getParent(); } return parentNode; }

2. 删除指定值的节点：

** * 根据值删除某个节点 * 主要分3种情况！！ * @param value * @throws Exception */ public void deleteByValue(int value) throws Exception{ TreeNode<Integer> currentNode=root; //根据节点值得到节点信息 TreeNode<Integer> targetNode=searchByValue(value); if(currentNode==null){ //空树 return ; } if(targetNode==null){ //目标节点不存在 return ; }else{ // 该结点既无左孩子结点，也无右孩子结点 if(targetNode.getLeftChild()==null&&targetNode.getRightChild()==null){ TreeNode<Integer> parentNode=targetNode.getParent(); if(targetNode==parentNode.getLeftChild()){ parentNode.setLeftChild(null); }else if(targetNode==parentNode.getRightChild()){ parentNode.setRightChild(null); }else{ targetNode=null; //待删除节点为根节点！ } return ; } // 该结点左孩子结点非空，右孩子结点为空 if(targetNode.getLeftChild()!=null&&targetNode.getRightChild()==null){ TreeNode<Integer> parentNode=targetNode.getParent(); if(targetNode==parentNode.getLeftChild()){ parentNode.setLeftChild(targetNode.getLeftChild()); targetNode.getRightChild().setParent(parentNode); }else{ parentNode.setRightChild(targetNode.getLeftChild()); //targetNode.getRightChild().setParent(parentNode); } return ; } //该结点左孩子结点为空，右孩子结点非空 if(targetNode.getLeftChild()==null&&targetNode.getRightChild()!=null){ TreeNode<Integer> parentNode=targetNode.getParent(); if(targetNode==parentNode.getRightChild()){ parentNode.setLeftChild(targetNode.getRightChild()); targetNode.getRightChild().setParent(parentNode); }else{ parentNode.setRightChild(targetNode.getRightChild()); targetNode.getRightChild().setParent(parentNode); } return ; } // 该结点左右孩子结点均非空，则删除该结点的后继结点，并用该后继结点取代该结点 TreeNode<Integer> successorNode=getSuccessorNode(targetNode); deleteByValue(successorNode.getValue()); targetNode.setValue(successorNode.getValue()); } }

补充 代码

package xianggen.tree; /** * 树节点类，泛型 * TreeNode.java * @author xianggen * @date 2016年8月11日 下午2:37:23 * @param <E> */ public class TreeNode<E> { private E value; private TreeNode<E> leftChild; private TreeNode<E> rightChild; private TreeNode<E> parent; /** * 无参构造函数 */ public TreeNode(){ } /** * 带value构造函数 * @param value */ public TreeNode(E value){ this.value=value; leftChild=null; rightChild=null; } public TreeNode(E value,TreeNode<E> leftChild,TreeNode<E> rightChild,TreeNode<E> parent){ this.value=value; this.leftChild=leftChild; this.rightChild=rightChild; this.parent=parent; } /** * 四个参数的set和get方法 * @return */ public E getValue() { return value; } public void setValue(E value) { this.value = value; } public TreeNode<E> getLeftChild() { return leftChild; } public void setLeftChild(TreeNode<E> leftChild) { this.leftChild = leftChild; } public TreeNode<E> getRightChild() { return rightChild; } public void setRightChild(TreeNode<E> rightChild) { this.rightChild = rightChild; } public TreeNode<E> getParent() { return parent; } public void setParent(TreeNode<E> parent) { this.parent = parent; } }

测试main

public static void main(String[] args) { BinarySearchTree bst=new BinarySearchTree(); bst.insertTreeNode(5); bst.insertTreeNode(8); bst.insertTreeNode(3); bst.insertTreeNode(6); bst.insertTreeNode(2); bst.insertTreeNode(4); bst.insertTreeNode(7); try { System.out.println(bst.getMaxValueNode(bst.getRoot()).getValue()); System.out.println(bst.getMinValueNode(bst.getRoot()).getValue()); System.out.println(bst.getSuccessorNode(bst.getRoot()).getValue()); bst.deleteByValue(5); System.out.println(bst.getRoot().getValue()); } catch (Exception e) { e.printStackTrace(); } }