// 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null
public E rightChild(TreeNode parent) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
return parent.right == null ? null : (E) parent.right.data;
}
// 返回该二叉树的深度
public int deep() {
// 获取该树的深度
return deep(root);
}
// 这是一个递归方法：每一棵子树的深度为其所有子树的最大深度 + 1
private int deep(TreeNode node) {
if (node == null) {
return 0;
}
// 没有子树
if (node.left == null && node.right == null) {
return 1;
} else {
int leftDeep = deep(node.left);
int rightDeep = deep(node.right);
// 记录其所有左、右子树中较大的深度
int max = leftDeep > rightDeep ? leftDeep : rightDeep;
// 返回其左右子树中较大的深度 + 1
return max + 1;
}
}
}
测试类：
package com.ietree.basic.datastructure.tree.binarytree;
/**
* Created by ietree
* 2017/5/1
*/
public class TwoLinkBinTreeTest {
public static void main(String[] args) {
TwoLinkBinTree<String> binTree = new TwoLinkBinTree<String>("根节点");
// 依次添加节点
TwoLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root(), "第二层左节点", true);
TwoLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root(), "第二层右节点", false);
TwoLinkBinTree.TreeNode tn3 = binTree.addNode(tn2, "第三层左节点", true);
TwoLinkBinTree.TreeNode tn4 = binTree.addNode(tn2, "第三层右节点", false);
TwoLinkBinTree.TreeNode tn5 = binTree.addNode(tn3, "第四层左节点", true);
System.out.println("tn2的左子节点：" + binTree.leftChild(tn2));
System.out.println("tn2的右子节点：" + binTree.rightChild(tn2));
System.out.println(binTree.deep());
}
}
程序输出：
tn2的左子节点：第三层左节点
tn2的右子节点：第三层右节点
4
四、二叉树的三叉链表存储
三叉链表存储方式是对二叉链表的一种改进，通过为树节点增加一个parent引用，可以让每个节点都能非常方便的访问其父节点，三叉链表存储的二叉树即可方便地向下访问节点，也可方便地向上访问节点。
package com.ietree.basic.datastructure.tree.binarytree;
/**
* Created by ietree
* 2017/5/1
*/
public class ThreeLinkBinTree<E> {
public static class TreeNode {
Object data;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode() {
}
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;
}
}
private TreeNode root;
// 以默认的构造器创建二叉树
public ThreeLinkBinTree() {
this.root = new TreeNode();
}
// 以指定根元素创建二叉树
public ThreeLinkBinTree(E data) {
this.root = new TreeNode(data);
}