二叉排序树的插入、遍历和删除

二叉排序树又称为二叉查找树BST。它或者是一颗空树，或者具有下列性质的二叉树： 1、如果左子树不为空，那么左子树上的所有结点值均小于它的根节点的值； 2、如果右子树不为空，那么右子树上的所有结点的值均大于它的根节点的值； 由于二叉树具有有序的特性，所以常考。

实现代码如下：

package tree; class Node //记得定义先 { public int data; public Node left; public Node right; public Node(int data) { this.data=data; this.right=null; this.left=null; } } public class treetest { private Node root; public treetest() { root=null; } public Node find( int key) { if(root==null) return -1; Node current=root; //start at root while(!(current.data==key)) { if(current.data<key) current=current.right; else current=current.left ; if(current==null) return -1; } return current.data; } public void insert(int data) { Node newnode = new Node(data); if(root==null) root=newnode; else { Node current =root; //start at root Node parent; while(true) //exits internally 寻找插入的位置 { parent=current; if(data<current.data) { current=current.left; if(current==null) { parent.left=newnode; return; } } else { current=current.right; if(current==null) {parent.right=newnode; return; } } } } } public void buildtree(int [] a) { for(int i=0;i<a.length;i++) { insert(a[i]); } }

遍历过程：

//中序遍历方法递归实现 会使所有的节点按关键字值升序被访问到 递归 //用递归方法遍历整棵树要用一个结点作为参数。初始化时是根 。 // 1 调用自身来遍历结点的左子树 2 访问这个结点 3 调用自身来遍历结点的右子树 // 不关心结点是否有关键字值，而是看这个结点是否有子节点 终止条件：结点为null //中序遍历是一个递增的有序序列 public void inOrder(Node localroot) { if(localroot!=null) { inOrder(localroot.left); System.out.print(localroot.data+" "); inOrder(localroot.right); } } public void inOrder() { this.inOrder(this.root); // } //先序遍历 递归 public void preOrder( Node localroot) { if(localroot!=null) { System.out.print(localroot.data+" "); preOrder(localroot.left ); preOrder(localroot.right); } } public void preOrder() { this.preOrder(this.root); } //后序遍历 递归 public void postOrder(Node localroot) { if(localroot!=null) { postOrder(localroot.left); postOrder(localroot.right); System.out.print(localroot.data+" "); } } public void postOrder() { this.postOrder(this.root); }

查找最小节点：走到左子树为空为止

//查找最小值 public Node minmum() { Node current,last=null; current=root; while(current!=null) { last=current; //remember node！ current=current.left; } return last; }

难点：删除结点~ 情况有三： 1、该节点是叶节点（没有子节点）； 2、该节点有一个子节点； 3、该节点有两个子节点。

//情况1 删除没有子节点的结点 为叶节点 public boolean delete(int key) { Node current=root; Node parent=root; boolean isleftchild =true; // find first while(current.data!=key) { parent =current; if(current.data>key) { isleftchild=true; current=current.left; } else { isleftchild=false; current=current.right ; } if(current==null) return false; //did't find } //找到之后，还需确认他是否真的没有子节点；若没有，还需要检查他是不是根 ,是，则直接置为null。 if(current.left ==null&&current.right==null) { if(current==root) //if root root=null; else if(isleftchild) parent.left=null; else parent.right=null; }

//情况2：删除只有一个子节点的结点 //这个结点只有两个连接：父节点和他唯一的子节点 //特殊情况：被删除的结点可能是根，他没有父节点，只是被合适的子树所替代 else if(current.right==null) { if(current==root) root=current.left; else if(isleftchild) //left child of parent parent.left =current.left; else parent.right=current.left; } else if(current.left==null) { if(current==root) root=current.right; else if(isleftchild) //left child of parent parent.left=current.right; else parent.right=current.right; else { 情况3

情况3不能简单用子树替代，但是记得在二叉搜索树里结点是按照升序的关键字值排列的。对每一个结点来说，比该结点关键字值高的结点是他的中序后继，可称为该节点的后继。 可以使用窍门：删除有两个子节点的节点，用他的中序后继来代替该节点。 （更麻烦的情况是，它的后继节点也有自己的子节点，后面讨论）

问题：如何查找后继节点？ 首先，找到初始节点的右子节点，他的关键字值一定会比初始节点大，然后转到初始节点的右子节点的左子节点那里，（如果有的话），然后找到这个左子节点的左子节点，以此类推，一直找下去。则这条路径上最后一个左子节点就是初始节点的后继，如下图。

这样做的目标是：找到比初始节点关键值大的节点集合中最小的一个节点。所以先向右找到右子节点，再找这颗子树的中值最小的节点，就顺着左子节点路径找下去。 如果初始节点的右子节点没有左子节点，那么这个右子节点本身就是后继。

