精华内容
下载资源
问答
  • Java 实现树结构
    千次阅读
    2021-02-12 09:34:11

    树是一种非常重要的数据结构,其中二叉树是最常用到的,之前学的时候用的都是c++,很长时间没有用了也忘得差不多了,最近一直都在用Java,所以总结一下怎样用java来实现二叉树的数据结构,用二叉树来存一个数组。

    二叉树得特点有以下几个:1. 每个节点最多有两棵子树。2. 左子树和右子树是有顺序的,次序不能任意颠倒。3. 即使树中只有一课子树,也要区分他是左子树还是右子树;

    二叉树的遍历:是指从根结点出发,按照某种次序,依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次;二叉树的遍历方式有好多种,如果我们限制了从左到右的习惯方式,那么主要就有以下几种:前序遍历,中序遍历,后序遍历和层序遍历。

    二叉树的实现:二叉树也可以通过顺序存储和链式存储来实现;

    二叉树的顺序存储就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如父结点与子结点的逻辑关系,子结点与子结点之间的关系;但顺序存储的实用性不强;所以一般采用链式存储;

    在Java中,采用类来声明树的节点 如下所示

    public class Node

    {

    private char

    key;  //

    数据

    private Node

    left, right;  //

    左右子结点

    public

    Node(char key)

    {

    this(key, null, null);

    }

    public

    Node(char key, Node left, Node right)

    {

    this.key = key;

    this.left = left;

    this.right = right;

    }

    public char

    getKey()

    {

    return key;

    }

    public void

    setKey(char key)

    {

    this.key = key;

    }

    public Node

    getLeft()

    {

    return left;

    }

    public void

    setLeft(Node left)

    {

    this.left = left;

    }

    public Node

    getRight()

    {

    return right;

    }

    public void

    setRight(Node right)

    {

    this.right = right;

    }

    }

    接下来就是创建一个二叉树,以及对二叉树进行前序遍历,中序遍历,后序遍历和层序遍历。

    public class Tree

    {

    protected

    Node root;

    public

    Tree(Node root)

    {

    this.root = root;

    }

    public Node

    getRoot()

    {

    return root;

    }

    //

    初始化,构造二叉树

    public

    static Node init()

    {

    Node a = new Node('A');

    Node b = new Node('B', null,

    a);

    Node c = new Node('C');

    Node d = new Node('D', b, c);

    Node e = new Node('E');

    Node f = new Node('F', e,

    null);

    Node g = new Node('G', null,

    f);

    Node h = new Node('H', d, g);

    return h;  //

    根结点

    }

    //

    访问节点

    public

    static void visit(Node p)

    {

    System.out.print(p.getKey() +

    " ");

    }

    //

    递归实现前序遍历

    protected

    static void preorder(Node p)

    {

    if (p != null)

    {

    visit(p);

    preorder(p.getLeft());

    preorder(p.getRight());

    }

    }

    //

    递归实现中序遍历

    protected

    static void inorder(Node p)

    {

    if (p != null)

    {

    inorder(p.getLeft());

    visit(p);

    inorder(p.getRight());

    }

    }

    //

    递归实现后序遍历

    protected

    static void postorder(Node p)

    {

    if (p != null)

    {

    postorder(p.getLeft());

    postorder(p.getRight());

    visit(p);

    }

    }

    //

    非递归实现前序遍历

    protected

    static void iterativePreorder(Node p)

    {

    Stack stack = new Stack();

    if (p != null)

    {

    stack.push(p);

    while (!stack.empty())

    {

    p =

    stack.pop();

    visit(p);

    if

    (p.getRight() != null)

    stack.push(p.getRight());

    if

    (p.getLeft() != null)

    stack.push(p.getLeft());

    }

    }

    }

    //

    非递归实现后序遍历

    protected

    static void iterativePostorder(Node p)

    {

    Node q = p;

    Stack stack = new Stack();

    while (p != null)

    {

    // 左子树入栈

    for (; p.getLeft() != null; p = p.getLeft())

    stack.push(p);

    // 当前结点无右子结点或右子结点已经输出

    while (p != null && (p.getRight() ==

    null || p.getRight() == q))

    {

    visit(p);

    q = p;

    // 记录上一个已输出结点

    if

    (stack.empty())

    return;

    p =

    stack.pop();

    }

    // 处理右子结点

    stack.push(p);

    p = p.getRight();

    }

    }

    //

    非递归实现中序遍历

    protected

    static void iterativeInorder(Node p)

    {

    Stack stack = new Stack();

    while (p != null)

    {

    while (p != null)

    {

    if

    (p.getRight() != null)

    stack.push(p.getRight());

    // 当前结点右子结点入栈

    stack.push(p);  // 当前结点入栈

    p =

    p.getLeft();

    }

    p = stack.pop();

    while (!stack.empty() && p.getRight() ==

    null)

    {

    visit(p);

    p =

    stack.pop();

    }

    visit(p);

    if (!stack.empty())

    p =

    stack.pop();

    else

    p = null;

    }

    }

    }

    更多相关内容
  • java版数据结构-树结构java版数据结构-树结构java版数据结构-树结构java版数据结构-树结构java版数据结构-树结构java版数据结构-树结构
  • java树结构递归查询

    2018-09-04 17:24:08
    //组装类目为树结构 assembleTree(categoryTreeDTO, allDTOList,Constants.CATEGORY_MAX_LEVEL - level); } return categoryTree; } /** * 组装树 * * @param categoryTreeDTO * @param allList ...
  • Java递归遍历结构

    2020-09-02 16:42:25
    主要介绍了Java递归遍历结构的相关资料,需要的朋友可以参考下
  • java根据过滤条件显示结构,其中包括所需要的jar包
  • 基于JAVA建立结构的算法优化.pdf
  • Javatree java树结构

    2009-11-28 18:59:54
    关于Java的一个树结构,类似于本论坛左侧的样式,对初学者有一定的帮助
  • java 树结构数据类型In this article, we will learn about tree and some of the common types of trees in data structure. 在本文中,我们将学习树以及数据结构中一些常见的树类型。 Tree in computer science ...

    java 树结构数据类型

    In this article, we will learn about tree and some of the common types of trees in data structure.

    在本文中,我们将学习树以及数据结构中一些常见的树类型。

    Tree in computer science is like a tree in the real world, the only difference is that in computer science it is visualized as upside-down with root on the top and branches originating from the root to the leaves of the tree. Tree Data Structure is used for various real-world applications as it can show relation among various nodes using the parent-child hierarchy. Due to this it is also known as hierarchical data structure. It is widely used to simplify and fasten searching and sorting operations. It is considered to be one of the most powerful and advanced data structures.

    计算机科学中的树就像现实世界中的一棵树,唯一的区别是计算机科学中的树是倒置的,其根在顶部,而分支从树的根部到叶部。 树数据结构可用于各种实际应用程序,因为它可以使用父子层次结构显示各种节点之间的关系。 因此,它也被称为分层数据结构。 它被广泛用于简化和加快搜索和排序操作。 它被认为是最强大和最先进的数据结构之一。

    Tree is a non-linear data structure. A tree can be represented using various primitive or user defined data types. To implement tree, we can make use of arrays, linked lists, classes or other types of data structures. It is a collection of nodes that are related with each other. To show the relation, nodes are connected with edges.

    树是一种非线性数据结构。 可以使用各种原始或用户定义的数据类型来表示树。 为了实现树,我们可以利用数组,链表,类或其他类型的数据结构。 它是彼此相关的节点的集合。 为了显示这种关系,节点与边连接。

    General Tree Structure

    Fig 1: General Tree structure (Source)

    图1:常规树结构( )

    Relations in a Tree:

    树中的关系:

    • A is the root of the tree

      A是树的根
    • A is Parent of B, C and D

      A是B,C和D的父母
    • B is child of A

      B是A的孩子
    • B, C and D are siblings

      B,C和D是兄弟姐妹
    • A is grand-parent of E, F, G, H and I

      A是E,F,G,H和I的祖父母

    Properties of Tree:

    树的属性:

    • Every tree has a special node called the root node. The root node can be used to traverse every node of the tree. It is called root because the tree originated from root only.

      每棵树都有一个称为根节点的特殊节点。 根节点可用于遍历树的每个节点。 之所以称为根,是因为该树仅起源于根。
    • If a tree has N vertices(nodes) than the number of edges is always one less than the number of nodes(vertices) i.e N-1. If it has more than N-1 edges it is called a graph not a tree.

      如果一棵树有N个顶点(节点),则边数总是比节点(顶点)的数量少1,即N-1。 如果它有N-1个以上的边,则称为图而不是树。
    • Every child has only a single Parent but Parent can have multiple child.

      每个孩子只有一个父母,但父母可以有多个孩子。

    数据结构中的树类型 (Types of Trees in Data Structure)

    普通树 (General Tree)

    A tree is called a general tree when there is no constraint imposed on the hierarchy of the tree.  In General Tree, each node can have infinite number of children. This tree is the super-set of all other types of trees. The tree shown in Fig 1 is a General Tree.

    当树的层次结构上没有任何限制时,该树称为普通树。 在“通用树”中,每个节点可以具有无限数量的子代。 该树是所有其他类型树的超集。 图1所示的树是通用树。

    二叉树 (Binary Tree)

    Binary tree is the type of tree in which each parent can have at most two children. The children are referred to as left child or right child. This is one of the most commonly used trees. When certain constraints and properties are imposed on Binary tree it results in a number of other widely used trees like BST (Binary Search Tree), AVL tree, RBT tree etc. We will see all these types in details as we move ahead.

    二叉树是每个父母最多可以有两个孩子的树的类型。 这些孩子被称为左孩子或右孩子。 这是最常用的树之一。 当对Binary树施加某些约束和属性时,它会导致许多其他广泛使用的树,例如BST(二进制搜索树),AVL树,RBT树等。随着我们的前进,我们将详细了解所有这些类型。

    Binary Tree

    Fig 2: Binary Tree (Source)

    无花果2:二叉树( 来源 )

    二进制搜索树 (Binary Search Tree)

    Binary Search Tree (BST) is an extension of Binary tree with some added constraints. In BST, the value of the left child of a node must be smaller than or equal to the value of its parent and the value of the right child is always larger than or equal to the value of its parent. This property of Binary Search Tree makes it suitable for searching operations as at each node we can decide accurately whether the value will be in left subtree or right subtree. Therefore, it is called a Search Tree.

    二进制搜索树(BST)是二进制树的扩展,带有一些附加的约束。 在BST中,节点的左子节点的值必须小于或等于其父节点的值,而右子节点的值始终大于或等于其父节点的值。 二进制搜索树的此属性使其适合于搜索操作,因为在每个节点上,我们都可以准确地确定该值是在左子树中还是在右子树中。 因此,它称为搜索树。

    Binary Search Tree

    Fig 3: Binary Search Tree (Source)

    无花果3:二叉树( Source )

    AVL树 (AVL Tree)

    AVL tree is a self-balancing binary search tree. The name AVL is given on the name of its inventors Adelson-Velshi and Landis. This was the first dynamically balancing tree. In AVL tree, each node is assigned a balancing factor based on which it is calculated whether the tree is balanced or not. In AVL tree, the heights of children of a node differ by at most 1. The valid balancing factor in AVL tree are 1, 0 and -1.  When a new node is added to the AVL tree and tree becomes unbalanced then rotation is done to make sure that the tree remains balanced. The common operations like lookup, insertion and deletion takes O(log n) time in AVL tree. It is widely used for Lookup operations.

    AVL树是一种自平衡二进制搜索树。 名称为AVL的是其发明者Adelson-Velshi和Landis的名字。 这是第一棵动态平衡树。 在AVL树中,为每个节点分配一个平衡因子,基于此平衡因子,可以计算树是否平衡。 在AVL树中,节点的子代的高度最多相差1。在AVL树中,有效的平衡因子为1、0和-1。 将新节点添加到AVL树后,树变得不平衡,然后进行旋转以确保树保持平衡。 查找,插入和删除等常见操作在AVL树中花费O(log n)时间。 它广泛用于查找操作。

    AVL Tree

    Fig 4: Source

    图4: 来源

    红黑树 (Red-Black Tree)

    Red-Black is another type of self-balancing tree. The name Red-Black is given to it because each node in a Red-Black tree is either painted Red or Black according to the properties of the Red- Black Tree. This make sure that the tree remains balanced. Although the Red-Black tree is not a perfectly balanced tree but its properties ensure that the searching operation takes only O(log n) time. Whenever a new node is added to the Red-Black Tree, the nodes are rotated and painted again if needed to maintain the properties of the Red-Black Tree .

    红黑是另一种自平衡树。 之所以使用名称Red-Black,是因为根据Red-Black树的属性,将Red-Black树中的每个节点涂成红色或黑色。 这样可以确保树保持平衡。 尽管红黑树不是完全平衡的树,但是它的属性可确保搜索操作仅花费O(log n)时间。 每当将新节点添加到Red-Black Tree时,如果需要维护Red-Black Tree的属性,就会旋转并再次绘制节点。

    Red-Black Tree

    Fig 5: Red-Black Tree (Source)

    图5:红黑树( 来源 )

    一元树 (N-ary Tree)

    In an N-ary tree, the maximum number of children that a node can have is limited to N. A binary tree is 2-ary tree as each node in binary tree has at most 2 children. Trie data structure is one of the most commonly used implementation of N-ary tree. A full N-ary tree is a tree in which children of a node is either 0 or N. A complete N-ary tree is the tree in which all the leaf nodes are at the same level.

    在N元树中,一个节点可以具有的最大子节点数限制为N。由于二叉树中的每个节点最多具有2个子节点,因此二叉树是2元树。 Trie数据结构是N元树的最常用实现之一。 完整的N元树是其中节点的子节点为0或N的树。完整的N元树是其中所有叶节点处于同一级别的树。

    N-ary tree (5-ary)

    Fig 6: N-ary tree (5-ary)

    图6:N元树(5元)

    I hope you got the idea about some of the common types of trees in data structure. If you have any queries then feel free to ask in the comment section.

    希望您对数据结构中一些常见的树类型有所了解。 如果您有任何疑问,请随时在评论部分提问。

    翻译自: https://www.thecrazyprogrammer.com/2019/09/types-of-trees-in-data-structure.html

    java 树结构数据类型

    展开全文
  • java组装结构数据小技巧,巧妙利用java的对象引用特点,仅使用2层for循环即可组装深层结构数据;比传统的自循环组装形数据,效率更高更实用;
  • java树结构,树结构表设计

    热门讨论 2009-12-01 12:08:08
    我当时回答设计就是通过一pid来保存父结点的id值来实现,通过递归来生成一棵,但是面试官说如果比较大的话这样做的效率太低,网上找好像也都是这种方法,后来发现以前看用友的表结构设计里没有用这种方法,...
  • java树结构的层级查询

    千次阅读 2021-02-07 17:36:29
    最近在做项目的过程中,需要做一个分类,设计出来的表结构: 查询层级的时候只需要用到父级id,也就是这个分类的上层分类,设计出来的分类层级是不限定级数的,也就是说可能有123456级。 规定一级的父id为0,二级为...

    最近在做项目的过程中,需要做一个分类,设计出来的表结构:
    在这里插入图片描述
    查询层级的时候只需要用到父级id,也就是这个分类的上层分类,设计出来的分类层级是不限定级数的,也就是说可能有123456级。
    规定一级的父id为0,二级为一级的id,以此类推,那么查询的时候我们就不知道这一级下面有多少级了,当然可以通过代码判断,但是没必要,这时候我们可以使用递归的方法了
    这是返回的bean结构,里面存放了一个自身结构的list
    在这里插入图片描述
    在这里插入图片描述
    执行sql语句getClassifyList,然后通过resultMap跳到NextTreeResultMap主体里面,通过标签,把id作为参数又再次执行sql语句getNextNodeTree,把获取到的对象存放到childrenList,然后一致循环执行。这种方法是可以实现效果的,但是当分类数量过多时不建议使用。
    使用场景(查询不确定层级数的分类)

    展开全文
  • 自己写的一个 用java代码复制结构数据的方法 很实用 希望对有需求的朋友给予帮助
  • 前台: function listToTree(myId,pId,list){ function exists(list, parentId){ for(var i=0; i<list.length; i++){ if (list[i][myId] == parentId) return true; } return false;
  • Java实现简单树结构

    2020-08-31 16:31:31
    主要为大家详细介绍了Java实现简单树结构的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Java递归算法构造JSON结构Java递归算法构造JSON结构Java递归算法构造JSON结构
  • ztree 后台树java代码组装 数据库建表sql jdbc连接,节点数据保存方法,生成方法采用递归算法实现。
  • Java组装树结构

    千次阅读 2022-03-25 15:08:08
    应用场景,数据库表里的多条数据互为父子级关系,现要对他们进行组装,形成结构的数据,需要到达如下效果: [ { "parentId": "0", "name": "一级目录1", "id": "10", "children": [ { ...

    应用场景,数据库表里的多条数据互为父子级关系,现要对他们进行组装,形成树形结构的数据,需要到达如下效果:

    [
    	{
    		"parentId": "0",
    		"name": "一级目录1",
    		"id": "10",
    		"children": [
    			{
    				"parentId": "10",
    				"name": "二级目录1",
    				"id": "20",
    				"children": []
    			}
    		]
    	},
    	{
    		"parentId": "0",
    		"name": "一级目录2",
    		"id": "11",
    		"children": [
    			{
    				"parentId": "11",
    				"name": "二级目录2",
    				"id": "21",
    				"children": [
    					{
    						"parentId": "21",
    						"name": "三级目录1",
    						"id": "30",
    						"children": []
    					}
    				]
    			}
    		]
    	}
    ]

    一、定义数据实体

    public class Chapters {
        /** 目录id */
        private String id;
        /** 父目录id */
        private String parentId;
        /** 目录名称 */
        private String name;
        /** 子目录列表 */
        @Builder.Default
        private List<Chapters> children = new ArrayList<>();;
    }

    二、组装树结构的编码

    public class Demo {
    
        public static void main(String[] args) {
            // 测试数据
            List<Chapters> list = getData();
            // 处理完成后的最终数据
            List<Chapters> resultList = new ArrayList<>();
            // 层级处理
            for (Chapters book : list) {
                // 父id是0,就是最大一级
                if ("0".equals(book.getParentId())) {
                    resultList.add(book);
                }
                // 父子级判断,确定父子级关系后把子目录放到父目录下面
                for (Chapters book2 : list) {
                    if (book.getId().equals(book2.getParentId())) {
                        book.getChildren().add(book2);
                    }
                }
            }
            System.out.println(JSON.toJSONString(resultList));
        }
    
        // 测试数据,模拟从数据库中查询
        public static List<Chapters> getData() {
            // 为了方便就直接使用lombok的Builder,不new对象了
            Chapters book10 = Chapters.builder().id("10").parentId("0").name("一级目录1").build();
            Chapters book11 = Chapters.builder().id("11").parentId("0").name("一级目录2").build();
    
            Chapters book20 = Chapters.builder().id("20").parentId("10").name("二级目录1").build();
            Chapters book21 = Chapters.builder().id("21").parentId("11").name("二级目录2").build();
    
            Chapters book30 = Chapters.builder().id("30").parentId("21").name("三级目录1").build();
    
            List<Chapters> list = new ArrayList<>();
            list.add(book10);
            list.add(book11);
            list.add(book20);
            list.add(book21);
            list.add(book30);
    
            return list;
        }
    
    }
    

    执行结果:

     

    展开全文
  • 一、数据库父子结构数据设计  大部分采用 parentId的形式来存储父id,并且只存储父id,祖父Id不存储。也可以添加存储层级级别或者层级关系等字段。 CREATE TABLE `t_resource` ( `id` varchar(255) NOT NULL ...
  • 主要介绍了JAVA后台转换成树结构数据返回给前端的实现方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • java后台常用的树结构,通过递归写成的。里面详细介绍了。树结构的用法实例。以及参考说明等。
  • 主要介绍了java实现构造无限层级形菜单,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • NULL 博文链接:https://hahawowo.iteye.com/blog/783874
  • 主要介绍了java数据结构排序算法之树形选择排序,结合具体实例形式分析了java树形选择排序的原理、实现技巧与相关注意事项,需要的朋友可以参考下
  • public GbiPrivilege getPrivilegeTree(UserInfo user) { String sql = sqlMap("privilege.getall"); if (StringUtils.isBlank(sql)) { throw new SqlNotFoundException("privilege.getall");...
  • 主要给大家介绍了关于利用java+mysql递归实现拼接形JSON列表的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面跟着小编来一起看看吧。
  • 主要介绍了JAVA如何转换树结构数据代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • JAVA树结构

    千次阅读 2020-10-04 16:00:41
    JAVA树结构实体数据处理类结果 实体 public class ProjectTree { private String id; private String name; private String childrenId; //父节点该值为“0”,子节点该值为父节点id private List<...
  • 主要介绍了JAVA 根据数据库表内容生产树结构JSON数据的实例代码,非常不错,具有参考借鉴价值,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 333,840
精华内容 133,536
关键字:

java树结构

java 订阅
友情链接: daima.rar