学习二叉树（2）搜索二叉树

​ 

    二叉搜索树的查找操作Find、

/* 　查找某个节点，我们必须从根节点开始遍历。 　　①、查找值比当前节点值大，则搜索右子树； 　　②、查找值等于当前节点值，停止搜索（终止条件）； 　　③、查找值小于当前节点值，则搜索左子树； */ public TreeNode Find(int data,TreeNode bst){ if (bst==null) return null;// 查找失败 if (data>bst.data) return Find(data,bst.right); else if (data<bst.data) return Find(data,bst.left); else return Find(data,bst.left); } //查找节点 public TreeNode find(int key,TreeNode root) { TreeNode current = root; while(current != null){ if(current.data > key){//当前值比查找值大，搜索左子树 current = current.left; }else if(current.data < key){//当前值比查找值小，搜索右子树 current = current.right; }else{ return current; } } return null;//遍历完整个树没找到，返回null }

················ 

// 找到最小值 public TreeNode findMin(TreeNode bt) { if (bt == null) { return null; } else if (bt.left == null) { return bt; } else { return findMin(bt.left); } } // 找到最大值 public TreeNode findMax(TreeNode bt) { if (bt == null) { return null; } else if (bt.right == null) { return bt; } else { return findMax(bt.right); } } //非递归 public TreeNode findMax2(TreeNode root){ if (root==null) return null; if (root!=null){ while (root.right!=null){ root=root.right; } } return root; }

二叉搜索树的插入，保证插入完成后仍然是二叉搜索树

  要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。

public boolean insert(int data,TreeNode root){ // 若原树为空，生成并返回一个结点的二叉搜索树 if (root==null) { TreeNode bs= new TreeNode(); bs.data=data; bs.left=bs.right=null; return true; } if (data>root.data) root.right = insert(data,root.right); else if (data<root.data) root.left= insert(data,root.left); else return false; } //插入节点 public boolean insert2(int data,TreeNode root) { TreeNode newNode = new TreeNode(data,null,null); if(root == null){//当前树为空树，没有任何节点 root = newNode; return true; }else{ TreeNode current = root; TreeNode parentNode = null; while(current != null){ parentNode = current; if(current.data > data){//当前值比插入值大，搜索左子节点 current = current.left; if(current == null){//左子节点为空，直接将新值插入到该节点 parentNode.left = newNode; return true; } }else{ current = current.right; if(current == null){//右子节点为空，直接将新值插入到该节点 parentNode.right = newNode; return true; } } } } return false; }

 二叉搜索树的删除

1.如果要删除的是叶节点：直接删除，并修改其父节点指针----置为null   35

2.要删除的结点只有一个孩子结点，将其父节点的指针指向要删除结点的孩子结点   33

3.要删除的结点有左右两颗子树，用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素  41  取 35

    

public TreeNode delete(int data,TreeNode current){ TreeNode temp=null; if (current==null) { System.out.println("树为空，无法删除"); return null;} //树为空 无法删除 if (data>current.data) current.right=delete(data,current.right); //右子树递归删除 else if (data<current.data) current.left=delete(data,current.left); //左子树递归删除 else// 找到删除的结点 { if (current.left!=null&¤t.right!=null){ //被删除的结点 有左右两个孩子 temp =current; //被删除结点 TreeNode temp1=findMin(current.right); //右子树中找最小的元素填充，删除原来的结点 current.data=temp1.data; current.right=delete(data,current.right);// 再删除结点的右子树中最小的元素 }else { // 被删除结点有一个或无子节点 temp =current; //被删除结点 if (current.left==null) //有 右孩子或无子节点 current=current.right ; else if (current.right==null)//有 左孩子或无子节点 current=current.left; } } return temp; //返回被删除结点 }

https://www.cnblogs.com/ysocean/p/8032642.html#_label2

另一类删除 ，来源于该篇博客

  

public boolean delete(int key) { Node current = root; Node parent = root; boolean isLeftChild = false; //查找删除值，找不到直接返回false while(current.data != key){ parent = current; if(current.data > key){ isLeftChild = true; current = current.leftChild; }else{ isLeftChild = false; current = current.rightChild; } if(current == null){ return false; } } //如果当前节点没有子节点 if(current.leftChild == null && current.rightChild == null){ if(current == root){ root = null; }else if(isLeftChild){ parent.leftChild = null; }else{ parent.rightChild = null; } return true; } //当前节点有一个子节点 if(current.leftChild == null && current.rightChild != null){ if(current == root){ root = current.rightChild; }else if(isLeftChild){ parent.leftChild = current.rightChild; }else{ parent.rightChild = current.rightChild; } return true; }else{ //current.leftChild != null && current.rightChild == null if(current == root){ root = current.leftChild; }else if(isLeftChild){ parent.leftChild = current.leftChild; }else{ parent.rightChild = current.leftChild; } return true; } public Node getSuccessor(Node delNode){ Node successorParent = delNode; Node successor = delNode; Node current = delNode.rightChild; while(current != null){ successorParent = successor; successor = current; current = current.leftChild; } //将后继节点替换删除节点 if(successor != delNode.rightChild){ successorParent.leftChild = successor.rightChild; successor.rightChild = delNode.rightChild; } return successor; }