树的遍历前序后序递归算法、层序非递归算法。_二叉树层序遍历非递归代码资源-CSDN下载

共3个文件

java：3个

需积分: 12 119 浏览量 2022-09-03 15:55:35 上传评论收藏 2KB 7Z 举报

在IT领域，树是一种重要的数据结构，广泛应用于各种算法和问题解决中。树的遍历是研究树结构的基础，它包括前序遍历、中序遍历和后序遍历。这里我们将重点讨论前序、后序递归算法以及层次（层序）非递归算法，并基于Java语言进行解析。我们来看树的存储结构。在Java中，通常使用二叉链表（Binary Link List）来表示树结构。`CSNode.java`可能定义了一个类`CSNode`，代表树中的节点，包含一个数据字段和两个指针字段，分别指向左子节点和右子节点。例如： ```java public class CSNode { int data; CSNode left; CSNode right; public CSNode(int data) { this.data = data; left = null; right = null; } } ``` **前序遍历**：在前序遍历中，我们首先访问根节点，然后遍历左子树，最后遍历右子树。递归算法实现如下： ```java public void preOrder(CSNode node) { if (node != null) { System.out.print(node.data + " "); preOrder(node.left); preOrder(node.right); } } ``` **后序遍历**：与前序遍历相反，后序遍历先遍历左子树，再遍历右子树，最后访问根节点。 ```java public void postOrder(CSNode node) { if (node != null) { postOrder(node.left); postOrder(node.right); System.out.print(node.data + " "); } } ``` **层次遍历（非递归）**：层次遍历按照从上到下，从左到右的顺序访问所有节点。可以使用队列（Queue）数据结构实现： ```java import java.util.LinkedList; import java.util.Queue; public void levelOrder(CSNode root) { if (root == null) return; Queue<CSNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { CSNode node = queue.poll(); System.out.print(node.data + " "); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } } ``` 在`Tree.java`和`test.java`中，可能包含了对这些算法的实现和测试。`Tree.java`可能定义了树的构造函数，用于根据给定的数据创建树。`test.java`则可能包含了主函数，创建树实例并调用上述遍历方法，以验证算法的正确性。通过理解和实现这些树的遍历算法，开发者可以更好地掌握数据结构和算法，这对于解决复杂问题，如搜索、排序、图论等问题至关重要。在实际编程中，理解并熟练运用这些基础知识能显著提高代码的效率和质量。

资源详情

资源评论

资源推荐

收起资源包目录

二叉链表.7z （3个子文件）

test.java 1KB

Tree.java 5KB

CSNode.java 1014B

import java.util.LinkedList; import java.util.Queue; import java.util.Stack; import java.util.List; import java.util.ArrayList; import java.util.Deque; import java.util.Map; import java.util.ArrayDeque; import java.util.HashMap; public class Tree<T> { // 根结点 private CSNode rootNode; // 结点个数 private int nodeNum; // 构造的树，传入根的结点 public Tree(CSNode rootNode) { this.rootNode = rootNode; } // 获取根结点 public CSNode getRootNode() { return rootNode; } public CSNode addChild(T data, CSNode parentNode) { CSNode<T> newNode = new CSNode<>(data); nodeNum++; // 如果该结点还没有子结点，那么新结点就是该结点的一个孩子结点 if (parentNode.getFirstNode() == null) { parentNode.setFirstNode(newNode); } else if (parentNode.getFirstNode().getRightNode() == null) { parentNode.getFirstNode().setRightNode(newNode); } else { CSNode rightNode = parentNode.getFirstNode().getRightNode(); while (rightNode.getRightNode() != null) { rightNode = rightNode.getRightNode(); } rightNode.setRightNode(newNode); } return newNode; } public void preOrder(CSNode preNode) { if (preNode != null) { // 先输出根结点 System.out.print(preNode.getData() + " "); preOrder(preNode.getFirstNode()); // 递归找到根结点的第一个孩子结点的兄弟 preOrder(preNode.getRightNode()); } } public void preorderTraversal(CSNode root) {// 非递归 Stack<CSNode> stack = new Stack<>(); CSNode preNode = rootNode; while (preNode != null || !stack.empty()) { while (preNode != null) { stack.push(preNode); System.out.print(preNode.getData() + " "); preNode = preNode.getFirstNode(); } CSNode top = stack.pop(); preNode = top.getRightNode(); } } // 后序遍历 public void postOrder(CSNode preNode) { if (preNode != null) { postOrder(preNode.getFirstNode()); System.out.print(preNode.getData() + " "); // 递归找到根结点的右兄弟，即上一个结点除第一个结点(当前根结点)的所有孩子结点，*/ postOrder(preNode.getRightNode()); } } // 后序非递归 public List<Integer> postorderTraversal(CSNode preNode) { List<Integer> list = new ArrayList<Integer>(); if (preNode == null) { return list; } Map<CSNode, Integer> map = new HashMap<CSNode, Integer>(); Deque<CSNode> stack = new ArrayDeque<CSNode>(); CSNode node = preNode; while (!stack.isEmpty() || node != null) { while (node != null) { stack.push(node); List<CSNode> children = node.children; if (children != null && children.size() > 0) { map.put(node, 0); node = children.get(0); } else { node = null; } } node = stack.peek(); int index = map.getOrDefault(node, -1) + 1; List<CSNode> children = node.children; if (children != null && children.size() > index) { map.put(node, index); node = children.get(index); } else { list.add(node.val); stack.pop(); map.remove(node); node = null; } } return list; } // 层序遍历 public void levelOrder(CSNode preNode) { // 创建队列存储结点 Queue<CSNode> queue = new LinkedList<>(); // 根结点入队 queue.offer(preNode); // 队列非空 while (!queue.isEmpty()) { // 取出队头元素并输出 CSNode node = queue.poll(); System.out.print(node.getData() + " "); CSNode firstNode = node.getFirstNode(); // 队头结点有第一个孩子结点 if (firstNode != null) { // 第一个孩子结点入队 queue.offer(firstNode); CSNode rightNode = firstNode.getRightNode(); // 队头结点除第一个结点外还有结点，继续入队 while (rightNode != null) { queue.offer(rightNode); rightNode = rightNode.getRightNode(); } } } } }