arentNode = parentNode.getLchild();
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? parentNode = parentNode.getRchild();? //向右查找父节点
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }? ? ? ? ? ?
? ? ? ? }
? ? ? ? return null;
? ? }
? ?
? ? /**
? ? * 得到结点node的直接前趋
? ? * a.该节点左子树不为空：其前驱节点为其左子树的最大元素
? ? * b.该节点左子树为空: 其前驱节点为其祖先节点(递归)，且该祖先节点的右孩子也为其祖先节点
? ? *? (就是一直往其parent找，出现左拐后的那个祖先节点)
? ? */
? ? public TreeNode getPrecessor(TreeNode root,TreeNode node){
? ? ? ? if(node == null){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? //a.该节点左子树不为空：其前驱节点为其左子树的最大元素
? ? ? ? if(node.getLchild() != null){
? ? ? ? ? ? return getMaxData(node.getLchild());
? ? ? ? }else{? //b.该节点左子树为空: 其前驱节点为其祖先节点(递归)? ? ? ?
? ? ? ? ? ? TreeNode parentNode = getParentNode(root, node.getData());
? ? ? ? ? ? while(parentNode != null && node == parentNode.getLchild()){
? ? ? ? ? ? ? ? node = parentNode;
? ? ? ? ? ? ? ? parentNode = getParentNode(root, parentNode.getData());
? ? ? ? ? ? }
? ? ? ? ? ? return parentNode;
? ? ? ? }
? ? }
? ?
? ? /**
? ? * 得到结点node的直接后继(后继节点就是比要删除的节点的关键值要大的节点集合中的最小值)
? ? * a.该节点右子树不为空，其后继节点为其右子树的最小元素
? ? * b.该节点右子树为空???则其后继节点为其祖先节点(递归)，且此祖先节点的左孩子也是该节点的祖先节点，
? ? *? 就是说一直往上找其祖先节点，直到出现右拐后的那个祖先节点：
? ? */
? ? public TreeNode getSuccessor(TreeNode root,TreeNode node){
? ? ? ? if(node == null){
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? //a.该节点右子树不为空，其后继节点为其右子树的最小元素
? ? ? ? if(node.getRchild() != null){
? ? ? ? ? ? return getMinData(node.getRchild());
? ? ? ? }else{? //b.该节点右子树为空，则其后继节点为其最高祖先节点(递归)? ? ? ?
? ? ? ? ? ? TreeNode parentNode = getParentNode(root, node.getData());
? ? ? ? ? ? while(parentNode != null && node == parentNode.getRchild()){
? ? ? ? ? ? ? ? node = parentNode;
? ? ? ? ? ? ? ? parentNode = getParentNode(root, parentNode.getData());
? ? ? ? ? ? }
? ? ? ? ? ? return parentNode;
? ? ? ? }
? ? }
? ?
? ? /**
? ? * 删除数据域为data的结点
? ? * 按三种情况处理：
? ? * a.如果被删除结点z是叶子节点，则直接删除，不会破坏二叉查找树的性质
? ? * b.如果节点z只有一颗左子树或右子树，则让z的子树成为z父节点的子树，代替z的位置
? ? * c.若结点z有左、右两颗子树，则令z的直接后继（或直接前驱）替代z，
? ? *? 然后从二叉查找树中删去这个直接后继（或直接前驱）,这样就转换为第一或第二种情况
? ? * @param node 二叉查找树的根节点
? ? * @param data 需要删除的结点的数据域
? ? * @return
? ? */
? ? public boolean deleteNode(TreeNode node, Integer data){
? ? ? ? if(node == null){ //树为空
? ? ? ? ? ? throw new RuntimeException("树为空！");
? ? ? ? }
? ? ? ? TreeNode delNode= searchNode(node, data);? //搜索需要删除的结点
? ? ? ? TreeNode parent = null;
? ? ? ? if(delNode == null){? //如果树中不存在要删除的关键字
? ? ? ? ? ? throw new RuntimeException("树中不存在要删除的关键字！");
? ? ? ? }else{
? ? ? ? ? ? parent = getParentNode(node,data);? //得到删除节点的直接父节点
? ? ? ? ? ? //a.如果被删除结点z是叶子节点，则直接删除，不会破坏二叉查找树的性质? ? ? ?
? ? ? ? ? ? if(delNode.getLchild()==null && delNode.getRchild()==null){? ?
? ? ? ? ? ? ? ? if(delNode==parent.getLchild()){? //被删除节点为其父节点的左孩子
? ? ? ? ? ? ? ? ? ? parent.setLchild(null);
? ? ? ? ? ? ? ? }else{? ? //被删除节点为其父节点的右孩子
? ? ? ? ? ? ? ? ? ? parent.setRchild(null);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? //b1.如果节点z只有一颗左子树，则让z的子树成为z父节点的子树，代替z的位置
? ? ? ? ? ? if(delNode.getLchild()!=null && delNode.getRchild()==null){
? ? ? ? ? ? ? ? if(delNode==parent.getLchild()){ //被删除节点为其父节点的左孩子
? ? ? ? ? ? ? ? ? ? parent.setLchild(delNode.getLchild());? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? }else{ //被删除节点为其父节点的右孩子
? ? ? ? ? ? ? ? ? ? parent.setRchild(delNode.getLchild());
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? delNode.setLchild(null); //设置被删除结点的左孩子为null
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? //b2.如果节点z只有一颗右子树，则让z的子树成为z父节点的子树，代替z的位置
? ? ? ? ? ? if(delNode.getLchild()==null && delNode.getRchild()!=null){
? ? ? ? ? ? ? ? if(delNode==parent.getLchild()){ //被删除节点为其父节点的左孩子
? ? ? ? ? ? ? ? ? ? parent.setLchild(delNode.getRchild());
? ? ? ? ? ? ? ? }else{? //被删除节点为其父节点的右孩子
? ? ? ? ? ? ? ? ? ? parent.setRchild(delNo |