Java实现二叉树深度优先遍历中的先序遍历
时间: 2023-06-20 11:08:33 浏览: 55
先序遍历是二叉树深度优先遍历的一种,其遍历顺序为 根节点 -> 左子树 -> 右子树。Java实现先序遍历的代码如下:
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
```
上述代码中,我们定义了一个TreeNode类用于表示二叉树节点,其中包含一个val属性表示节点值,以及left和right属性表示左右子节点。preorderTraversal方法用于进行先序遍历,输入参数为二叉树根节点root。在方法中,我们首先判断root是否为空,如果是,则直接返回;否则,输出root节点的值,然后递归调用preorderTraversal方法遍历root的左子树和右子树。
相关问题
java 二叉树深度优先遍历
Java实现二叉树的深度优先遍历可以使用递归或者栈来实现。递归方法比较简单,可以按照先序遍历、中序遍历和后序遍历的方式进行深度优先遍历。下面是一段示例代码,演示了Java中使用递归实现深度优先遍历的方法:
```
public class BinaryTree {
// 定义二叉树节点类
public class TreeNode {
public TreeNode leftNode;
public TreeNode rightNode;
public Integer val;
public TreeNode(Integer val) {
this.val = val;
}
}
// 深度优先遍历-先序遍历
public void startErgodic(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
startErgodic(node.leftNode);
startErgodic(node.rightNode);
}
// 深度优先遍历-中序遍历
public void midErgodic(TreeNode node) {
if (node == null) {
return;
}
midErgodic(node.leftNode);
System.out.print(node.val + " ");
midErgodic(node.rightNode);
}
// 深度优先遍历-后序遍历
public void endErgodic(TreeNode node) {
if (node == null) {
return;
}
endErgodic(node.leftNode);
endErgodic(node.rightNode);
System.out.print(node.val + " ");
}
// 二叉树的插入操作
public void insert(Integer val) {
// 插入操作的具体实现代码
}
// 二叉树的递归插入操作
public void insertDigui(Integer val, TreeNode node) {
// 递归插入操作的具体实现代码
}
// 广度优先遍历
public void Order() {
// 广度优先遍历的具体实现代码
}
}
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
// 创建二叉树并进行插入操作
// 深度优先遍历-先序遍历
binaryTree.startErgodic(binaryTree.root);
System.out.println();
// 深度优先遍历-中序遍历
binaryTree.midErgodic(binaryTree.root);
System.out.println();
// 深度优先遍历-后序遍历
binaryTree.endErgodic(binaryTree.root);
}
}
```
上述代码中的`startErgodic()`方法实现了二叉树的深度优先遍历先序遍历,`midErgodic()`方法实现了中序遍历,`endErgodic()`方法实现了后序遍历。可以根据需要选择相应的方法进行遍历。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [Java实现二叉树的深度优先遍历和广度优先遍历算法示例](https://download.csdn.net/download/weixin_38518885/12761000)[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* *3* [java有序二叉树的深度优先遍历和广度优先遍历](https://blog.csdn.net/m566666/article/details/122280365)[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 ]
不用递归,用栈实现二叉树的中序遍历、先序遍历、后续遍历C语言代码
好的,以下是C语言代码实现二叉树的中序遍历、先序遍历、后续遍历,使用栈而非递归:
```C
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int size = 0;
while (root || size) {
while (root) {
stack[size++] = root;
root = root->left;
}
root = stack[--size];
printf("%d ", root->data);
root = root->right;
}
}
void preorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int size = 0;
while (root || size) {
while (root) {
printf("%d ", root->data);
stack[size++] = root;
root = root->left;
}
root = stack[--size];
root = root->right;
}
}
void postorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int size = 0;
struct TreeNode* lastVisited = root;
while (root || size) {
while (root) {
stack[size++] = root;
root = root->left;
}
root = stack[size - 1];
if (root->right && root->right != lastVisited) {
root = root->right;
} else {
printf("%d ", root->data);
lastVisited = root;
size--;
root = NULL;
}
}
}
int main() {
struct TreeNode a = {4, NULL, NULL};
struct TreeNode b = {5, NULL, NULL};
struct TreeNode c = {2, &a, &b};
struct TreeNode d = {6, NULL, NULL};
struct TreeNode e = {3, &d, NULL};
struct TreeNode f = {1, &c, &e};
inorderTraversal(&f);
printf("\n");
preorderTraversal(&f);
printf("\n");
postorderTraversal(&f);
printf("\n");
return 0;
}
```
请注意,这只是实现的一种方法,并不是唯一的正确答案。