JAvaツリーの実装

ツリーの親ノードストレージ実装

import java.util.*;
public class TreeParent<E>{
	public static class Node<T>{
		T data;
		//         
		int parent;
		public Node(){
		}
		public Node(T data){
			this.data = data;
		}
		public Node(T data , int parent){
			this.data = data;
			this.parent = parent;
		}
		public String toString(){
			return "TreeParent$Node[data=" + data + ", parent="
				+ parent + "]";
		}
	}
	private final int DEFAULT_TREE_SIZE = 100;
	private int treeSize = 0;
	//    Node[]             
	private Node<E>[] nodes;
	//     
	private int nodeNums;
	//         
	public TreeParent(E data){
		treeSize = DEFAULT_TREE_SIZE;
		nodes = new Node[treeSize];
		nodes[0] = new Node<E>(data , -1);
		nodeNums++;
	}
	//      、  treeSize   
	public TreeParent(E data ,int treeSize){
		this.treeSize = treeSize;
		nodes = new Node[treeSize];
		nodes[0] = new Node<E>(data , -1);
		nodeNums++;
	}
	//          
	public void addNode(E data , Node parent){
		for (int i = 0 ; i < treeSize ; i++){
			//         null   ，        
			if (nodes[i] == null){
				//     ，            
				nodes[i] = new Node(data , pos(parent));;
				nodeNums++;
				return;
			}
		}
		throw new RuntimeException("    ，       ");
	}
	//       。
	public boolean empty(){
		//      null
		return nodes[0] == null;
	}
	//     
	public Node<E> root(){
		//     
		return nodes[0];
	}
	//      （    ）    。
	public Node<E> parent(Node node){
		//     parent          
		return nodes[node.parent];
	}
	//      （     ）      。
	public List<Node<E>> children(Node parent){
		List<Node<E>> list = new ArrayList<Node<E>>();
		for (int i = 0 ; i < treeSize  ; i++){
			//               parent     
			if (nodes[i] != null && nodes[i].parent == pos(parent)){
				list.add(nodes[i]);
			}
		}
		return list;
	}
	//       。
	public int deep(){
		//           
		int max = 0;
		for(int i = 0 ; i < treeSize && nodes[i] != null ; i++){
			//         
			int def = 1;
			//m             
			int m = nodes[i].parent;
			//        
			while(m != -1 && nodes[m] != null){
				//         
				m = nodes[m].parent;
				def++;
			}
			if(max < def){
				max = def;
			}
		}
		//      
		return max; 
	}
	//          。
	public int pos(Node node){
		for (int i = 0 ; i < treeSize ; i++){
			//      
			if (nodes[i] == node){
				return i;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		TreeParent<String> tp = new TreeParent<String>("root");
		TreeParent.Node root = tp.root();
		System.out.println(root);
		tp.addNode("  1" , root);
		System.out.println("     :" + tp.deep());
		tp.addNode("  2" , root);
		//           
		List<TreeParent.Node<String>> nodes = tp.children(root);
		System.out.println("          ：" + nodes.get(0));
		//                  
		tp.addNode("  3" , nodes.get(0));
		System.out.println("     :" + tp.deep());
	}
}

ツリーのサブノードチェーンテーブル実装

import java.util.*;
public class TreeChild<E>
{
	private static class SonNode
	{
		//         
		private int pos;
		private SonNode next;
		public SonNode(int pos , SonNode next)
		{
			this.pos = pos;
			this.next = next;
		}
	}
	public static class Node<T>
	{
		T data;
		//        
		SonNode first;
		public Node(T data)
		{
			this.data = data;
			this.first = null;
		}
		public String toString()
		{
			if (first != null)
			{
				return "TreeChild$Node[data=" + data + ", first="
					+ first.pos + "]";
			}
			else
			{
				return "TreeChild$Node[data=" + data + ", first=-1]";
			}
		}
	}
	private final int DEFAULT_TREE_SIZE = 100;
	private int treeSize = 0;
	//    Node[]             
	private Node<E>[] nodes;
	//     
	private int nodeNums;
	//         
	public TreeChild(E data)
	{
		treeSize = DEFAULT_TREE_SIZE;
		nodes = new Node[treeSize];
		nodes[0] = new Node<E>(data);
		nodeNums++;
	}
	//      、  treeSize   
	public TreeChild(E data ,int treeSize)
	{
		this.treeSize = treeSize;
		nodes = new Node[treeSize];
		nodes[0] = new Node<E>(data);
		nodeNums++;
	}
	//          
	public void addNode(E data , Node parent)
	{
		for (int i = 0 ; i < treeSize ; i++)
		{
			//         null   ，        
			if (nodes[i] == null)
			{
				//     ，            
				nodes[i] = new Node(data);
				if (parent.first == null)
				{
					parent.first = new SonNode(i , null);
				}
				else
				{
					SonNode next = parent.first;
					while (next.next != null)
					{
						next = next.next;
					}
					next.next = new SonNode(i , null);
				}
				nodeNums++;
				return;
			}
		}
		throw new RuntimeException("    ，       ");
	}
	//       。
	public boolean empty()
	{
		//      null
		return nodes[0] == null;
	}
	//     
	public Node<E> root()
	{
		//     
		return nodes[0];
	}
	//      （     ）      。
	public List<Node<E>> children(Node parent)
	{
		List<Node<E>> list = new ArrayList<Node<E>>();
		//  parent         
		SonNode next = parent.first;
		//                
		while (next != null)
		{
			//         
			list.add(nodes[next.pos]);
			next = next.next;
		}
		return list;
	}
	//      （     ）  index    。
	public Node<E> child(Node parent , int index)
	{
		//  parent         
		SonNode next = parent.first;
		//                
		for (int i = 0 ; next != null  ; i++)
		{
			if (index == i)
			{
				return nodes[next.pos];
			}
			next = next.next;
		}
		return null;
	}
	//       。
	public int deep()
	{
		//       
		return deep(root()); 
	}
	//        ：                   + 1
	private int deep(Node node)
	{
		if (node.first == null)
		{
			return 1;
		}
		else
		{
			//            
			int max = 0;
			SonNode next = node.first;
			//                
			while (next != null)
			{
				//               
				int tmp = deep(nodes[next.pos]);
				if (tmp > max)
				{
					max = tmp;
				}
				next = next.next;
			}
			//               + 1
			return max + 1;
		}
	}
	//          。
	public int pos(Node node)
	{
		for (int i = 0 ; i < treeSize ; i++)
		{
			//      
			if (nodes[i] == node)
			{
				return i;
			}
		}
		return -1;
	}
	
	public static void main(String[] args) 
	{
		TreeChild<String> tp = new TreeChild<String>("root");
		TreeChild.Node root = tp.root();
		System.out.println("   ：" + root);
		tp.addNode("  1" , root);
		tp.addNode("  2" , root);
		tp.addNode("  3" , root);
		System.out.println("          ：" + root);
		System.out.println("     :" + tp.deep());
		//           
		List<TreeChild.Node<String>> nodes = tp.children(root);
		System.out.println("          ：" + nodes.get(0));
		//                  
		tp.addNode("  4" , nodes.get(0));
		System.out.println("          ：" + nodes.get(0));
		System.out.println("     :" + tp.deep());
	}
}