java多叉树的遍历 小鱼儿 2023-10-18 14:06 51阅读 0赞 用过了二叉树后,正好业务上有一个需求,就是需要求出从根节点到每个叶子节点的路径集合,由于不是二叉树,而是如同一种多叉树的结构,下面来看具体代码, 1、节点对象,包含3个属性,当前节点Id,持有的父节点Id,当前节点的内容, public class TreeNode { /** 节点Id */ private String nodeId; /** 父节点Id */ private String parentId; /** 文本内容 */ private String text; /** * 构造函数 * * @param nodeId * 节点Id */ public TreeNode(String nodeId) { this.nodeId = nodeId; } /** * 构造函数 * * @param nodeId * 节点Id * @param parentId * 父节点Id */ public TreeNode(String nodeId, String parentId) { this.nodeId = nodeId; this.parentId = parentId; } public String getNodeId() { return nodeId; } public void setNodeId(String nodeId) { this.nodeId = nodeId; } public String getParentId() { return parentId; } public void setParentId(String parentId) { this.parentId = parentId; } public String getText() { return text; } public void setText(String text) { this.text = text; } } 2、多节点,我理解的是某个包含了多个其他节点的节点,即这个ManyTreeNode实际上存储的是当前节点以及对其包含的多个节点的引用, public class ManyTreeNode { private TreeNode data; private List<ManyTreeNode> childList; public ManyTreeNode(TreeNode data) { this.data = data; this.childList = new ArrayList<ManyTreeNode>(); } public ManyTreeNode(TreeNode data, List<ManyTreeNode> childList) { this.data = data; this.childList = childList; } public TreeNode getData() { return data; } public void setData(TreeNode data) { this.data = data; } public List<ManyTreeNode> getChildList() { return childList; } public void setChildList(List<ManyTreeNode> childList) { this.childList = childList; } } 3、多叉树节点的操作,插入,遍历等, public class ManyNodeTree { /** 树根 */ private ManyTreeNode root; public ManyNodeTree() { root = new ManyTreeNode(new TreeNode("root")); } // 生成一个多茶树,根节点为root public ManyNodeTree createTree(List<TreeNode> treeNodes) { if (treeNodes == null || treeNodes.size() <= 0) { return null; } ManyNodeTree manyNodeTree = new ManyNodeTree(); // 将所有节点添加到多茶树中 for (TreeNode treeNode : treeNodes) { if (treeNode.getParentId().equals("root")) { manyNodeTree.getRoot().getChildList().add(new ManyTreeNode(treeNode)); } else { addChild(manyNodeTree.getRoot(), treeNode); } } return manyNodeTree; } // 向指定多叉树节点添加子节点 public void addChild(ManyTreeNode manyTreeNode, TreeNode child) { for (ManyTreeNode item : manyTreeNode.getChildList()) { if (item.getData().getNodeId().equals(child.getParentId())) { // 找到对应的父亲 item.getChildList().add(new ManyTreeNode(child)); break; } else { if (item.getChildList() != null && item.getChildList().size() > 0) { addChild(item, child); } } } } // 遍历多叉树 public String iteratorTree(ManyTreeNode manyTreeNode) { List<String> rsData = new ArrayList<>(); StringBuilder buffer = new StringBuilder(); buffer.append("|"); if (manyTreeNode != null) { for (ManyTreeNode index : manyTreeNode.getChildList()) { buffer.append(index.getData().getNodeId() + ","); if (index.getChildList() != null && index.getChildList().size() > 0) { buffer.append(iteratorTree(index)); } } } //buffer.append("\n"); return buffer.toString(); } public ManyTreeNode getRoot() { return root; } public void setRoot(ManyTreeNode root) { this.root = root; } public static void main(String[] args) { List<TreeNode> treeNodes = new ArrayList<TreeNode>(); treeNodes.add(new TreeNode("系统权限管理", "root")); treeNodes.add(new TreeNode("用户管理", "系统权限管理")); treeNodes.add(new TreeNode("角色管理", "系统权限管理")); treeNodes.add(new TreeNode("组管理", "系统权限管理")); treeNodes.add(new TreeNode("用户菜单管理", "系统权限管理")); treeNodes.add(new TreeNode("角色菜单管理", "系统权限管理")); treeNodes.add(new TreeNode("用户权限管理", "系统权限管理")); treeNodes.add(new TreeNode("站内信", "root")); treeNodes.add(new TreeNode("写信", "站内信")); treeNodes.add(new TreeNode("收信", "站内信")); treeNodes.add(new TreeNode("草稿", "站内信")); ManyNodeTree tree = new ManyNodeTree(); System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot())); System.out.println("-------------"); String result = tree.iteratorTree(tree.createTree(treeNodes).getRoot()); } } 运行一下main函数,可以打印出从root开始到各个最终的子节点的值
还没有评论,来说两句吧...