공통 트 리

package com.test.me;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.locks.ReentrantLock;

public class Tree {
	
	class TreeNode {
		private TreeNode parent;
		private volatile Set children;
		private T attachment;

		public TreeNode(T attach) {
			attachment = attach;
		}

		@Override
		public int hashCode() {
			return attachment.hashCode();
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			TreeNode other = (TreeNode) obj;
			if (attachment == null) {
				if (other.attachment != null)
					return false;
			} else if (!attachment.equals(other.attachment))
				return false;
			return true;
		}
	}

	public Tree(T attach) {
		this.root = new TreeNode(attach);
	}

	private TreeNode root;

	private ReentrantLock lock = new ReentrantLock();

	public T getRoot() {
		return root.attachment;
	}

	/**
	 *  parent        ,
	 *
	 * @return   parent     ,        tree ，       true
	 */
	public boolean addchild(T parent, T attachment) {
		TreeNode parentNode = findTreeNode(parent);

		//   attachment       
		if (parentNode != null) {

			//   children List ，      
			if (parentNode.children == null) {
				try {
					lock.lock();
					if (parentNode.children == null) {
						parentNode.children = Collections.synchronizedSet(new HashSet());
					}
				} finally {
					lock.unlock();
				}
			}

			TreeNode node = new TreeNode(attachment);
			node.parent = parentNode;
			
			return parentNode.children.add(node);
		}
		return false;
	}

	/**
	 *                  true.
	 *             。          ，    
	 * @param       
	 *            ，   true      ;false，   child      
	 * */
	protected boolean remove(T attachment, boolean cascade) {
		TreeNode node = findTreeNode(attachment);
		if (node != null) {
			//          ，       ，   false
			if (!cascade && node.children != null && node.children.size() > 0) {
				return false;
			}
			TreeNode parent = node.parent;
			return parent.children.remove(node);
		} else {
			return false;
		}
	}

	/**
	 *   node       
	 */
	public List getDescendants(T attachment) {
		TreeNode node = findTreeNode(attachment);
		if (node != null) {
			List list = new ArrayList();
			Stack set = new Stack();
			if(node.children!=null && node.children.size()>0)
			{
				for (TreeNode children : node.children) {
					set.push(children);
				}
			}
			//                 
			while (!set.isEmpty()) {
				TreeNode cur = set.pop();
				list.add(cur.attachment);

				if (cur.children != null && cur.children.size() > 0) {
					for (TreeNode children : cur.children) {
						set.push(children);
					}
				}
			}

			return list;
		}
		return null;
	}

	/**
	 *         。 root    ，    root
	 * */
	public List getAncestors(T attach) {
		TreeNode node = findTreeNode(attach);
		if (node != null && node.parent!=null) {
			List list = new ArrayList();
			TreeNode cur = node.parent;
			while (cur != root && cur != null) {
				list.add(cur.attachment);
				cur = cur.parent;
			}
			//   root
			if (cur == root) {
				list.add(root.attachment);
				Collections.reverse(list);
				return list;
			} else {
				return null;
			}
		} else {
			return null;
		}
	}

	/**
	 *     ,       
	 */
	public List getChild(T attachment) {
		TreeNode node = findTreeNode(attachment);
		if (node != null && node.children!=null) {
			List list = new ArrayList();
			
			for(TreeNode child : node.children)
			{
				list.add(child.attachment);
			}
			return list;
		}
		return null;
		
	}

	/**
	 *       。
	 */
	public T getFather(T attachment) {
		TreeNode node = findTreeNode(attachment);
		if (node != null && node != this.root) {
			return node.parent.attachment;
		}
		return null;
	}
	
	/**
	 *     ，         ，    null
	 * */
	private TreeNode findTreeNode(T attachment) {

		Stack set = new Stack();
		set.push(root);

		//       tree
		TreeNode cur = root;
		while ((!set.empty()) && attachment != cur.attachment && (!attachment.equals(cur.attachment))) {
			cur = set.pop();
			if (cur.children != null && cur.children.size() > 0) {
				for (TreeNode children : cur.children) {
					set.push(children);
				}
			}
		}

		if (attachment.equals(cur.attachment)) {
			return cur;
		} else {
			return null;
		}
	}
}