java+树+数据结构+递归的应用

向右看齐 2022-12-01 14:29 234阅读 0赞

## 为了解决报表中不同地市的数据统计问题 ##

> \*\*\*\*\*\*\*\*\*\*\*数据统计问题，记录下树的解决方案。  
> 二叉树：二叉树的结构-有且最多有两个子节点—不符合全国地市代码的统计要求  
> 树： 所以构造一个普通的树应该可以解决。  
> 下面是自己写的实现方案，和测试方法  
> 有什么不足之处，哪位大佬看到后可以指教一下

### 树节点 ###

/* * 树节点 */
    public class Node { 
    	//数据项
    	public Long data;
    	public List<Node> nodes;
    	
    	/** * 构造方法 * @param data */
    	public Node(Long data) { 
    		this.data = data;
    	}
        /** * 添加子树 * @param tree 子树 */  
        public void addNode(Node node) {  
        	if(nodes==null){ 
        		nodes=new ArrayList<>();
        		nodes.add(node);
        	}else{ 
        		nodes.add(node);  
        	}
        }

### 树 ###

/* * 树类 */
    public class Tree { 
    	//根节点
    	public Node root;
    	/** * 为了满足业务需求初始化数的时候指定数的根节点 * 需要根据地市代码初始化不同的树 * @param root */
    	public Tree(Node root){ 
    		this.root=root;
    	}
    	/** * 删除节点 * @param value */
    	public void delte(long value) { 
    		
    	}

### 往指定节点下添加节点 ###

/** * 指定节点添加子节点 * 根节点加入子节点 * @param value */
    		public void insert(long value,long parent) { 
    			//封装节点
    			Node newNode = new Node(value);
    			Node par = new Node(parent);
    			//查找指定父节点
    			Node current=find(par,parent);
    			//给指定父节点添加节点
    			current.addNode(newNode);
    		}

### 查询指定节点 ###

/** * 递归查找指定节点 * 需要根据对象递归，所以参数为Node * @param value */
    		public Node find(long value) { 
    			Node parent = new Node(value);
    			Node curnet = find(parent, value);
    			if(curnet!=null){ 
    				System.out.println(curnet.data);
    			}else{ 
    				System.out.println("数据不存在。。。。。");
    			}
    			return curnet;
    		}
    		 /** * 递归查找指定节点 * 需要根据对象递归，所以参数为Node * @param value */
    		public Node find(Node parent,long value) { 
    			Node curnet= find(parent,true,value);
    			return curnet;
    		}
    		 /** * 递归查找指定节点 * 需要对树进行递归，所以参数为Node * flag 判断是否是跟节点 * value 查找的值 * @param value */
    		public Node find(Node parent, boolean flag, long value) { 
    		// 引用当前节点，从根节点开始
    		Node curnet = null;
    		if (flag) { 
    			curnet = root;
    			if (curnet.data != value) { 
    				// 如果value不是根节点那么查找是否是子节点
    				List<Node> currents = curnet.nodes;
    				if (currents != null && currents.size() > 0) { 
    					for (Node node : currents) { 
    						if (node.data != value) { 
    							// 如果在根节点的子节点中没有找到，那么去子节点中接着递归
    							curnet=find(node, false, value);
    							//下面的递归结束，或者找到数据，这里接着循环，
    							//为了防止找到数据后，还接着递归所有这里做下校验
    							if(curnet!=null&&curnet.data==value){ 
    								return curnet;
    							}
    						} else { 
    							// 如果在根节点的子节点中找到返回改节点
    							return curnet = node;
    						}
    					}
    				} else { 
    					// 如果查找的是根节点，那么直接返回跟节点
    					return curnet;
    				}
    			}
    		}
    		if (!flag) { 
    			// 下次递归不能再从跟节点开始,从根节点的子节点开始
    				if (parent.nodes != null) { 
    					curnet = parent;
    					// 比较查找值和当前节点的值不相等，若果存在子节点，那么接着递归子节点
    					List<Node> currents = curnet.nodes;
    					if (currents != null && currents.size() > 0) { 
    						for (Node node : currents) { 
    							if (node.data != value) { 
    								curnet=find(node, false, value);
    							} else { 
    								// 找到直接返回
    								return curnet = node;
    							}
    						}
    					}
    			}
    		}
    		return curnet;
    	}

### 遍历指定节点的所有子节点 ###

/** * 查找指定节点的所有子节点 * @param root 根结点 */  
    	    public void preOrder(long value) { 
    	    	Node parent =new Node(value);
    	    	preOrder(parent,true,value);
    	    }
    	/** * 递归遍历指定节点的所有节点 * 1、定位指定节点，需要 find 方法 * 2、递归Node数，所以需要传入对象Node * * @param root 根结点 */
    	public void preOrder(Node parent, boolean flag, long value) { 
    		Node current = parent;
    		if (flag) { 
    			// 从根节点查找到该节点
    			current = find(value);
    			System.out.println("查找的节点+++++++" + value + "+++++++");
    			flag = false;
    		}
    		if (!flag) { 
    			// 如果当前节点有子节点，递归遍历该节点的所有子节点
    			if (current.nodes != null) { 
    				for (Node child : current.nodes) { 
    					System.out.print("子节点=" + child.data);
    					preOrder(child, flag, value);
    				}
    			}
    		}
    	}

### 测试 ###

public class testTree { 
    	public static void main(String[] args) { 
    		Node node=new Node(100l);
    		Tree tree = new Tree(node);
    		long[]seconds={ 1,2,3,4,5,6,7,8,9};
    		for(long second: seconds){ 
    		//100l是根节点，添加9个子节点
    			tree.insert(second, 100l);
    				for(int i=10;i<20;i++){ 
    					//每个节点下面添加10个子节点
    					tree.insert(second*i, second);
    					//可以再添加几层
    			}
    		}
    		//遍历指定节点的所有子节点
    		tree.preOrder(100l);
    		tree.find(55l);
    	}
    }