C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

基本数据结构:树(tree)

Posted on 2012-08-03 09:18 C小加 阅读(9989) 评论(2)  编辑 收藏 引用 所属分类: 数据结构和算法

基本数据结构:树(tree)

作者:C小加 更新时间:2012-8-3

无论是链表,栈还是队列,它们都是线性结构的,每个节点的左边最多一个节点,右边也最多一个节点,对于大量的输入数据,线性表的访问时间太慢,不宜使用。这里我要说一种非线性的数据结构,其大部分操作的运行时间平均为O(logn)。

我们涉及到的这种数据结构叫做树。在计算机科学中,树是非常有用的抽象概念。我们形象的去描述一棵树,一个家族的老祖可能有两个儿子,这两个儿子一个有一个儿子,一个有三个儿子,像这样发展下去的一个族谱,就是一个树,如图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)    每个节点有零个或多个子节点。

(2)    每个子节点只有一个父节点。

(3)    没有父节点的节点称为根节点。

关于树的一些术语

        节点的度:一个节点含有的子树的个数称为该节点的度;

        叶节点或终端节点:度为零的节点称为叶节点;

        非终端节点或分支节点:度不为零的节点;

        双亲节点或父节点:若一个结点含有子节点,则这个节点称为其子节点的父节点;

        孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;

        兄弟节点:具有相同父节点的节点互称为兄弟节点;

        树的高度或深度:定义一棵树的根结点层次为1,其他节点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。节点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;

        树的度:一棵树中,最大的节点的度称为树的度;

        节点的祖先:从根到该节点所经分支上的所有节点;

        子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

        森林:由m(m>=0)棵互不相交的树的集合称为森林;

树的实现

节点的代码如下:

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

树的应用

       大部分操作系统的目录结构就是采用树结构。

       树的种类有很多,树所扩展出来的很多数据结构都有着很大的作用,比如说红黑树,B树,后缀树等等,这将在日后写到。

Feedback

# re: 基本数据结构:树(tree)  回复  更多评论   

2012-08-03 11:16 by SunRise_at
你这是坑人吗?

# re: 基本数据结构:树(tree)  回复  更多评论   

2013-11-20 15:17 by einverne
就是坑人的。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理