重温数据结构:树 及 Java 实现

数据结构,指的是数据的存储形式,常见的有线性结构(数组、链表,队列、栈),还有非线性结构(树、图等)。

今天我们来学习下数据结构中的

什么是树

线性结构中,一个节点至多只有一个头节点,至多只有一个尾节点,彼此连接起来是一条完整的线。

比如链表和数组:

而树,非线性结构的典型例子,不再是一对一,而变成了一对多(而图则可以是 多对多),如下图所示:

可以看到:

  • 图中的结构就像一棵倒过来的树,最顶部的节点就是“根节点 (root 节点)
  • 每棵树至多只有一个根节点
  • 根节点生出多个孩子节点,每个孩子节点只有一个父节点,每个孩子节点又生出多个孩子
  • 父亲节点 (parent) 和孩子节点 (child) 是相对的
  • 没有孩子节点的节点成为叶子节点 (leaf)

树的相关术语

根节点、父亲节点、孩子节点、叶子节点如上所述。

节点的度

一个节点直接含有的子树个数,叫做节点的度。比如上图中的 3 的度是 2,10 的度是 1。

树的度

一棵树中 最大节点的度,即哪个节点的子节点最多,它的度就是 树的度。上图中树的度为 2 。

节点的层次

从根节点开始算起,根节点算第一层,往后底层。比如上图中,3 的层次是 2,4 的层次是 4。

树的高度

树的高度是从叶子节点开始,自底向上增加

树的深度

与高度相反,树的深度从根节点开始,自顶向下增加

整个树的高度、深度是一样的,但是中间节点的高度 和 深度是不同的,比如上图中的 6 ,高度是 2 ,深度是 3。

树的两种实现

从上述概念可以得知,树是一个递归的概念,从根节点开始,每个节点至多只有一个父节点,有多个子节点,每个子节点又是一棵树,以此递归。

树有两种实现方式:

  • 数组
  • 链表

数组表示:

我们可以利用每个节点至多只有一个父节点这个特点,使用 父节点表示法 来实现一个节点:

public class TreeNode {

    private Object mData;   //存储的数据
    private int mParent;   //父亲节点的下标

    public TreeNode(Object data, int parent) {
        mData = data;
        mParent = parent;
    }

    public Object getData() {
        return mData;
    }

    public void setData(Object data) {
        mData = data;
    }

    public int getParent() {
        return mParent;
    }

    public void setParent(int parent) {
        mParent = parent;
    }
}

上述代码中,使用 角标 来指明父亲节点的位置,使用这个节点组成的数组就可以表示一棵树。

public static void main(String[] args){
    TreeNode[] arrayTree = new TreeNode[10];
}

用数组实现的树表示下面的树,(其中一种 )结果就是这样的:

数组实现的树节点使用角标表示父亲的索引,下面用链表表示一个节点和一棵树:

链表表示的节点:

public class LinkedTreeNode {

    private Object mData;   //存储的数据
    private LinkedTreeNode mParent;   //父亲节点的下标
    private LinkedTreeNode mChild;  //孩子节点的引用

    public LinkedTreeNode(Object data, LinkedTreeNode parent) {
        mData = data;
        mParent = parent;
    }

    public Object getData() {
        return mData;
    }

    public void setData(Object data) {
        mData = data;
    }

    public Object getParent() {
        return mParent;
    }

    public void setParent(LinkedTreeNode parent) {
        mParent = parent;
    }

    public LinkedTreeNode getChild() {
        return mChild;
    }

    public void setChild(LinkedTreeNode child) {
        mChild = child;
    }

}

使用引用,而不是索引表示父亲与孩子节点。

使用一个 List, 元素是 LinkedTreeNode,就可以表示一棵链表树:

public static void main(String[] args){
    LinkedList<LinkedTreeNode> linkedTree = new LinkedList<>();
}

这样只需知道 根节点就可以遍历整个树。知道某个节点也可以获取它的父亲和孩子。

树的几种常见分类及使用场景

树,为了更好的查找性能而生。

常见的树有以下几种分类:

  • 二叉树
  • 平衡二叉树
  • B 树
  • B+ 树
  • 哈夫曼树
  • 红黑树

接下来陆续介绍完回来补使用场景。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(47) 堆和PriorityQueue的应用 / 计算机程序的思维逻辑

45节介绍了堆的概念和算法,上节介绍了Java中堆的实现类PriorityQueue,PriorityQueue除了用作优先级队列,还可以用来解决一些别的问题,...

17810
来自专栏余林丰

MyBatis之级联——一对一关系

在学数据库概论的时候会听到这么几个词:数据库的关系分为一对一、一对多、多对多。对于在学校里学的知识已经忘得差不多了,在这里简单的提一下数据库的关系。此篇是介绍M...

1795
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

2028
来自专栏Golang语言社区

Go语言struct类型详解

struct Go语言中,也和C或者其他语言一样,我们可以声明新的类型,作为其它类型的属性或字段的容器。例如,我们可以创建一个自定义类型person代表一个人的...

2714
来自专栏HTML5学堂

为什么不要在 JavaScript 中使用位操作符?

如果你的第一门编程语言不是 JavaScript,而是 C++ 或 Java,那么一开始你大概会看不惯 JavaScript 的数字类型。在 JavaScrip...

34710
来自专栏醒者呆

面向程序员编程——精研排序算法

这篇文章很长,我花了好久的时间(中间公司出了bug,加班了好几天( ¯ ¨̯ ¯̥̥ ))进行整理,如有任何疑问,欢迎随时留言。 关键字:排序算法,时间...

3255
来自专栏PPV课数据科学社区

【工具】SAS数据整理的16个技巧

1、修改属性   attrib 2、根据条件删除记录   if条件 then delete; 3、分拆数据集 data mastermissing; me...

2955
来自专栏desperate633

一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找...

1992
来自专栏数据结构与算法

小米OJ刷题日志

$f[i][j]$表示第一个队列匹配到了$i$位置,第二个队列匹配到了$j$位置是否可行

2162
来自专栏岑玉海

hbase源码系列(五)Trie单词查找树

  在上一章中提到了编码压缩,讲了一个简单的DataBlockEncoding.PREFIX算法,它用的是前序编码压缩的算法,它搜索到时候,是全扫描的方式搜索的...

3548

扫码关注云+社区