美文网首页java技术基础
数据结构:树型结构

数据结构:树型结构

作者: 步积 | 来源:发表于2017-04-23 17:59 被阅读91次

    无论是链表,栈还是队列,它们都是线性结构的,每个节点的左边最多一个节点,右边也最多一个节点。对于大量的输入数据,线性表的访问时间太长,效率较低,不宜使用。
    因此需要一种非线性的数据结构,树型结构,其大部分操作的运行时间平均为O(logN)。
    在计算机科学中,树是非常有用的抽象概念。我们形象的去描述一棵树,一个家族的祖父有两个儿子,这两个儿子一个有一个儿子,一个有三个儿子,像这样发展下去的一个族谱,就是一个树,如图1所示。

    图1 族谱图
    就像一棵真正的树一样,我们把祖父称为树根,两个儿子是分叉开的两个树枝,这两棵树枝可以继续向下分成N个树枝,循环下去,一直到长出叶子为止。
    我们把祖父或者树根称为根root节点,祖父的儿子称为子节点,每个儿子作为根节点又可以形成一棵树,我们把这样的树称为根节点的子树。

    树的标准定义:

    tree是包含n(n>0)个节点的有穷集合,其中:

    1. 每个元素称为节点node
    2. 有一个特定的节点被称为根节点或树根root
    3. 除根节点之外的其余数据元素被分为m(m≥0)个互不相交的结合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树subtree

    树具有以下特点:

    1. 每个节点有零个或多个子节点。
    • 每个子节点只有一个父节点。
    • 没有父节点的节点称为根节点。

    关于树的一些术语

    • 节点的度:一个节点含有的子树的个数称为该节点的度;
    • 叶节点或终端节点:度为零的节点称为叶节点;
    • 非终端节点或分支节点:度不为零的节点;
    • 双亲节点或父节点:若一个结点含有子节点,则这个节点称为其子节点的父节点;
    • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
    • 兄弟节点:具有相同父节点的节点互称为兄弟节点;
    • 树的高度或深度:定义一棵树的根结点层次为1,其他节点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。
    • 节点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
    • 树的度:一棵树中,最大的节点的度称为树的度;
    • 节点的祖先:从根到该节点所经分支上的所有节点;
    • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
    • 森林:由m(m>=0)棵互不相交的树的集合称为森林;

    树的实现

    节点的代码如下:

    struct treenode
    {
        int data;
        struct treenode * fistchild;//第一个儿子
        struct treenode * nextsibling;//下一个兄弟
    }
    

    树的应用

    大部分操作系统的目录结构就是采用树结构。
    树的种类有很多,树所扩展出来的很多数据结构都有着很大的作用,比如说红黑树,B树,后缀树等等。

    参考:
    基本数据结构:树(tree)

    相关文章

      网友评论

        本文标题:数据结构:树型结构

        本文链接:https://www.haomeiwen.com/subject/htzezttx.html