时间戳

首页 > 解决方案 > 打印三叉树的元素

java - 打印三叉树的元素

问题描述

给出了深度为 n 的完整三叉树。编写一个程序，打印 Pre-Order 中树的所有节点。枚举从 0 开始，依次遍历各个级别。

输入： n 是树的深度。

输出： Pre-Order 中的一系列节点除以空格。

样本输入： 2

样本输出： 0 1 4 5 6 2 7 8 9 3 10 11 12

class Main {
public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int targetDepth = Integer.parseInt(reader.readLine());
    int currentDepth = 1;
    int node = 0;
    System.out.print(node + " ");
    printNodes(node, currentDepth, targetDepth);
}

public static void printNodes(int node, int currentDepth, int targetDepth) {
    if (targetDepth == 1) {
        System.out.print((3 * node + 1) + " " + (3 * node + 2) + " " + (3 * node + 3));
        return;
    }
    if (currentDepth < targetDepth) {
        int leftChild, midChild, rightChild;
        int rightParent = 3 * node + 3;
        node++;
        while (node <= rightParent) {
            leftChild = 3 * node + 1;
            midChild = 3 * node + 2;
            rightChild = 3 * node + 3;
            System.out.print(node + " " + leftChild + " " + midChild + " " + rightChild + " ");
            node++;
        }
        node = rightParent;
        currentDepth++;
        printNodes(node, currentDepth, targetDepth);
    }
}

一个简单的测试报告一个错误：无效的答案。测试使用深度为 3 的树，虽然测试成功通过了深度为 2 的树。我已经检查了 100 次，根据问题的条件，答案必须是正确的。也许我错过了一些东西。请指出我正确的方向。

标签： java

解决方案

你需要做的是：

public static void process(Node n){
  sysout(n.value)
  process(n.right)
  process(n.mid)
  process(n.left)}

你正在做的是：

public static void process(Node n){
      sysout(n.value)
      sysout(n.left.value)
      sysout(n.mid.value)
      sysout(n.right.value)
      process(n.right)}

保持简单，只需尝试打印当前节点，然后继续其子节点。

如果您目前正在学习数据结构的课程，还有一种使用堆栈或队列的方法。我建议也检查一下。在使用递归时，您自然会使用 java 使用的进程堆栈。

伪代码如下：

push initial node into the stack 
while stack has nodes:
     pop node from the stack 
     print nodes value 
     if node is not at the target depth:
          push node's children onto the stack(from right to left)

当堆栈为空时，你得到了你的序列！

推荐阅读