讲解一下 二叉排序树的查找操作： 1.若二叉排序树为空，查找失败，返回空指针。 2.若查找的值等于当前根节点的值，返回当前节点。 查找的值大于当前的根节点，递归返回当前根节点的右子树 小于就返回从根节点的左子树。 算法：
void Search(BSTree T,Key key){ if(!T || key==T.data)return T; if(key<T.data)return Search(T.left,key); else if(T>T.data)return Search(T.right,key); }插入操作： 1.若BST为空，则待插入节点S作为根插入到空树种。 2.若二叉排序树非空，则将key与根节点的关键字T.data进行比较。 key<T.data,递归插入左子树 否则，递归插入右子树
void InsertBst(BSTree &T,Key key){ if(!T){ S = new BSTNode; s->data = e; s->left = s->right = null; T = S; else if(e.key<T.data) InsertBst(T->left,key); else if(e.key>T.data){ InsertBst(T->right,key); } }二叉排序树的删除 有这么几种情况 1.缺右子树用左孩子填补 2.缺左子树用右孩子填补 3.在左子树上找中序最后一个节点填补，待删除的左右子树都存在 或者也能在待删除节点的右子树中找中序遍历的第一个节点填补，待删除的左右子树都存在。
附带上代码
// 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin(Node node) { if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜索树中删除键为key的节点 public V remove(K key) { Node node = getNode(root, key); if (node != null) { root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key) { if (node == null) return null; if (key.compareTo(node.key) < 0) { node.left = remove(node.left, key); return node; } else if (key.compareTo(node.key) > 0) { node.right = remove(node.right, key); return node; } else { // key.compareTo(node.key) == 0 // 待删除节点左子树为空的情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待删除节点右子树为空的情况 if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }liuyubobobo老师那学习的BST
package com.hnist.lzn.AVLTree; public class BST<K extends Comparable<K>, V> { private class Node { public K key; public V value; public Node left, right; public Node(K key, V value) { this.key = key; this.value = value; left = null; right = null; } } private Node root; private int size; public BST() { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } // 向二分搜索树中添加新的元素(key, value) public void add(K key, V value) { root = add(root, key, value); } // 向以node为根的二分搜索树中插入元素(key, value)，递归算法 // 返回插入新节点后二分搜索树的根 private Node add(Node node, K key, V value) { if (node == null) { size++; return new Node(key, value); } if (key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if (key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; return node; } // 返回以node为根节点的二分搜索树中，key所在的节点 private Node getNode(Node node, K key) { if (node == null) return null; if (key.equals(node.key)) return node; else if (key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); } public boolean contains(K key) { return getNode(root, key) != null; } public V get(K key) { Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue) { Node node = getNode(root, key); if (node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node) { if (node.left == null) return node; return minimum(node.left); } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin(Node node) { if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜索树中删除键为key的节点 public V remove(K key) { Node node = getNode(root, key); if (node != null) { root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key) { if (node == null) return null; if (key.compareTo(node.key) < 0) { node.left = remove(node.left, key); return node; } else if (key.compareTo(node.key) > 0) { node.right = remove(node.right, key); return node; } else { // key.compareTo(node.key) == 0 // 待删除节点左子树为空的情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待删除节点右子树为空的情况 if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } }