Python 官方文档：入门教程 => 点击学习
目录一、先序遍历与后序遍历 二、中序遍历三、层序遍历一、先序遍历与后序遍历 先序遍历根节点，再遍历左子树，再遍历右子树。 后序遍历先遍历左子树，再遍历右子树，再遍历根节点。 先序遍
先序遍历根节点，再遍历左子树，再遍历右子树。
后序遍历先遍历左子树，再遍历右子树，再遍历根节点。
先序遍历递归实现：
public static void preOrderByRecursion(Treenode root) {
// 打印节点值
System.out.println(root.value);
preOrder(root.left);
preOrder(root.right);
}
先序遍历的非递归实现：
非递归实现需要借助栈这样一个数据结构，实际上递归实现也是依靠栈，只不过是隐式的。
public static void preOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
// 打印节点值
System.out.print(node.value + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
后序遍历递归实现：先序遍历反过来，就不赘述了。
public static void postOrderByRecursion(TreeNode root) {
postOrderByRecursion(root.left);
postOrderByRecursion(root.right);
System.out.println(root.value);
}
后序遍历非递归实现：后序遍历就是先序遍历反过来，所以需要两个栈，多出来的栈用来反向输出。
public static void postOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(root);
while (!s1.empty()) {
TreeNode node = s1.pop();
s2.push(node);
if (node.left != null) {
s1.push(node.left);
}
if (node.right != null) {
s1.push(node.right);
}
}
while (!s2.empty()) {
System.out.println(s2.pop().value);
}
}
中序遍历先遍历左子树，再遍历根节点，再遍历右子树。
递归遍历：
public static void inOrderByRecursion(TreeNode root) {
if (root == null) {
return;
}
inOrderByRecursion(root.left);
// 打印节点值
System.out.println(root.value);
inOrderByRecursion(root.right);
}
非递归遍历：
public static void inOrder(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
while (!stack.empty()) {
TreeNode node = stack.pop();
System.out.println(node.value);
cur = node.right;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
}
}
层序遍历顾名思义就是一层一层，从左到右的遍历二叉树。需要用到队列这一数据结构。
public static void floorOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.value);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
到此这篇关于Java二叉树的四种遍历（递归与非递归）的文章就介绍到这了,更多相关Java二叉树的四种遍历内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
--结束END--
本文标题: Java二叉树的四种遍历（递归与非递归）
本文链接: https://www.lsjlt.com/news/137423.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑，方便收藏和打印～
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0