java - 将节点连接到树中的下一个兄弟节点

Question

我试图将树中的所有节点连接到它们的右兄弟。

例如，root.nextSibling 应该为空。如果 root 有 2 个孩子“a”和“b”，a.nextSibling 应该是“b”并且 b 应该是 null。

我所做的是按级别顺序遍历树，同时为该级别中的所有节点设置 nextSibling 指针，然后再向下移动到下一个级别。

请查看代码并让我知道是否有更好的实现方式？

\* In class BinTree.java *\
public void connectSiblings() {
    Queue q = new LinkedList(); 
    if(root!= null) {
        q.add(root);
    }        
    while(!q.isEmpty()) {
       Object[] a = q.toArray();
       for(int i = 0; i < a.length; i++) {
           BinTreeNode node = (BinTreeNode)q.remove();
           if(i == a.length-1) {
               ((BinTreeNode) a[i]).nextSibling = null;
           }
           else {
               ((BinTreeNode) a[i]).nextSibling = (BinTreeNode) a[i+1];
           } 
           if(node.visitLeftChild() != null) {
               q.add(node.visitLeftChild());
           }
           if(node.visitRightChild() != null) {
               q.add(node.visitRightChild());
           }             
       }     
    }
}



\* In class BinTreeNode.java *\
public BinTreeNode visitLeftChild() {
   if(this.leftChild != null) {
       return this.leftChild;
   } 
   return null;
}

\* In class BinTreeNode.java *\
public BinTreeNode visitRightChild() {
    if(this.rightChild != null) {
        return this.rightChild;
    }
    return null;
}

Answer 1

这更容易通过 BinTreeNode 具有对其 Parent 的引用来实现。然后 Siblings 是 Parent 的 Children except this，特殊情况 Root 没有兄弟姐妹很容易由 Parent 确定null。