多叉树的一些算法

import com.nfschina.iot.iotdroid.model.Node;


public class NodeUtils {
	/**
	 * 
	 * @description: 初始化树
	 * @param nodeList
	 * @return
	 * 
	 */
	public static Node initNode(HashMap<Object, ? extends Node> nodeList) {
		Node root = null;
		// 构造无序的多叉树
		Set<?> entrySet = nodeList.entrySet();
		for (Iterator<?> it = entrySet.iterator(); it.hasNext();) {
			@SuppressWarnings("rawtypes")
			Node node = (Node) ((Map.Entry) it.next()).getValue();
			if (node.getParentId() == null || node.getParentId().equals("-1")) {
				root = node;
			} else {
				Node bean = (Node) nodeList.get(node.getParentId());
				if (bean.getChildren() == null) {
					// bean.children=new ArrayList<Node>();
					bean.setChildren(new ArrayList<Node>());
				}
				bean.getChildren().add(node);
			}
		}
		// 功能叶子列表

		// 构造功能叶子列表
		initializeLeafList(root);
		// 对多叉树进行横向排序
		sortChildren(root);
		return (Node) root;
	}

	// 广度优先遍历，对子节点进行横向排序
	private static void sortChildren(Node root) {
		List<Node> children = root.getChildren();
		if (children != null && children.size() != 0) {
			// 对本层节点进行排序
			Collections.sort(children, new NodePriorityComparator());
			// 对每个节点的下一层节点进行排序
			for (Iterator<Node> it = children.iterator(); it.hasNext();) {
				sortChildren(it.next());
			}
		}
	}

	private static List<Node> leafList = new ArrayList<Node>();
	// 深度优先先序遍历，构造功能叶子列表
	public static void initializeLeafList(Node root) {
		List<Node> children = root.getChildren();
		if (children == null || children.size() == 0) {
			leafList.add(root);
		} else {
			for (Iterator<Node> it = children.iterator(); it.hasNext();) {
				initializeLeafList(it.next());

			}
		}

	}

	public static Node initNode(String[] nodeList) {
		return NodeUtils.initNode(nodePackager(nodeList,0));

	}
	public static Node initNode(String[] nodeList ,int init_num) {
		return NodeUtils.initNode(nodePackager(nodeList,init_num));
		
	}

	public static HashMap<Object, Node> nodePackager(String[] info,int init_num) {
		HashMap<Object, Node> nodeList = new LinkedHashMap<Object, Node>(0);
		for (int i = init_num; i < info.length; i++) {
			Node n=new Node();
			String itemArr[] = info[i].split(":");
			n.setId(itemArr[0]);
			n.setName(itemArr[1]);
			n.setParentId(itemArr[2]);
			n.setLft(Integer.valueOf(itemArr[3]));
			n.setRgt(Integer.valueOf(itemArr[4]));
			nodeList.put(n.getId(), n);
		}

		return nodeList;
	}

	private static int count=0;
	private static Node tempNode;
	private static String id;
	private static void findNodeByID(Node root,String id){
		count++;
		for(Node node:root.getChildren()){
			if(node.getId().equals(id)){
				System.out.print("find it:" + id + " the count is " + count);
				tempNode=node;
				break;
			}else if(node.getChildren()==null || 0==node.getChildren().size()){
				continue;
			}else {
				findNodeByID(node,id);
			}
		}
	}



	/**
	 * 
	 * @description:  返回所有叶子
	 * @return
	 *
	 */
	private static List<Node> leafNode;
	public static List<Node> getAllLeaf(Node root){
		leafNode=new ArrayList<Node>();
		getLeaf(root);
		return leafNode;
	}
	private static void getLeaf(Node root){
		count++;
		for(Node node:root.getChildren()){
			if(node.getChildren()==null || 0==node.getChildren().size()){
				leafNode.add(node);
				continue;
			}else {
				getLeaf(node);
			}
		}
	}
	/**
	 * 由Node获取深度链
	 */
	private static List<Node> deapNodeList;

	public static List<Node> getDeapLink(Node root, Node node) {
		putTree2List(root);
		deapNodeList = new ArrayList<Node>();
		getDeap(node);
		deapNodeList.add(root);
		return deapNodeList;
	}

