JAVA代码实现二叉树的递归遍历
时间: 2023-03-13 17:16:53 浏览: 83
可以使用以下代码来实现二叉树的递归遍历: public void preOrder(TreeNode root) {
if (root != null) {
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
}
相关问题
Java二叉树非递归遍历
Java二叉树的非递归遍历可以通过使用栈数据结构来实现。首先,我们创建一个空的栈,将根节点入栈。然后,我们进入一个循环,直到栈为空为止。在每一次循环中,我们弹出栈顶元素,并将其访问。接下来,如果该节点有右子节点,则将右子节点入栈。如果该节点有左子节点,则将左子节点入栈。由于栈是先进后出的数据结构,所以我们先入栈右子节点,再入栈左子节点,以确保在遍历过程中先访问左子树节点。这样就能够实现二叉树的非递归遍历。
以下是一个示例代码实现二叉树的非递归中序遍历:
```java
public void inorderTraversal(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.leftChild;
}
current = stack.pop();
System.out.print(current.data + " "); // 访问节点
current = current.rightChild;
}
}
```
在这个示例代码中,我们首先判断当前节点是否为空或者栈是否为空,如果不满足则进入循环。在循环内部,我们首先将当前节点及其所有左子节点入栈,直到当前节点为空。然后,我们弹出栈顶节点并访问该节点。最后,将当前节点更新为其右子节点,并继续下一次循环。
通过这种方式,我们可以实现二叉树的非递归中序遍历。你可以根据需要修改代码实现其他类型的非递归遍历,比如前序遍历和后序遍历。<span class="em">1</span><span class="em">2</span>
#### 引用[.reference_title]
- *1* [用Python实现二叉树、二叉树非递归遍历及绘制的例子](https://download.csdn.net/download/weixin_38618784/14869891)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [java实现二叉树树的非递归遍历](https://blog.csdn.net/weixin_41826973/article/details/105555647)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
java实现二叉树层次遍历
要实现二叉树的层次遍历,可以使用递归的方式来完成。首先,我们可以定义一个辅助函数levelOrderHelper,该函数接收一个二叉树的根节点,一个存储层次遍历结果的列表和一个表示当前层次的参数level。在levelOrderHelper函数中,我们首先判断当前节点是否为空,如果为空则直接返回。接下来,我们判断当前层次是否已经在列表中创建了对应的列表,如果没有,则创建一个新的列表。然后,将当前节点的值添加到对应层次的列表中。接着,我们递归调用levelOrderHelper函数遍历当前节点的左子树,并将层次参数level加1。再递归调用levelOrderHelper函数遍历当前节点的右子树,并将层次参数level加1。最后,我们可以定义一个levelOrder函数,该函数接收二叉树的根节点作为参数,并在其中创建一个空的结果列表。然后,我们调用levelOrderHelper函数对二叉树进行层次遍历,并将结果存储到结果列表中。最后,返回结果列表作为层次遍历的结果。
```java
//二叉树的层次遍历
public List<List<String>> levelOrder(Tree root){
List<List<String>> list = new ArrayList<>();
levelOrderHelper(root, list, 0);
return list;
}
//层级遍历辅助
public void levelOrderHelper(Tree root, List<List<String>> list, int level) {
if(root == null) {
return;
}
if(level >= list.size()) {
list.add(new ArrayList<>());
}
list.get(level).add(root.val);
levelOrderHelper(root.left, list, level + 1);
levelOrderHelper(root.right, list, level + 1);
}
```
以上代码是一个简单的Java实现二叉树层次遍历的示例,其中Tree表示二叉树的节点,root表示二叉树的根节点。函数levelOrder接收二叉树的根节点作为参数,并返回一个列表,列表中包含了二叉树的层次遍历结果。函数levelOrderHelper是一个辅助函数,用于递归地进行二叉树的层次遍历,将每个层次的元素分别存储起来。最后,我们可以调用levelOrder函数进行二叉树的层次遍历。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [Java:实现二叉树的层次遍历](https://blog.csdn.net/qq_45000317/article/details/123143184)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *3* [Java实现二叉树的遍历](https://blog.csdn.net/m0_37911706/article/details/125268444)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]