在这里，我没有采取map键值对的形式来表示二叉搜索树的节点，对于搜索树的节点我采取了含有三个引用型的变量分别指向父节点，左子节点，右子节点。
还包含有一个int类型的数据，当然在正式搜索二叉树中应该采用键值对的形式。以下为代码，其中还有一个bug
package Offer1; /* * 实现搜索二叉树，包括增删改查 * 1 定义搜索二叉树的节点数据结构 * 2 二叉树添加操作 * 3 二叉树更改操作 * 4 二叉树删除操作 */ public class SearchTree { Node head = null; private class Node{ int val; Node leftChild; Node rightChild; Node parent; Node(int val){ this.val=val; leftChild=null; rightChild=null; parent=null; } } //实现搜索二叉树的插入操作（出现错误，没有得到） public void add(int num){ Node cur = head; Node node = new Node(num); if(head==null) head=node; while(cur!=null){ if(num>cur.val) cur=cur.rightChild; else cur=cur.leftChild; } if(cur==null) cur=node; } //实现二叉树的插入 能够成功执行 public void insert (int num){ Node node = new Node(num); if(head==null){ head=node; return; } Node cur = head; while(true){ if(num>cur.val){ if(cur.rightChild==null){ cur.rightChild=node; node.parent=cur; return; } else cur = cur.rightChild; }else{ if(cur.leftChild==null){ cur.leftChild=node; node.parent=cur; return; } else cur = cur.leftChild; } } } /* * 实现搜索二叉树的删除操作 * 删除操作思路：1 首先判断要删除的节点是否有左右孩子，分三种情况 * 情况一：假如删除的节点为叶子节点 直接删除 * 情况二：假如删除的节点只有单支，只需该节点的父节点指向该节点孩子节点即可 * 情况三：假如该删除节点有双支，则首先找到该节点的后继， */ public void delete(int num){ Node node = search(num); Node parentnode = node.parent; int middlenum = 0; if(node.leftChild==null && node.rightChild==null){ if(parentnode.leftChild==node) parentnode.leftChild=null; else parentnode.rightChild=null; } else if(node.leftChild==null && node.rightChild!=null){ parentnode.rightChild=node.rightChild; } else if(node.rightChild==null && node.leftChild!=null){ parentnode.leftChild=node.leftChild; }else{ //交换该节点同其后继节点的值 Node successornode = successor(node); middlenum = node.val; node.val = successornode.val; successornode.val = middlenum; delete(successornode); /* * 采用如下的delete（middlenum)会报空指针错误java.lang.NullPointerException *at Offer1.SearchTree.search(SearchTree.java:111) *at Offer1.SearchTree.delete(SearchTree.java:75) *at Offer1.SearchTree.delete(SearchTree.java:97) *at Offer1.SearchTree.main(SearchTree.java:147) */ // delete(middlenum); } } public void delete(Node node){ Node parentnode = node.parent; if(parentnode.rightChild==node){ parentnode.rightChild=null; }else{ parentnode.leftChild=null; } } //搜索节点在二叉树中所处的位置 public Node search(int num){ Node node=head; while(node.val!=num){ if(num>node.val) node=node.rightChild; else node=node.leftChild; } return node; } //搜索某个节点的后继,某个节点的后继为比该节点大的最小值 public Node successor(Node node){ Node cur = node.rightChild; while(cur.leftChild!=null){ cur=cur.leftChild; } return cur; } //实现一个二叉树的遍历来走一个 public void preprint(Node node){ if(node==null) return; System.out.print(node.val); preprint(node.leftChild); preprint(node.rightChild); } public void print(){ preprint(head); } public static void main(String[] args) { SearchTree bst = new SearchTree(); bst.insert(3); bst.insert(2); bst.insert(5); bst.insert(4); bst.insert(6); bst.print(); System.out.println(); bst.delete(5); bst.print(); } }