方法二叉樹

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我們只修剪兩個節點並返回。