首页 > 代码库 > Java中二叉树存储结构实现
Java中二叉树存储结构实现
一、二叉树
二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称为“左子树”(left subtree),右边的子树被称为右子树。
二叉树的每个节点最多只有2棵子树,二叉树的子树次序不能颠倒。
二、顺序存储二叉树的实现
1 package com.ietree.basic.datastructure.tree.binarytree; 2 3 /** 4 * Created by ietree 5 * 2017/5/1 6 */ 7 public class ArrayBinTree<T> { 8 9 // 使用数组来记录该树的所有节点 10 private Object[] datas; 11 private int DEFAULT_DEEP = 8; 12 // 保存该树的深度 13 private int deep; 14 private int arraySize; 15 16 // 以默认的深度创建二叉树 17 public ArrayBinTree() { 18 this.deep = DEFAULT_DEEP; 19 this.arraySize = (int) (Math.pow(2, deep) - 1); 20 datas = new Object[arraySize]; 21 } 22 23 // 以指定深度创建二叉树 24 public ArrayBinTree(int deep) { 25 this.deep = deep; 26 this.arraySize = (int) Math.pow(2, deep) - 1; 27 datas = new Object[arraySize]; 28 } 29 30 // 以指定深度、指定节点创建二叉树 31 public ArrayBinTree(int deep, T data) { 32 this.deep = deep; 33 this.arraySize = (int) Math.pow(2, deep) - 1; 34 datas = new Object[arraySize]; 35 datas[0] = data; 36 } 37 38 /** 39 * 为指定节点添加子节点 40 * 41 * @param index 需要添加子节点的父节点的索引 42 * @param data 新子节点的数据 43 * @param left 是否为左节点 44 */ 45 public void add(int index, T data, boolean left) { 46 if (datas[index] == null) { 47 throw new RuntimeException(index + "处节点为空,无法添加子节点"); 48 } 49 if (2 * index + 1 >= arraySize) { 50 throw new RuntimeException("树底层的数组已满,树越界异常"); 51 } 52 // 添加左子节点 53 if (left) { 54 datas[2 * index + 1] = data; 55 } else { 56 datas[2 * index + 2] = data; 57 } 58 } 59 60 // 判断二叉树是否为空 61 public boolean empty() { 62 // 根据根元素判断二叉树是否为空 63 return datas[0] == null; 64 } 65 66 // 返回根节点 67 public T root() { 68 return (T) datas[0]; 69 } 70 71 // 返回指定节点(非根结点)的父节点 72 public T parent(int index) { 73 return (T) datas[(index - 1) / 2]; 74 } 75 76 // 返回指定节点(非叶子)的左子节点,当左子节点不存在时返回null 77 public T left(int index) { 78 if (2 * index + 1 >= arraySize) { 79 throw new RuntimeException("该节点为叶子节点,无子节点"); 80 } 81 return (T) datas[index * 2 + 1]; 82 } 83 84 // 返回指定节点(非叶子)的右子节点,当右子节点不存在时返回null 85 public T right(int index) { 86 if (2 * index + 1 >= arraySize) { 87 throw new RuntimeException("该节点为叶子节点,无子节点"); 88 } 89 return (T) datas[index * 2 + 2]; 90 } 91 92 // 返回该二叉树的深度 93 public int deep(int index) { 94 return deep; 95 } 96 97 // 返回指定节点的位置 98 public int pos(T data) { 99 // 该循环实际上就是按广度遍历来搜索每个节点 100 for (int i = 0; i < arraySize; i++) { 101 if (datas[i].equals(data)) { 102 return i; 103 } 104 105 } 106 return -1; 107 } 108 109 public String toString() { 110 return java.util.Arrays.toString(datas); 111 } 112 113 }
测试类:
1 package com.ietree.basic.datastructure.tree.binarytree; 2 3 /** 4 * Created by ietree 5 * 2017/5/1 6 */ 7 public class ArrayBinTreeTest { 8 9 public static void main(String[] args) { 10 11 ArrayBinTree<String> binTree = new ArrayBinTree<String>(4, "根"); 12 binTree.add(0, "第二层右子节点", false); 13 binTree.add(2, "第三层右子节点", false); 14 binTree.add(6, "第四层右子节点", false); 15 System.out.println(binTree); 16 17 } 18 19 }
程序输出:
[根, null, 第二层右子节点, null, null, null, 第三层右子节点, null, null, null, null, null, null, null, 第四层右子节点]
三、二叉树的二叉链表存储
四、二叉树的三叉链表存储
Java中二叉树存储结构实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。