如何为BinaryTree类编写left()和right()方法？

7 浏览
0 Comments

如何为BinaryTree类编写left()和right()方法？

我正在修读一门数据结构与算法课程。上节课，我的教授在黑板上放了一些代码，解释了如何编写size()、height()以及left()/right()方法，为我们准备了一次关于二叉树平衡的测验。\n他在黑板上写下了下面的代码，但是他提到虽然他犯了一个错误，现在我们要关注逻辑，他会运行一些测试来理解他的错误。\n

public class BT {
    TreeNode root;
    BT myTree;
    //size
    public int size() {
        if(this.isEmpty())
            return 0;
        return (1 + this.left().size() + this.right().size());
    }
    //isEmpty()
    public boolean isEmpty() {
        return (root == null);
    }
    //left
    public BT left() {
        return root.left;
    } 
    public BT right() {
        return root.right;
    }
}

\n在周末，由于教授办公室被大量学生拜访以准备期中考试，我尝试自己解决这个问题。\n如何修复这个方法呢？\n编辑：\n这是TreeNode类：\n

class TreeNode {
    T data;
    TreeNode left;
    TreeNode right;
}

\n它是在同一个包中的另一个类中定义的。

0

2 答案

0 Comments

问题的出现原因是left()和right()方法应该属于内部的TreeNode类，而不是公开的方法。解决方法是将这两个方法移动到TreeNode类中去。

class TreeNode {
    T data;
    TreeNode left;
    TreeNode right;
    TreeNode left() {
        return left;
    } 
    TreeNode right() {
        return right;
    }
    int size() {
        int n = 1;
        if (left != null) {
            n += left.size();
        } else if (right != null) {
            n += right.size();
        }
        return n;
    }
}

由于没有公共的子树概念，容器类BT只持有大小和根节点。因此，拥有像left()和right()这样的getter方法更多是一种风格上的考虑。

0
0 Comments

问题的原因是在一个BinaryTree类中，TreeNode类被定义为一个内部类。在这种情况下，不能直接访问内部类而不创建外部类的实例。解决方法是在创建TreeNode对象时，需要同时创建外部类的实例。

如果TreeNode类被定义在A类内部，那么创建TreeNode对象的方式应该是：

A.TreeNode node = new A.TreeNode()

如果我对内部类的理解有误，请告诉我，我会相应地修改或删除我的回答。

链接中的stackoverflow页面解释了访问内部类的问题以及解决方法。

不完全正确，更像是这样的：

class TreeNode {
    T data;
    TreeNode left;
    TreeNode right;
}
public class Traverse {
    // 代码主体
}

0