-2

我不得不做一些关于 BinaryTree 的方法（没有搜索二叉树）。我不能做 3 种方法：反射（反射树，我的代码不起作用，因为只反射树的一部分），cut 和 cut2。代码是：

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 的方法。请帮帮我，谢谢！

4

2 回答 2

0

你几乎是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使用上述内容作为开始自己锻炼。

于 2012-10-30T15:52:46.113 回答
0

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

话虽如此，您能解释一下实现这两种方法的不清楚之处吗？除了cut2. 我将通过cutInternal(Node n, int currLevel, int h)传入我们当前所在的级别号的递归私有方法来实现它。然后，当currLevel == h我们只修剪两个节点并返回时。

于 2012-10-30T15:53:08.267 回答