多叉树的查找及转换
1. 带有父节点信息的节点：
?
public class FlatNode {
??? private Integer path;
??? private String name;
??? private Integer parent;
??? public Integer getPath() {
??????? return path;
??? }
??? public void setPath(Integer path) {
??????? this.path = path;
??? }
??? public Integer getParent() {
??????? return parent;
??? }
??? public void setParent(Integer parent) {
??????? this.parent = parent;
??? }
??? public String getName() {
??????? return name;
??? }
??? public void setName(String name) {
??????? this.name = name;
??? }
??? @Override
??? public String toString() {
??????? return "FlatNode{" +
??????????????? "path=" + path +
??????????????? ", name='" + name + '\'' +
??????????????? ", parent=" + parent +
??????????????? '}';
??? }
}
?
2. 多叉树的节点：
public class MulNode {
??? private Integer path;
??? private String name;
??? private List<MulNode> childList;
??? public Integer getPath() {
??????? return path;
??? }
??? public void setPath(Integer path) {
??????? this.path = path;
??? }
??? public String getName() {
??????? return name;
??? }
??? public void setName(String name) {
??????? this.name = name;
??? }
??? public List<MulNode> getChildList() {
??????? return childList;
??? }
??? public void setChildList(List<MulNode> childList) {
??????? this.childList = childList;
??? }
??? public boolean hasChildren(MulNode node) {
??????? return node.getChildList() != null && node.getChildList().size() > 0;
??? }
??? @Override
??? public String toString() {
??????? return "MulNode{" +
??????????????? "path=" + path +
??????????????? ", name='" + name + '\'' +
??????????????? ", childList=" + childList +
??????????????? '}';
??? }
}
?
3.工具类，包括多叉树遍历查找节点方法（利用队列进行递归层序遍历 PS :从二叉树层序遍历得到的灵感）
???????????????? 二叉树转换成带有父节点信息的一位数组方法（同样是利用递归）
???????????????? 测试方法--main函数。
?
public class NodeUtils {
??? public static MulNode find(MulNode root, Integer value) {
??????? Queue<MulNode> queue = new LinkedList<MulNode>();
??????? queue.add(root);
??????? return find(queue, value);
??? }
??? // 层序遍历
??? private static MulNode find(Queue<MulNode> queue, Integer value) {
??????? MulNode res = null;
??????? while (!queue.isEmpty()) {
??????????? MulNode node = queue.peek();
??????????? if (node.getPath().equals(value)) {
??????????????? res = node;
??????????????? break;
??????????? } else {
??????????????? queue.remove();
??????????????? if (node.hasChildren(node)) {
??????????????????? for (MulNode child : node.getChildList()) {
??????????????????????? queue.add(child);
??????????????????? }
??????????????? } else {
??????????????????? find(queue, value);
??????????????? }
??????????? }
??????? }
??????? return res;
??? }
??? public static List<FlatNode> transfer(MulNode root) {
??????? Queue<MulNode> queue = new LinkedList<MulNode>();
??????? queue.add(root);
??????? Queue<MulNode> parent = new LinkedList<MulNode>();
??????? List<FlatNode> nodeList = new ArrayList<FlatNode>();
??????? return transfer(queue, parent, nodeList);
??? }
??? private static List<FlatNode> transfer(Queue<MulNode> queue, Queue<MulNode> parent, List<FlatNode> nodeList) {
??????? while (!queue.isEmpty()) {
??????????? MulNode node = queue.peek();
??????????? MulNode father = parent.peek();
??????????? FlatNode flatNode = new FlatNode();
??????????? flatNode.setName(node.getName());
??????????? flatNode.setPath(node.getPath());
??????????? if (father == null) {
??????????????? flatNode.setParent(null);
??????????? } else {
??????????????? flatNode.setParent(father.getPath());
??????????????? parent.remove();
??????????? }
??????????? queue.remove();
??????????? nodeList.add(flatNode);
??????????? if (node.hasChildren(node)) {
??????????????? for (MulNode child : node.getChildList()) {
??????????????????? queue.add(child);
??????????????????? parent.add(node);
??????????????? }
??????????? } else {
??????????????? transfer(queue, parent, nodeList);
??????????? }
??????? }
??????? return nodeList;
??? }
??? public static void main(String[] args) {
??????? MulNode root = new MulNode();
??????? root.setPath(0);
??????? root.setName("root");
??????? MulNode node1 = new MulNode();
??????? node1.setPath(1);
??????? node1.setName("Clothes");
??????? MulNode node2 = new MulNode();
??????? node2.setPath(2);
??????? node2.setName("food");
??????? MulNode node3 = new MulNode();
??????? node3.setPath(3);
??????? node3.setName("Animal");
??????? MulNode node10 = new MulNode();
??????? node10.setPath(10);
??????? node10.setName("shoe");
??????? MulNode node11 = new MulNode();
??????? node11.setPath(11);
??????? node11.setName("skirt");
??????? MulNode node12 = new MulNode();
??????? node12.setPath(12);
??????? node12.setName("jacket");
??????? MulNode node20 = new MulNode();
??????? node20.setPath(20);
??????? node20.setName("pizza");
??????? MulNode node21 = new MulNode();
??????? node21.setPath(21);
??????? node21.setName("noodle");
??????? MulNode node30 = new MulNode();
??????? node30.setPath(30);
??????? node30.setName("hen");
??????? MulNode node31 = new MulNode();
??????? node31.setPath(31);
??????? node31.setName("pig");
??????? MulNode node32 = new MulNode();
??????? node32.setPath(32);
??????? node32.setName("wolf");
??????? MulNode node200 = new MulNode();
??????? node200.setPath(200);
??????? node200.setName("Italy Pizza");
??????? List<MulNode> list1 = new ArrayList<MulNode>();
??????? List<MulNode> list10 = new ArrayList<MulNode>();
??????? List<MulNode> list20 = new ArrayList<MulNode>();
??????? List<MulNode> list30 = new ArrayList<MulNode>();
??????? List<MulNode> list200 = new ArrayList<MulNode>();
??????? list200.add(node200);
??????? node20.setChildList(list200);
??????? list20.add(node20);
??????? list20.add(node21);
??????? node2.setChildList(list20);
??????? list30.add(node30);
??????? list30.add(node31);
??????? list30.add(node32);
??????? node3.setChildList(list30);
??????? list10.add(node10);
??????? list10.add(node11);
??????? list10.add(node12);
??????? node1.setChildList(list10);
??????? list1.add(node1);
??????? list1.add(node2);
??????? list1.add(node3);
??????? root.setChildList(list1);
??????? System.out.println(root);
??????? System.out.println(find(root, 32));
??????? System.out.print(transfer(root));
??? }
}
