多叉树的先序遍历、后序遍历、层次遍历

本文主要是介绍多叉树的先序遍历、后序遍历、层次遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

package com;import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;/*** @author liushihao <liushihao@kuaishou.com>* Created on 2021/4/12 4:38 下午*/
public class TreeTest {public static void main(String[] args) {/*       12   3   45 6   7   8 9*/NaryTreeNode root = new NaryTreeNode(1);root.addChildNode(new NaryTreeNode(2));root.addChildNode(new NaryTreeNode(3));root.addChildNode(new NaryTreeNode(4));List<NaryTreeNode> childList = root.getChildren();childList.get(0).addChildNode(new NaryTreeNode(5));childList.get(0).addChildNode(new NaryTreeNode(6));childList.get(1).addChildNode(new NaryTreeNode(7));childList.get(2).addChildNode(new NaryTreeNode(8));childList.get(2).addChildNode(new NaryTreeNode(9));for (int i : preOrder(root)) {System.out.print(i + "  ");}System.out.println();for (int i : postOrder(root)) {System.out.print(i + "  ");}System.out.println();for (List<Integer> i : levelOrder(root)) {for (int a : i) {System.out.print(a + "  ");}System.out.println();}}/*** 先序遍历：根左右* 利用栈模拟递归调用* 将根结点压入栈中，当栈不空时执行：* 弹出栈中结点，将其放入结果队列中* 将该结点的孩子按照倒序依次放入栈中*/public static List<Integer> preOrder(NaryTreeNode root) {Deque<NaryTreeNode> stack = new LinkedList<>();List<Integer> pre = new LinkedList<>();if (root == null) return pre;stack.add(root);while (!stack.isEmpty()) {NaryTreeNode node = stack.pop();pre.add(node.getVal());Deque<NaryTreeNode> reChildren = new LinkedList<>(node.getChildren());while (!reChildren.isEmpty()) {stack.push(reChildren.pop());}}return pre;}/*** 后序遍历：左右根* 利用栈模拟递归调用* 将根结点压入栈中，当栈不空时执行：* 弹出栈中结点，将其头插放入结果队列中* 将该结点的孩子依次放入栈中* * * 其实后序遍历就是先序遍历的逆序列* 先序遍历：先遍历children再遍历root* 后序遍历：先遍历root再遍历children*/public static List<Integer> postOrder(NaryTreeNode root) {Deque<NaryTreeNode> stack = new LinkedList<>();LinkedList<Integer> post = new LinkedList<>();if (root == null) return post;stack.add(root);while (!stack.isEmpty()) {NaryTreeNode node = stack.pop();// LinkedList的add方法是尾插法post.addFirst(node.getVal());for (NaryTreeNode child : node.getChildren()) {stack.push(child);}}return post;}/*** 层次遍历：* 利用队列模拟递归调用* 将根结点压入队中，当队不空时执行：* 获取当前队列长度，当迭代次数小于当前队列长度时：* 弹出当前队头结点，将其放入当前层的结果队列中* 将该结点的孩子依次放入队列中* 将当前层的结果队列放入结果队列中*/public static List<List<Integer>> levelOrder(NaryTreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;Queue<NaryTreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<>();int size = queue.size();for (int i = 0; i < size; i++) {NaryTreeNode node = queue.poll();level.add(node.getVal());queue.addAll(node.getChildren());}result.add(level);}return result;}
}class NaryTreeNode {private int val;private List<NaryTreeNode> children;public NaryTreeNode(int val) {this.val = val;children = new ArrayList<NaryTreeNode>();}public NaryTreeNode(int val, List<NaryTreeNode> children) {this.val = val;if (children != null) this.children = children;else this.children = new ArrayList<NaryTreeNode>();}public int getVal() {return val;}public List<NaryTreeNode> getChildren() {return children;}public boolean isLeaf() {return children.isEmpty();}public boolean addChildNode(NaryTreeNode node) {children.add(node);return true;}
}