	private static void getDeap(Node tempNode) {

		for (Node node : allList) {
			if (node.getId().equals(tempNode.getParentId())) {
				deapNodeList.add(tempNode);
				getDeap(node);
			}
		}
	}

	/**
	 * 
	 * @description: 多叉树列表化
	 * @param root
	 * 
	 */
	static List<Node> allList;

	private static void putTree2List(Node root) {
		if (null == allList)
			allList = new ArrayList<Node>();
		allList.add(root);
		for (Node node : root.getChildren()) {
			if (node.getChildren() != null && 0 != node.getChildren().size()) {// 不是叶子
				putTree2List(node);
			} else
				allList.add(node);
		}
	}
}

public class Node  {


	private String id;

	private String name;

	private String parentId;

	private List<Node> children;

	private Integer lft;

	private Integer rgt;

	public String getId() {
		return id;
	}

	public void setId(String id) {
		this.id = id;
	}



	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public String getParentId() {
		return parentId;
	}

	public void setParentId(String parentId) {
		this.parentId = parentId;
	}

	public List<Node> getChildren() {
		return children;
	}

	public void setChildren(ArrayList<Node> arrayList) {
		this.children = arrayList;
	}

	public Integer getLft() {
		return lft;
	}

	public void setLft(Integer lft) {
		this.lft = lft;
	}

	public Integer getRgt() {
		return rgt;
	}

	public void setRgt(Integer rgt) {
		this.rgt = rgt;
	}




	


	
}

 import java.util.HashMap;

import java.util.LinkedHashMap;
import java.util.List;

public class NODEtest {
	public static void main(String[] args) {
		// id:text:pid:lid:rid
		String info = "1," + "1:化肥:-1:1:30," + "2:有机肥:1:2:9,"
				+ "3:无机肥:1:10:15," + "4:其他肥:1:16:27," + "5:化肥4:1:28:29,"
				+ "6:猪粪1:2:3:4," + "7:猪粪2:2:5:6," + "8:猪粪3:2:7:8,"
				+ "9:氮肥1:3:11:12," + "10:氮肥2:3:14:15," + "11:其他肥料1:4:17:18,"
				+ "12:其他肥料2:4:19:20,"
				+ "13:其他肥料3:4:21:22,"
				+ "15:NEW:14:24:25,"
				+ "14:其他肥料4:4:23:26";
		String[] infoArr = info.split(",");
		HashMap<Object, Park> nodeList = new LinkedHashMap<Object, Park>(0);
		for (int i = 1; i < infoArr.length; i++) {
			Park n = new Park();
			String itemArr[] = infoArr[i].split(":");
			// n.id=itemArr[0];
			// n.text=itemArr[1];
			// n.parentId=itemArr[2];
			// n.lft=Integer.valueOf(itemArr[3]);
			// n.rgt=Integer.valueOf(itemArr[4]);
			n.setII("i= " + i);
			n.setId(itemArr[0]);
			n.setName(itemArr[1]);
			n.setParentId(itemArr[2]);
			n.setLft(Integer.valueOf(itemArr[3]));
			n.setRgt(Integer.valueOf(itemArr[4]));
			nodeList.put(n.getId(), n);
		}

		Node node = NodeUtils.initNode(nodeList);
		String s = ((Park) node).getII();
//		NodeUtils sss = new NodeUtils();
//		Node node3 = sss.findNodeByID(node, String.valueOf(6));
		NodeUtils.getAllLeaf(node).size();
//		System.out.println(NodeUtils.getAllLeaf(node).size());
		List<Node> list=NodeUtils.getDeapLink(node, NodeUtils.findNodeByID(node, "15"));
		for (int i = 0; i < list.size(); i++) {
//			Node node2 = sss.findNodeByID(node, String.valueOf(i));
//			System.out.println(node2.getName());
			System.out.print(list.get(i).getId()+", ");
		}
		System.out.println();
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i).getName()+", ");
		}
	}
}

 

much time!!

评论

1 楼 wersion 2012-04-16  

这代码。。。