首先查察下面一段代码，我指出了问题代码的地址，读者先本身思考一下这段代码会有什么问题。
这是用clone要领完整拷贝一个二项堆（BinomialHeap）布局的代码。二项堆中包括一个内部类BinomialHeapEntry，这个内部类的工具即二项堆中的每一个结点，除了包括结点对应的要害字外，还记录父节点parent，下一个兄弟结点sibling和第一个孩子结点child三个指针。二项堆的根表通过每棵二项树根节点的sibling指针链接。
cloneBinomialTree(BinomialHeapEntry root)要领递归拷贝一个根节点（含根节点）下的整个二项树，clone要领中遍历根表中每个树根结点，拷贝对应的二项树，然后将新的head指针赋给拷贝后的新堆。
public class BinomialHeap<E> implements Cloneable {
transient BinomialHeapEntry head; // 根表中的第一个元素
int size; // 整个二项堆的巨细（结点数）
private class BinomialHeapEntry {
E element;
transient BinomialHeapEntry parent = null, child = null,
sibling = null;
transient int degree = 0;
private BinomialHeapEntry(E element) {
this.element = element;
}
// 得到孩子结点的迭代器
private Iterable<BinomialHeapEntry> children {...}
}
@Override
public BinomialHeap<E> clone() {
// TODO Auto-generated method stub
BinomialHeap<E> clone;
try {
clone = (BinomialHeap<E>) super.clone();
} catch (CloneNotSupportedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
throw new InternalError();
}
BinomialHeapEntry newHead = null, curRoot = null;
// 遍历根表
Iterator<HeapEntry<E>> rootIt = this.roots().iterator();
while(rootIt.hasNext()){
BinomialHeapEntry root = (BinomialHeapEntry) rootIt.next();
// 拷贝根节点下的整棵二项树<br> <span style="color: #ff0000;">// BUG引入的处所</span>
BinomialHeapEntry newRoot = cloneBinomialTree(root);
if(curRoot == null){
newHead = newRoot;
} else {
curRoot.sibling = newRoot;
}
curRoot = newRoot;
}
clone.head = newHead;
return clone;
}
// 拷贝根节点（含根节点）下的整棵子树
private BinomialHeapEntry cloneBinomialTree(BinomialHeapEntry root){
BinomialHeapEntry newRoot = new BinomialHeapEntry(root.element());
BinomialHeapEntry curChild = null;
// 遍历根节点的所有孩子结点
Iterator<HeapEntry<E>> childIt = root.children().iterator();
while(childIt.hasNext()){
BinomialHeapEntry child = (BinomialHeapEntry) childIt.next();
// 递归拷贝孩子节点下的子树
BinomialHeapEntry newChild = cloneBinomialTree(child);
newChild.parent = newRoot;
if(curChild == null){
newRoot.child = newChild;
} else {
curChild.sibling = newChild;
}
curChild = newChild;
}
newRoot.degree = root.degree;
return newRoot;
}
}
先回首一下Java内部类的一些常识，非静态的Java内部类作为外部类的一个成员，只能通过外部类的工具来会见，要建设一个内部类工具，也需要通过外部类工具来建设，即：outerObject.new InnerClass()。这时，所建设的内部类工具会发生名称为this$0的一个字段，该字段生存的是建设这个内部类工具的外部类工具引用，即适才的outerObject。这个引用使得一个内部类工具可以自由的会见外部类的成员变量。
在回首上面二项堆拷贝的代码，在挪用cloneBinomialTree要领拷贝二项树时，我们试图通过new BinomialHeapEntry()来建设一个新的结点，把新的结点作为新二项堆中的结点，但事实上我们实际挪用的是this.new BinomialHeapEntry()，也就是说建设的新结点中，this$0是指向老的二项堆(this)而不是新的正在拷贝的二项堆(clone)。这使得我们获得拷贝的新二项堆之后，通过新二项堆的任一结点会见和修改整个堆的信息时，修改的都是老的二项堆，最后发生了一系列奇怪的功效。
要想修复这个bug很简朴，把clone要领中的BinomialHeapEntry newRoot = cloneBinomialTree(root)即赤色注释下的语句，修改为BinomialHeapEntry newRoot = clone.cloneBinomialTree(root)。这样cloneBinomialTree要领中建设的结点都是通过clone工具建设，问题也就办理了。
#p#分页标题#e#
问题其实较量简朴，这确实是今后在编程中值得留意的一点：拷贝内部类工具时思量清楚拷贝后的工具this$0字段是否指向的是你但愿指向的外部类工具。
查察本栏目
