方法二叉树

Question

我不得不做一些关于BinaryTree（没有搜索二叉树）的方法。我不能够做3种方法：反射（反映树，我的代码不工作，因为只反映树的一部分），剪切和切割2。代码是：

public class BinaryTree { 

    protected class Node { 

     Integer element; 
     Node left; 
     Node right; 

     Node(int element) { 
      this.element = element; 
      left = right = null; 
     } 

     Node(int element, Node left, Node right) { 
      this.element = element; 
      this.left = left; 
      this.right = right; 
     } 

      // is leaf? 
     boolean isLeaf() { 
      return left == null && right == null; 
     } 
    } 

    protected Node root; 

    public BinaryTree() { 
     root = null; 
    } 

    /* doesn't work */ 
    public void reflect() { 
     if (root == null) 
      return; 
     reflect(root); 
    } 

    protected void reflect(Node node) { 
     reflect(node.left); 
     reflect(node.right); 
     Node temp = new Node(node.left.element); 
     node.left.element = node.right.element; 
     node.right.element = temp.element; 
    } 

    /* this method had to trim the tree at level h, 
     if h=0, it cut the whole tree. It change the original tree */ 
    /* doesn't work */ 
    public void cut(int h) { 

    } 

    /* i can change parameters */ 
    protected void cut(Node node, int h) { 

    } 


    /* this method had to trim the tree at level h, 
     if h=0, it cut the whole tree. It doesn't change the original tree, 
     it returns a new tree */ 
    /* doesn't work */ 
    public BinaryTree cut2(int h) { 

    } 


    /* i can change parameters */  
    protected BinaryTree cut2(Node node, int h) { 

    } 

    } 
} 

我无法做到反映cut和cut2的方法。请帮助我，谢谢！

Answer 1

你几乎有reflect没错。只要避免创造新的Node对象：

protected void reflect(Node node) { 
    if (node != null) { 
     reflect(node.left); 
     reflect(node.right); 
     Node temp = node.left; 
     node.left = node.right; 
     node.right = temp; 
    } 
} 

至于cut：

public void cut(int h) { 
    if (h == 0) { 
     root = null; 
    } else { 
     cut(root, h - 1); 
    } 
} 

然后，你可以写cut(Node, int)：

protected void cut(Node node, int h) { 
    if (node != null) { 
     if (h == 0) { 
      node.left = node.right = null; 
     } else { 
      cut(node.left, h - 1); 
      cut(node.right, h - 1); 
     } 
    } 
} 

看看你是否可以用你自己的工作了cut2以上为开始。

Answer 2

这听起来像作业，即使标签被修剪，我不认为我们编写完整的二叉树实现是正确的。

话虽如此，你能否解释一下对这两种方法的实现还不清楚？他们几乎相等，除了cut2所需的树复制外。我会通过递归私有方法cutInternal(Node n, int currLevel, int h)传递我们当前所在的级别数来实现它。然后，当currLevel == h我们只修剪两个节点并返回。