java - 在 Java 中镜像二叉树

Question

我目前正在高中学习 Java 数据结构类(class)，我需要镜像树的帮助。下面我有所有有用的代码和两种解决mirrorImage方法的方法，这两种方法总是由于某种未知的原因返回null。我的主要问题是，为什么这些方法不起作用？我该如何解决它？我认为这可能与我正在使用的树有关，因为插入方法无法正常工作。

提前致谢，这是我第一次在 Stack Overflow 上发帖，我很期待!

注意:这个方法不是我的作业，我只是为了自己好

public class TreeLab {

  public static void main(String[] args)
  {
    String s = "XCOMPUTERSCIENCE";

    TreeNode root = new TreeNode("" + s.charAt(1), null, null);

    for(int pos = 2; pos < s.length(); pos++)
        insert(root, "" + s.charAt(pos), pos, (int)(1 + Math.log(pos) / 
        Math.log(2)));

    insert(root, "B", 17, 5); 
    insert(root, "A", 18, 5); 
    insert(root, "C", 37, 6); //B's right child

    // display the tree sideways
    display(root, 0);

    System.out.println("\n\nMirror Image: ");
    display(root.mirrorImage(), 0);
  }


  public static void insert(TreeNode t, String s, int pos, int level) {

    TreeNode p = t;
    for(int k = level - 2; k > 0; k--)
        if((pos & (1 << k)) == 0) 
            p = p.getLeft();
        else                        
            p = p.getRight();

    if((pos & 1) == 0)
        p.setLeft(new TreeNode(s, null, null));
    else
        p.setRight(new TreeNode(s, null, null));
  } // end of insert


  //postcondition: display the tree sideways
  public static void display(TreeNode t, int level) {
    if(t == null)
        return;
    display(t.getRight(), level + 1); //recurse right

    for(int k = 0; k < level; k++)
        System.out.print("\t");
    System.out.println(t.getValue());

    display(t.getLeft(), level + 1); //recurse left
  }  // end of display

  public static TreeNode mirrorImage (TreeNode t) {

    //way 1
    /*
    if (t == null)
        return null;

    TreeNode right = t.getRight();
    TreeNode left = t.getLeft();

    t.setLeft(mirrorImage(right));
    t.setRight(mirrorImage(left));

    return t;
    */      

    //way 2
    /*
    if (t == null)
        return null;
    else
        return new TreeNode (t.getValue(), mirrorImage(t.getRight()), 
      mirrorImage(t.getLeft()));
    */      

    return null; //only here to help complile
  }
}//end of TreeLab

//TreeNode class

class TreeNode {

  private Object value; 
  private TreeNode left, right;

  public TreeNode(Object initValue) { 
    value = initValue; 
    left = null; 
    right = null; 
  }

  public TreeNode mirrorImage() {
    return null;
  }

  public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) { 
    value = initValue; 
    left = initLeft; 
    right = initRight; 
  }

  public Object getValue() { 
    return value; 
  }

  public TreeNode getLeft()  { 
    return left; 
  }

  public TreeNode getRight()  { 
    return right; 
  }

  public void setValue(Object theNewValue)  { 
    value = theNewValue; 
  }

  public void setLeft(TreeNode theNewLeft)  { 
    left = theNewLeft;
  }

  public void setRight(TreeNode theNewRight) { 
    right = theNewRight;
  }
}

Answer 1

在您的 mirrorImage 方法中，您应该创建作为参数获得的节点的新副本(现在您只需重新分配其左右属性)并递归地复制其子节点:

public static TreeNode mirrorImage(TreeNode t) {
    if (t == null) {
        return null;
    }
    return new TreeNode(
        t.getValue(),
        mirrorImage(t.getLeft()),
        mirrorImage(t.getRight())
    );
}