概述
二叉树的非递归遍历
- 非递归遍历模板
- 前序遍历
- 中序遍历
- 后序遍历
- 测试
- 代码
- 结果
非递归遍历模板
这个模板只适用于前序遍历和中序遍历
private static void travers(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur!=null || !stack.isEmpty()) {
if (cur != null) {
//这里写前序遍历代码
//在进入左子树前访问根节点
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
//这里中序遍历代码写这里
//在进入右子树前访问根节点
cur = cur.right;
}
}
}
前序遍历
/**
* 迭代前序遍历
* @param root
*/
private static void pre_travers_iterator(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur!=null || !stack.isEmpty()) {
if (cur != null) {
//前序遍历代码
System.out.print(cur.val + " ");
//在进入左子树前访问根节点
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
//中序遍历代码写这里
cur = cur.right;
}
}
}
中序遍历
/**
* 迭代中序遍历
* @param root
*/
private static void in_travers_itrator(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur!=null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
//中序遍历代码
System.out.print(cur.val + " ");
//在进入右子树前访问根节点
cur = cur.right;
}
}
}
后序遍历
后序遍历比较特殊，它是先访问左节点、再访问右节点，最后再访问根节点。从比较好理解的角度来说的话，采用双栈是最好的。
后序遍历：左右根
从栈的特性的来说，先进后出，所以根节点先进去，然后右节点，最后才是左节点
/**
* 迭代后序遍历
* @param root
*/
private static void post_travers_iterator(TreeNode root) {
//记录结点栈
Stack<TreeNode> stack_main = new Stack<>();
//辅助栈
Stack<TreeNode> stack_help = new Stack<>();
stack_help.push(root);
while (!stack_help.isEmpty()) {
TreeNode cur = stack_help.pop();
stack_main.push(cur);
if (cur.left != null) {
stack_help.push(cur.left);
}
if (cur.right != null) {
stack_help.push(cur.right);
}
}
while (!stack_main.isEmpty()) {
TreeNode node = stack_main.pop();
System.out.print(node.val + " ");
}
}
测试
迭代和递归一起测试
代码
package com.BinaryTree;
import java.util.Stack;
/**
* 前中后遍历树
* 递归
* 迭代
* @author: 小LeetCode~
**/
public class TraversTree {
public static void main(String[] args) {
//构造一个棵二叉树
TreeNode root = createTree();
//递归前序遍历[0,1,3,7,4,2,5,8,6]
System.out.println("递归前序遍历：");
pre_travers(root);
System.out.println();
//递归中序遍历[3,7,1,4,0,8,5,2,6]
System.out.println("递归中序遍历：");
in_travers(root);
System.out.println();
//递归后序遍历[7,3,4,1,8,5,6,2,0]
System.out.println("递归后序遍历：");
post_travers(root);
System.out.println();
//迭代前序遍历
System.out.println("迭代前序遍历：");
pre_travers_iterator(root);
System.out.println();
//迭代中序遍历
System.out.println("迭代中序遍历：");
in_travers_itrator(root);
System.out.println();
//迭代后序遍历
System.out.println("迭代后序遍历：");
post_travers_iterator(root);
}
/**
* 构造一个棵二叉树
* @return
*/
private static TreeNode createTree() {
TreeNode root = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
node3.right = node7;
node5.left = node8;
return root;
}
/**
* 递归前序遍历
* @param root
*/
private static void pre_travers(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
pre_travers(root.left);
pre_travers(root.right);
}
/**
* 递归中序遍历
* @param root
*/
private static void in_travers(TreeNode root) {
if (root == null) {
return;
}
in_travers(root.left);
System.out.print(root.val + " ");
in_travers(root.right);
}
/**
* 递归后序遍历
* @param root
*/
private static void post_travers(TreeNode root) {
if (root == null) {
return;
}
post_travers(root.left);
post_travers(root.right);
System.out.print(root.val + " ");
}
/**
* 迭代前序遍历
* @param root
*/
private static void pre_travers_iterator(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur!=null || !stack.isEmpty()) {
if (cur != null) {
//前序遍历代码
System.out.print(cur.val + " ");
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
//中序遍历代码写这里
cur = cur.right;
}
}
}
/**
* 迭代中序遍历
* @param root
*/
private static void in_travers_itrator(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur!=null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right;
}
}
}
/**
* 迭代后序遍历
* @param root
*/
private static void post_travers_iterator(TreeNode root) {
Stack<TreeNode> stack_main = new Stack<>();
Stack<TreeNode> stack_help = new Stack<>();
stack_help.push(root);
while (!stack_help.isEmpty()) {
TreeNode cur = stack_help.pop();
stack_main.push(cur);
if (cur.left != null) {
stack_help.push(cur.left);
}
if (cur.right != null) {
stack_help.push(cur.right);
}
}
while (!stack_main.isEmpty()) {
TreeNode node = stack_main.pop();
System.out.print(node.val + " ");
}
}
}
结果
最后
以上就是虚拟小土豆为你收集整理的二叉树的非递归遍历模板非递归遍历模板前序遍历中序遍历后序遍历测试的全部内容，希望文章能够帮你解决二叉树的非递归遍历模板非递归遍历模板前序遍历中序遍历后序遍历测试所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复