데이터 구조: 이 진 트 리 의 세 갈래 링크 저장 - 자바 구현

public class ThreeLinkTree<E> {
	//      
	public static class TreeNode {
		Object data;
		TreeNode left;
		TreeNode right;
		TreeNode parent;

		public TreeNode(Object data) {
			this.data = data;
		}

		public TreeNode(Object data, TreeNode left, TreeNode right,
				TreeNode parent) {
			this.data = data;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}

		public TreeNode() {

		}
	}

	// root
	private TreeNode root;

	//          
	public ThreeLinkTree() {
		root = new TreeNode();
	}

	//          
	public ThreeLinkTree(E data) {
		root = new TreeNode(data);
	}

	//          
	public boolean empty() {
		return root == null;
	}

	//      
	public TreeNode getRoot() {
		if (empty()) {
			throw new RuntimeException("    ");
		} else {
			return root;
		}
	}

	//           
	public E leftChild(TreeNode node) {
		if (node == null) {
			throw new RuntimeException("     ");
		}
		return node.left == null ? null : (E) node.left.data;
	}

	//           
	public E rightChild(TreeNode node) {
		if (node == null) {
			throw new RuntimeException("     ");
		}
		return node.right == null ? null : (E) node.right.data;
	}

	//           
	public E parent(TreeNode node) {
		if (node == null) {
			throw new RuntimeException("     ");
		}
		return (E) node.parent.data;
	}

	//          
	public TreeNode addNote(TreeNode parent, E data, boolean isleft) {
		if (parent == null) {
			throw new RuntimeException("       ，     ");
		}
		if (isleft && parent.left != null) {
			throw new RuntimeException("        ，    ");
		}
		if (!isleft && parent.right != null) {
			throw new RuntimeException("        ，    ");
		}
		TreeNode newNode = new TreeNode(data);
		if (isleft) {
			parent.left = newNode;
		} else {
			parent.right = newNode;
		}
		newNode.parent = parent;
		return newNode;
	}

	//         
	public int deepin() {
		return deepin(root);
	}

	//             
	public int deepin(TreeNode node) {
		if (node == null) {
			return 0;
		}
		if (node.left == null && node.right == null) {
			return 1;
		} else {
			int leftdeep = deepin(node.left);
			int rightdeep = deepin(node.right);
			int max = (leftdeep > rightdeep ? leftdeep : rightdeep);
			return max + 1;
		}
	}

}