import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;


public class TreeNode {
	public int id;
	List <TreeNode>childList;
	String nodeName;
	double nodeValue;



	int ParentId;

	public void initChildTree(){
		if(this.getChildList()==null){
			this.childList = new ArrayList();
		}
	}
	//向当前节点插入node
	public void insertTree(TreeNode node){
		initChildTree();
		node.setId(++selfid);
		this.childList.add(node);
	}

	//根据节点的ParentId插入树种对应的ParentId的子节点中
	public void insertTreeByParentId(TreeNode node){
		if(node.ParentId==this.ParentId){
			node.setId(++selfid);
			this.childList.add(node);
			
		}else{
			List<TreeNode>child = this.getChildList();
			for(int i = 0;i<child.size();i++){
				child.get(i).insertTreeByParentId(node);
			}
		}

	}
　　　　　　//删除最近的节点
	public void delectNow(){
		delectById(selfid);
		selfid = selfid-1;
	}
	//根据id删除节点
	public boolean delectById(int id){
		if(this.childList==null){
			return false;
		}
		int childNum = this.getChildList().size();
		for(int i = 0;i<childNum;i++){
			if(this.getChildList().get(i).getId()==id){
				this.getChildList().remove(i);
				return true;
			}else{
				this.getChildList().get(i).delectById(id);
			}
		}
		return false;
	}
	
	
	
	
	
	
	
	
	//根据id找到树种某一个节点
	public TreeNode findTreeNodeById(int id) {
		TreeNode t =new TreeNode();
		if(this.id==id){
			return this;
		}else{
			List <TreeNode>child = this.getChildList();
			for(int i = 0;i<child.size();i++){
				
				t=child.get(i).findTreeNodeById(id);
				if(t.nodeName!=null){
					return t;
				}
			}
		}
		return t;
	}

	//将数组中每一组数据作为一列，添加到data中，attribute表示属性列
	static int selfid = 0;
	public TreeNode creatTree(TreeNode tree,List<ArrayList<Double>>data,List<String>attribute){
		if(tree==null){
			tree = new TreeNode();
			tree.setId(selfid);
			tree.setNodeName("start");
			tree.setNodeValue(0);
			tree.setChildList(new ArrayList()) ;
		}
		if(attribute.size()==0){
			return tree;
		}
		List<Double>value = http://www.mamicode.com/new ArrayList();//用于记录data第0列中不重复的属性"---"+this.getNodeName()+": "+this.getNodeValue());
		if(this.childList==null){
			return;
		}
		int childNum = this.getChildList().size();
		System.out.println(childNum);
		if(childNum==0){
			return;
		}else{
			for(int i = 0;i<childNum;i++){
				TreeNode childNode = this.getChildList().get(i);
				childNode.traverse();
			}
		}
	}

	
	//求两个节点最近的公共祖先
	public TreeNode FindParent(TreeNode node1,TreeNode node2){
		List <TreeNode>list1 = new ArrayList();
		List <TreeNode>list2 = new ArrayList();
		list1 = getAllParentNode(node1);
		list2 = getAllParentNode(node2);
		TreeNode result = new TreeNode();
		boolean flag = false;
		for(int i = 0;i<list1.size();i++){
			TreeNode temp1 = (TreeNode) list1.get(i);
			int temp1Id = temp1.getId();
			for(int j = 0;j<list2.size();j++){
				TreeNode temp2 = (TreeNode) list2.get(j);
				int temp2Id = temp2.getId();
				if(temp1Id==temp2Id){
					flag = true;
					break;
				}
				
			}
			if(flag){
				result = temp1;
				break;
			}
		}
		return result;
	}
	
	
	
	
	//得到所有父节点
	public List getAllParentNode(TreeNode node){
		List<TreeNode> Parent = new ArrayList();
		if(node.getId()==0){
			return Parent;
		}else{
		int ParentId = node.getParentId();
		TreeNode P = findTreeNodeById(ParentId);
		Parent.add(P);
		Parent.addAll(getAllParentNode(P));
		return Parent;
		}

	}
	
	//得到所有子节点
	public List getAllChildNode(TreeNode node){
		List<TreeNode> Child = new ArrayList();
		if(node.childList==null){
			return Child;
		}else{
			int childNum = node.getChildList().size();
			for(int i = 0;i<childNum;i++){
				Child.add(node.getChildList().get(i));
				Child.addAll(getAllChildNode(node.getChildList().get(i)));
			}
		return Child;
		}

	}
	//求树的深度
	public int DepthOfTree(TreeNode node){
		int childNum1 = node.getChildList().size();
		System.out.println(node.id+":   "+childNum1+"  ,"+node.getNodeName());
		if(childNum1==0){
			return 1;
		}else{
			int childNum = node.getChildList().size();
			int []Count = new int [childNum];
			for(int i = 0;i<childNum;i++){
				Count[i] = DepthOfTree(node.getChildList().get(i))+1;
			}
			int maxCount = Count[0];
			for(int i = 1;i<Count.length;i++){
				if(maxCount<Count[i]){
					maxCount = Count[i];
				}
			}
			return maxCount;
		}
	}
	
	
	
	
	
	


	public double getNodeValue() {
		return nodeValue;
	}
	public void setNodeValue(double nodeValue) {
		this.nodeValue = http://www.mamicode.com/nodeValue;>