//情况3：删除有两个子节点的结点 // 找后继节点 返回参数delnode的后继节点，此时已经判断过这个要删除的节点有两个子节点 // 当后继节点是delnode的右子节点时： 图 8.19 // 1把current从他的父节点的right删除，也可能是左，把这个字段指向后继； // 2 把current的左子节点移除来，插到后继的左边。 Node successor =getsuccessor(current); //connect parent of current to successor instead if(current==root) // if root root=successor; else if(isleftchild) //连接删除节点的父节点 parent.left=successor; else parent.right=successor; //connect successor to current's left child successor.left=current.left; } return true; //当后继节点是delnode右子节点的左后代 图8.20 //1、把后继父节点的leftchild字段置为successor右子节点 //2、把successor的rightchild字段置为要删除节点的右子节点 //3、把current从他父节点的rightchild字段删除，把这个字段置为successor //4、把current的左子节点从current移除，successor的leftchild字段置为current的左子节点 //1、2 由getsuccessor()完成 3、4与上面的情况代码一样 }

private Node getsuccessor( Node delnode) //获取后继节点 { Node successorparent =delnode; Node successor=delnode; Node current=delnode.right; while(current!=null) { successorparent =successor; successor=current; current=current.left; } if(successor!=delnode.right) //right child make connection { successorparent.left=successor.right; //rightchild to sp successor.right=delnode.right; //s to rightchild } return successor; }

主函数：

public static void main(String[] args) { treetest tree = new treetest(); int[] a={3,4,8,2,5,6}; tree.buildtree(a); int node =tree.find(9); System.out.println("find:" +node); int node2 =tree.minmum(); System.out.println(node2); //System.out.print("中序遍历： "); //tree.inOrder(); //System.out.println(); //System.out.print("先序遍历： "); //tree.preOrder(); //System.out.println(); //System.out.print("后序遍历： "); //tree.postOrder(); //System.out.println(); tree.displaytree();

这个竟然没看懂~

public void displaytree() { Stack gstack = new Stack(); gstack.push(root); int nblanks =32; boolean isrowempty=false; System.out.println("..........."); while(isrowempty==false) { Stack localstack = new Stack(); isrowempty=true; for(int j=0;j<nblanks;j++) { System.out.print(' '); } while(gstack.isEmpty()==false) { Node temp =(Node)gstack.pop(); if(temp!=null) { System.out.print(temp.data); localstack.push(temp.left); localstack.push(temp.right); if(temp.left!=null||temp.right!=null) isrowempty=false; } else { System.out.print("--"); localstack.push(null); localstack.push(null); } for(int j=0;j<nblanks*2-2;j++) { System.out.print(' '); } System.out.println(); nblanks/=2; while(localstack.isEmpty()==false) gstack.push(localstack.pop()); } System.out.println( "........."); } }

层序遍历：

//层序遍历 ：用队列实现 public void layerTranverse() { if(this.root==null) return; Queue<Node> q = new LinkedList<Node>(); q.add(this.root); while(!q.isEmpty()) //直到队列为空 { Node n =q.poll(); System.out.print(n.data); System.out.print(" "); if(n.left!=null) q.add(n.left ); if(n.right!=null) q.add(n.right); } }

如果已知先序遍历和中序遍历，那如何求后序遍历？？ 1、先确定树的根节点。 2、求解树的子树 3、不断递归，直到根节点左边和右边都为空时，则他已经为叶子节点。

package tree; //已知先序遍历、中序遍历，如何求后序遍历？ class Node { public Node left; public Node right; public int data; public Node(int data) { this.data=data; this.left=null; this.right=right; } } public class Binarytreetwo { private Node root; public Binarytreetwo() { this.root=null; } public void postOrder(Node localroot) { if(localroot!=null) { postOrder(localroot.left); postOrder(localroot.right); System.out.print(localroot.data+" "); } } public void postOrder() { this.postOrder(this.root); } public Node initTree(int[]preOrder,int start1,int end1,int[]inOrder,int start2,int end2) { if(start1>end1||start2>end2) return null; int rootdata=preOrder[start1]; Node head =new Node(rootdata); // //找到根节点所在的位置 int rootindex= findindexinarray(inOrder,rootdata,start2,end2); //构建左子树 int offset=rootindex-start2-1; Node left =initTree(preOrder,start1+1,offset+start1+1,inOrder,start2,start2+offset); //构建右子树 Node right=initTree(preOrder,offset+2+start1,end1,inOrder,rootindex+1,end2); head.left=left; head.right=right; return head; } public void initTree(int[] preOrder,int[] inOrder) { this.root=this.initTree(preOrder, 0, preOrder.length-1, inOrder, 0, inOrder.length-1); } public int findindexinarray(int[]a ,int x,int begin,int end) { for(int i=begin;i<=end;i++) { if(a[i]==x) return i; } return -1; } public static void main(String[] args) { Binarytreetwo tree= new Binarytreetwo(); int [] preOrder={1,2,4,8,9,5,10,3,6,7}; int[] inOrder={8,4,9,2,10,5,1,6,3,7}; tree.initTree(preOrder,inOrder); System.out.println("后序遍历为："); tree.postOrder(); } }

历时两天终于搞定了~