java多叉树的遍历

小鱼儿 2023-10-18 14:06 101阅读 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开始到各个最终的子节点的值