java - 将二叉搜索树打印为单个字符串

Question

我一直在解决一个令我困惑的练习问题。

定义一个满足以下要求的函数treeLevelOrder:如果 Q 是整数二叉搜索树，则 treeLevelOrder(Q) 是 Q 内容根据其在树中的级别的字符串表示形式。 我们以这棵树为例

      9
   /     \
  5       16
 / \     /  \
1   7   12  19

在这种情况下，表达式 treeLevelOrder(Q) 的值将是“[9,5,16,1,7,12,19]”。

我见过类似的问题，但它们不遵循我正在寻找的相同格式，想要按级别顺序或按有序元组打印。这是我一直在编写的一些示例代码:

 private String treeLevelOrder(Node Q)
 {
   if (Q.left == null && Q.right == null)
       return "[" + Q.datum + "]";
   else if (Q.left == null && Q.right != null)
       return "[" + Q.datum + ", "+Q.right.datum+"]" + treeLevelOrder(Q.right);
   else if (Q.left !=null && Q.right == null)
       return"[" + Q.datum + ", "+Q.left.datum+", *]"+ treeLevelOrder(T.left);
   else
       return "[" + Q.datum + ", "+Q.left.datum+", "+Q.right.datum+"]" + 
              treeLevelOrder(Q.left) + treeLevelOrder(Q.right);          
 } 

任何帮助都会有帮助。

编辑:好的，所以我一直在尝试 Geeks for Geeks 的级别顺序示例。 ，谢谢大括号，这会更接近我正在寻找的东西，尽管我无法弄清楚让它返回一个字符串。这是他们使用的代码:

/* function to print level order traversal of tree*/
void printLevelOrder()
{
    int h = height(root);
    int i;
    for (i=1; i<=h; i++)
        printGivenLevel(root, i);
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node root)
{
    if (root == null)
       return 0;
    else
    {
        /* compute  height of each subtree */
        int lheight = height(root.left);
        int rheight = height(root.right);        
        /* use the larger one */
        if (lheight > rheight)
            return(lheight+1);
        else return(rheight+1); 
    }
}
/* Print nodes at the given level */
void printGivenLevel (Node root ,int level)
{
    if (root == null)
        return;
    if (level == 1)
        System.out.print(root.data + ", ");
    else if (level > 1)
    {
        printGivenLevel(root.left, level-1);
        printGivenLevel(root.right, level-1);
    }
}

有什么想法吗？

Answer 1

这是一个使用 while 循环和两个队列来跟踪所有节点的实现:

    public String treeLevelOrder(Node root) {
        StringBuilder result = new StringBuilder("");
        Queue<Node> current = new LinkedList<>();
        Queue<Node> other = new LinkedList<>();
        if(root != null)
            current.add(root);

        while(!current.isEmpty()) {
            while(!current.isEmpty()) {
                Node node = current.remove();
                result.append(",");
                result.append(node.datum);

                // adding children to the other queue
                if(node.left != null)
                    other.add(node.left);
                if(node.right != null)
                    other.add(node.right);
            }

            // swapping the queues
            Queue<Node> temp = current;
            current = other;
            other = temp;
        }

        // building final string
        if(result.length() == 0)
            result.append("[");
        else
            result.setCharAt(0,'[');
        result.append("]");
        return result.toString();
    }