二叉树S型遍历算法

2024-05-31 21:24| 来源: 网络整理| 查看: 265

算法需求

如下图所示，按照图中的箭头顺序遍历节点。因为实在找不到更好的算法描述方式，暂且就叫做S型遍历吧 ^_^ 在这里插入图片描述

算法分析

图中每一层节点的迭代顺序都会改变，使用传统的单个队列或单个栈都是以固定的顺序存储数据，实现起来特别麻烦，所以我们考虑使用两个栈空间来分别存储正向和逆向的节点，以达到按层换序的目的

我们以第一、二行和第三行为例，初始化时将root节点1压入右栈 1、遍历右栈节点1时，按顺序将其左子节点3和右子节点2压入左栈（图一）

2、然后对左栈进行出栈操作。取出节点2，将其右子节点6压入右栈。取出节点3，分别将其右子节点5和左子节点4压入右栈（图二）

3、继续遍历右栈，将每个节点按照其左右子节点的顺序压入左栈（图三）。重复以上三个步骤，完成递归操作在这里插入图片描述

代码实现 public static void print(TreeNode root) { //左栈 Stack leftStack = new Stack(); //右栈 Stack rightStack = new Stack(); //初始化-将根节点压入右栈 rightStack.push(root); //打印树 printTree(leftStack, rightStack); } public static void printTree(Stack leftStack, Stack rightStack) { if (leftStack.isEmpty() && rightStack.isEmpty()) { return; } //右栈出栈操作 printRight(leftStack, rightStack); //左栈出栈操作 printLeft(leftStack, rightStack); //递归 printTree(leftStack, rightStack); } private static void printRight(Stack leftStack, Stack rightStack) { while (!rightStack.isEmpty()) { TreeNode treeNode = rightStack.pop(); if (treeNode != null) { System.out.print(treeNode.getData() + "-->"); TreeNode left = treeNode.getLeft(); TreeNode right = treeNode.getRight(); leftStack.push(left); leftStack.push(right); } } } private static void printLeft(Stack leftStack, Stack rightStack) { while (!leftStack.isEmpty()) { TreeNode treeNode = leftStack.pop(); if (treeNode != null) { System.out.print(treeNode.getData() + "-->"); TreeNode left = treeNode.getLeft(); TreeNode right = treeNode.getRight(); rightStack.push(right); rightStack.push(left); } } }

定义树对象

class TreeNode { private TreeNode left; private TreeNode right; private final int data; public TreeNode(int data) { this.data = data; } public TreeNode getLeft() { return left; } public void setLeft(TreeNode left) { this.left = left; } public TreeNode getRight() { return right; } public void setRight(TreeNode right) { this.right = right; } public int getData() { return data; } }

启动程序+组装树数据【案例图】

public static void main(String[] args) { TreeNode root = new TreeNode(1); TreeNode t2 = new TreeNode(2); TreeNode t3 = new TreeNode(3); TreeNode t4 = new TreeNode(4); TreeNode t5 = new TreeNode(5); TreeNode t6 = new TreeNode(6); TreeNode t7 = new TreeNode(7); TreeNode t8 = new TreeNode(8); TreeNode t9 = new TreeNode(9); root.setLeft(t3); root.setRight(t2); t3.setLeft(t4); t3.setRight(t5); t2.setRight(t6); t5.setLeft(t9); t6.setLeft(t8); t6.setRight(t7); print(root); }

打印结果如下：

1–>2–>3–>4–>5–>6–>7–>8–>9–>

总结

当然我们也可以按照从根节点的右子节点开始遍历（反S型），只需要将根节点压入左栈，同时改变一下printRight和printLeft打印的顺序即可

【本文地址】

公司简介

联系我们