问逐层打印BST树
EN

Code Review用户

提问于 2015-10-02 13:50:45

回答 1查看 147关注 0票数 3

请回顾并告诉我可以作出哪些改进：

package trees;

import java.util.LinkedList;
import java.util.Queue;

public class PrintBSTLevelByLevel {


     public static class Node {

        int data;
        Node left;
        Node right;

        Node(int val){

            this.data = val;
            Node left = null;
            Node right = null;

        }
    }

      public void LevelOrderQueue(Node root){

          Queue q = new LinkedList();
          int levelNodes = 0;

          if(root == null) return;
          q.add(root);

          while(!q.isEmpty()){

              levelNodes = q.size();

              while (levelNodes > 0){

                  Node n = (Node)q.remove();
                  System.out.println(""+n.data);
                  if(n.left!= null)
                      q.add(n.left);
                  if(n.right!=null)
                      q.add(n.right);
                  levelNodes--;

              }
              System.out.println("");




          }



          //return null;
      }

    public static void main(String[] args) {

        Node root = new Node(5);

        root.left = new Node(10);
        root.right = new Node(15);
        root.left.left = new Node(20);
        root.left.right = new Node(25);
        root.right.left = new Node(30);
        root.right.right = new Node(35);

        PrintBSTLevelByLevel l = new PrintBSTLevelByLevel();

        System.out.println(" Output by Better Approach : ");
        l.LevelOrderQueue(root);




    }




}

tree

java

回答 1

Code Review用户

回答已采纳

发布于 2015-10-05 17:58:14

尽管您的代码足以完成当前任务，但我将创建一个完全(或部分)功能良好的Tree类，以便以后可以使用它。另一个类将处理显示。这就是Tree类的样子：

public class Tree<T> {

    private Node rootNode;

    public Tree() {
        rootNode = null;
    }

    public Tree(T rootValue) {
        rootNode = new Node(rootValue);
    }

    public Node getRootNode() {
        return rootNode;
    }

    public Node createNewNode(T value) {
        return new Node(value);
    }

    class Node {

        private T value;
        public Node left = null;
        public Node right = null;

        Node(T value) {
            this.value = value;
        }

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

    }

}

这是一个非常基本的Tree类，它具有非常基本的函数，但是它完成了工作。稍后，当您需要Tree类的更多函数时，您可以轻松地去添加它。课堂解释：

默认构造函数(Tree())只将根节点设置为null。
另一个构造函数将使用参数并创建一个新的Node，其中包含参数的值。
getRootNode()方法是获取根Node，这样就可以得到其他Nodes，如下所示：

// example
Tree tree = new Tree(10);
// initialization of values
Node someNode = tree.getRootNode().left.right/*etc*/;

createNewNode(T value)方法提供了对其他无法访问的Node(T value)构造函数(至少在包之外)的间接访问。虽然这不是必要的，因为您可以让Node的S构造函数公开，这是以后的良好实践。
Node类是一个简单的类，它表示一个具有左右节点的节点，以及它的值：。
- 该值是一个private变量，因此访问它需要getter和setter。再说一遍，尽管您可以只制作value public，但最好不要这样做。
- 为了便于使用，我将left和right变量公之于众。尽管它与良好实践不同，但也有一些例外情况(一些程序员可能不同意这种说法)。

现在，对于打印组件：

由于我完全重新设计了Tree类，所以我们也必须更改您的方法。为了准确地执行代码所做的工作，下面是新的方法：

public <T> void LevelOrderQueue(Tree<T> tree) {
    if (tree != null) {
        Tree<T>.Node rootNode = tree.getRootNode();
        if (rootNode != null) {
            Queue<Tree<T>.Node> queue = new LinkedList<>();
            int levelNodes = 0;
            queue.add(rootNode);
            while (!queue.isEmpty()) {
                levelNodes = queue.size();
                while (levelNodes > 0) {
                    Tree<T>.Node node = queue.remove();
                    System.out.println(node.getValue());
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                    levelNodes--;
                }
                System.out.println();
            }
        }
    }

}

注意一些更改：

该方法现在接受的是Tree<T>对象而不是Node对象。
这个方法有两个null检查；第一个检查树，第二个检查根节点。
我为if语句添加了大括号。之所以如此，是因为缺乏支撑可能会导致可怕的、难以识别的错误，这可能会让你连续几天感到沮丧。我找不到我写得更详细的那篇文章，但一旦我找到它，我会把它贴上去。(编辑:找到了！读这里)
我在Queue初始化中添加了泛型。
我删除了Node的演员阵容。当使用泛型时，这是不必要的。
我改了名字。像node和queue这样的变量名比n和q更容易理解。
我把System.out.println("");改成了System.out.println();。有一个不带参数的println()方法。
我把System.out.println(""+n.data);改成了System.out.println(node.value);。开始的""不是必需的，因为System.out.println()会通过类定义的toString()方法(或者在定义它的继承链中的任何类)自动将给定的内容转换为字符串。
我在一些单独的关键字、变量名、大括号、括号等之间添加了更多的空间:这是为了更好的可读性，并遵循Java的约定。如果您不确定，只需在谷歌上搜索"Java约定“即可。
我去掉了空白处。您可以在您喜欢的地方重新添加它们；我喜欢这样的代码。