java前序遍历二叉树

可以这样实现：

public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}

其中，TreeNode 表示二叉树的节点，val 表示节点的值，left 和 right 分别表示左右子节点。

相关问题

Java实现前序遍历输出二叉树

Java实现前序遍历输出二叉树的方法如下:

首先, 定义二叉树的结点类型:

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}

然后, 可以使用递归的方式来遍历二叉树:

void preorderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  System.out.println(root.val);  // 访问当前结点
  preorderTraversal(root.left);  // 遍历左子树
  preorderTraversal(root.right); // 遍历右子树
}

或者使用非递归的方式, 可以使用栈来存储遍历的结点:

void preorderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  Stack<TreeNode> stack = new Stack<>();
  TreeNode p = root;
  while (p != null || !stack.isEmpty()) {
    while (p != null) {
      System.out.println(p.val);  // 访问当前结点
      stack.push(p);
      p = p.left;
    }
    if (!stack.isEmpty()) {
      p = stack.pop();
      p = p.right;
    }
  }
}

这两种方法都可以用来实现前序遍历二叉树, 其中第二种方法不使用递归, 可以避免递归带来的调用开销, 在处理大型二叉树时更加高效。

Java根据前序遍历创建二叉树

在Java中，根据前序遍历（Preorder Traversal）创建二叉树通常涉及到递归的过程。前序遍历的顺序是先根节点、再左子树、最后右子树。下面是一个简单的步骤：

1. 首先，我们需要一个Node类，它包含两个属性：值（value）和指向左右子节点的引用（left和right）。

class Node {
    int value;
    Node left, right;

    // 构造函数和默认空节点省略
}

2. 创建一个方法`buildTree(int[] preorder, int start, int end)`，接收前序遍历数组、起始位置和结束位置作为参数。这将用于构建整个树。

public Node buildTree(int[] preorder, int start, int end) {
    if (start > end) return null; // 如果已经遍历完，返回null

    // 根据前序遍历的第一个元素找到根节点
    Node root = new Node(preorder[start]);
    
    // 计算中序遍历的中间位置（根节点的右子树开始位置）
    int mid = findMid(preorder, start + 1, end);

    // 继续在剩余的前序遍历中查找左子树和右子树
    root.left = buildTree(preorder, start + 1, mid - 1);
    root.right = buildTree(preorder, mid, end);

    return root;
}

private int findMid(int[] preorder, int low, int high) {
    // 使用中序遍历的性质，找到根节点右子树的开始位置
    // 中间元素左边的元素都是左子树，右边的是右子树
    // 这里假设数组下标从0开始，所以high+1表示数组长度
    while (low < high) {
        int mid = (low + high) / 2;
        if (preorder[mid] < preorder[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}