public class ThreeLinkTree {
// 内部节点类
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;
}
}
}
