ArrayBinTree<String> binTree = new ArrayBinTree<String>(4, "根");
binTree.add(0, "第二层右子节点", false);
binTree.add(2, "第三层右子节点", false);
binTree.add(6, "第四层右子节点", false);
System.out.println(binTree);
}
}
程序输出：
[根, null, 第二层右子节点, null, null, null, 第三层右子节点, null, null, null, null, null, null, null, 第四层右子节点]
三、二叉树的二叉链表存储
二叉链表存储的思想是让每个节点都能“记住”它的左、右两个子节点。为每个节点增加left、right两个指针，分别引用该节点的左、右两个子节点。
package com.ietree.basic.datastructure.tree.binarytree;
/**
* Created by ietree
* 2017/5/1
*/
public class TwoLinkBinTree<E> {
public static class TreeNode {
Object data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(Object data) {
this.data = data;
}
public TreeNode(Object data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
private TreeNode root;
// 以默认的构造器创建二叉树
public TwoLinkBinTree() {
this.root = new TreeNode();
}
// 以指定根元素创建二叉树
public TwoLinkBinTree(E data) {
this.root = new TreeNode(data);
}
/**
* 为指定节点添加子节点
*
* @param parent 需要添加子节点的父节点的索引
* @param data 新子节点的数据
* @param isLeft 是否为左节点
* @return 新增的节点
*/
public TreeNode addNode(TreeNode parent, E data, boolean isLeft) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null， 无法添加子节点");
}
if (isLeft && parent.left != null) {
throw new RuntimeException(parent + "节点已有左子节点，无法添加左子节点");
}
if (!isLeft && parent.right != null) {
throw new RuntimeException(parent + "节点已有右子节点，无法添加右子节点");
}
TreeNode newNode = new TreeNode(data);
if (isLeft) {
// 让父节点的left引用指向新节点
parent.left = newNode;
} else {
// 让父节点的left引用指向新节点
parent.right = newNode;
}
return newNode;
}
// 判断二叉树是否为空
public boolean empty() {
// 根据元素判断二叉树是否为空
return root.data == null;
}
// 返回根节点
public TreeNode root() {
if (empty()) {
throw new RuntimeException("树为空，无法访问根节点");
}
return root;
}
// 返回指定节点（非根节点）的父节点
public E parent(TreeNode node) {
// 对于二叉树链表存储法，如果要访问指定节点的父节点必须遍历二叉树
return null;
}
// 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null
public E leftChild(TreeNode parent) {
if (parent == null) {
throw new RuntimeException(parent + "节点为null，无法添加子节点");
}
return parent.left == null ? null : (E) parent.left.data;
}