Java中二叉树存储结构达成
发布时间:2021-12-08 20:13:29 所属栏目:PHP教程 来源:互联网
导读:一、二叉树 二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称为左子树(left subtree),右边的子树被称为右子树。 二叉树的每个节点最多只有2棵子树,二叉树的子树次序不能颠倒。 二、顺序存储二叉树的实现 package com.ietree.basic.d
一、二叉树 二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称为“左子树”(left subtree),右边的子树被称为右子树。 二叉树的每个节点最多只有2棵子树,二叉树的子树次序不能颠倒。 二、顺序存储二叉树的实现 package com.ietree.basic.datastructure.tree.binarytree; /** * Created by ietree * 2017/5/1 */ 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]; } // 返回指定节点(非叶子)的左子节点,当左子节点不存在时返回null public T left(int index) { if (2 * index + 1 >= arraySize) { throw new RuntimeException("该节点为叶子节点,无子节点"); } return (T) datas[index * 2 + 1]; } // 返回指定节点(非叶子)的右子节点,当右子节点不存在时返回null public 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); } } 测试类: package com.ietree.basic.datastructure.tree.binarytree; /** * Created by ietree * 2017/5/1 */ public class ArrayBinTreeTest { public static void main(String[] args) { 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; } // 返回指定节点(非叶子)的右子节点,当右子节点不存在时返回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); } /** * 为指定节点添加子节点 * * @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; } // 让新节点的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("节点为null,无法访问其父节点"); } return (E) node.parent.data; } // 返回指定节点(非叶子)的左子节点,当左子节点不存在时返回null public E leftChild(TreeNode parent) { if (parent == null) { throw new RuntimeException(parent + "节点为null,无法添加子节点"); } return parent.left == null ? null : (E) parent.left.data; } // 返回指定节点(非叶子)的右子节点,当右子节点不存在时返回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 ThreeLinkBinTreeTest { public static void main(String[] args) { ThreeLinkBinTree<String> binTree = new ThreeLinkBinTree<String>("根节点"); // 依次添加节点 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.leftChild(tn2)); System.out.println("tn2的右子节点:" + binTree.rightChild(tn2)); System.out.println(binTree.deep()); } } 程序输出: tn2的左子节点:第三层左节点 tn2的右子节点:第三层右节点 4 (编辑:云计算网_泰州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |