首页 > 代码库 > 多叉树的建立以及其他的一些操作

多叉树的建立以及其他的一些操作

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;>

 

多叉树的建立以及其他的一些操作