【code】java二叉树的实现
二叉树的顺序存储
public class ArrayBinTree<T>{//使用数组来记录该树的所有节点private Object[] datas;private int DEFAULT_DEEP = 8;//保存该树的深度private int deep;private int arraySize;//以默认的深度来创建二叉树public ArrayBinTree(){this.deep = DEFAULT_DEEP;this.arraySize = (int)Math.pow(2 , deep) - 1;datas = new Object[arraySize];}//以指定深度来创建二叉树public ArrayBinTree(int deep){this.deep = deep;this.arraySize = (int)Math.pow(2 , deep) - 1;datas = new Object[arraySize];}//以指定深度,指定根节点创建二叉树public ArrayBinTree(int deep , T data){this.deep = deep;this.arraySize = (int)Math.pow(2 , deep) - 1;datas = new Object[arraySize];datas[0] = data;}/** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param left 是否为左节点 */public void add(int index , T data , boolean left){if (datas[index] == null){throw new RuntimeException(index + "处节点为空，无法添加子节点");}if (2 * index + 1 >= arraySize){throw new RuntimeException("树底层的数组已满，树越界异常");}//添加左子节点if (left){datas[2 * index + 1] = data;}else{datas[2 * index + 2] = data;}}//判断二叉树是否为空。public boolean empty(){//根据根元素来判断二叉树是否为空return datas[0] == null;}//返回根节点。public T root(){return (T)datas[0] ;}//返回指定节点（非根节点）的父节点。public T parent(int index){return (T)datas[(index - 1) / 2] ;}//返回指定节点（非叶子）的左子节点。当左子节点不存在时返回nullpublic T left(int index){if (2 * index + 1 >= arraySize){throw new RuntimeException("该节点为叶子节点，无子节点");}return (T)datas[index * 2 + 1] ;}//返回指定节点（非叶子）的右子节点。当右子节点不存在时返回nullpublic T right(int index){if (2 * index + 1 >= arraySize){throw new RuntimeException("该节点为叶子节点，无子节点");}return (T)datas[index * 2 + 2] ;}//返回该二叉树的深度。public int deep(int index){return deep;}//返回指定节点的位置。public int pos(T data){//该循环实际上就是按广度遍历来搜索每个节点for (int i = 0 ; i < arraySize ; i++){if (datas[i].equals(data)){return i;}}return -1;}public String toString(){return java.util.Arrays.toString(datas);}public static void main(String[] args) {ArrayBinTree<String> binTree = new ArrayBinTree<String>(4, "根");binTree.add(0 , "第二层右子节点" , false);//是从0位置开始binTree.add(2 , "第三层右子节点" , false);binTree.add(6 , "第四层右子节点" , false);System.out.println(binTree);}}?二叉树的链表存储
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 index 需要添加子节点的父节点的索引 * @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;}//返回指定节点（非叶子）的左子节点。当左子节点不存在时返回nullpublic E leftChild(TreeNode parent){if (parent == null){throw new RuntimeException(parent +"节点为null，无法添加子节点");}return parent.left == null ? null : (E)parent.left.data;}//返回指定节点（非叶子）的右子节点。当右子节点不存在时返回nullpublic 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); }//这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1private 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;//返回其左右子树中较大的深度 + 1return max + 1;}}public static void main(String[] args) { TwoLinkBinTree<String> binTree = new TwoLinkBinTree("根节点");//依次添加节点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()); }}?二叉树的三叉链表存储
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);}/** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @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;}//让新节点的parent引用到parent节点newNode.parent = parent;return newNode;}//判断二叉树是否为空。public boolean empty(){//根据根元素来判断二叉树是否为空return root.data == null;}//返回根节点。public TreeNode root(){if (empty()){throw new RuntimeException("树为空，无法访问根节点");}return root;}//返回指定节点（非根节点）的父节点。public E parent(TreeNode node){if (node == null){throw new RuntimeException(node +"节点为null，无法访问其父节点");}return (E)node.parent.data;}//返回指定节点（非叶子）的左子节点。当左子节点不存在时返回nullpublic E leftChild(TreeNode parent){if (parent == null){throw new RuntimeException(parent +"节点为null，无法添加子节点");}return parent.left == null ? null : (E)parent.left.data;}//返回指定节点（非叶子）的右子节点。当右子节点不存在时返回nullpublic 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); }//这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1private 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;//返回其左右子树中较大的深度 + 1return max + 1;}}public static void main(String[] args) { ThreeLinkBinTree<String> binTree = new ThreeLinkBinTree("根节点");//依次添加节点ThreeLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root(), "第二层左节点" , true);ThreeLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root(), "第二层右节点" ,false );ThreeLinkBinTree.TreeNode tn3 = binTree.addNode(tn2 , "第三层左节点" , true);ThreeLinkBinTree.TreeNode tn4 = binTree.addNode(tn2, "第三层右节点" , false);ThreeLinkBinTree.TreeNode tn5 = binTree.addNode(tn3, "第四层左节点" , true);System.out.println("tn2的父节点：" + binTree.parent(tn2));System.out.println("tn2的左子节点：" + binTree.leftChild(tn2));System.out.println("tn2的右子节点：" + binTree.rightChild(tn2));System.out.println(binTree.deep()); }}?