基本数据结构:树(tree

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

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

我们涉及到的这种数据结构叫做树。在计算机科学中,树是非常有用的抽象概念。我们形象的去描述一棵树,一个家族的老祖可能有两个儿子,这两个儿子一个有一个儿子,一个有三个儿子,像这样发展下去的一个族谱,就是一个树,如图1所示。

 

就像一棵真正的树一样,我们把老祖称为树根,两个字儿是分叉开的两个树枝,这两棵树枝可以继续向下分成N个树枝,循环下去,一直到长出叶子为止。

我们把老祖或者树根称为根(root)节点,老祖的儿子称为子节点,每个儿子作为根节点又可以形成一棵树,我们把这样的树称为根节点的子树。

树的标准定义:

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

  (1)每个元素称为节点(node);

  (2)有一个特定的节点被称为根节点或树根(root)。

3)除根节点之外的其余数据元素被分为mm≥0)个互不相交的结合T1T2……Tm-1,其中每一个集合Ti1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。

树具有以下特点:

(1)    每个节点有零个或多个子节点。

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

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

关于树的一些术语

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

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

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

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

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

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

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

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

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

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

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

树的实现

节点的代码如下:

 

 
  1. struct treenode 
  2.  
  3.  
  4.        int data; 
  5.  
  6.        struct treenode *fistchild;//第一个儿子 
  7.  
  8. struct treenode *nextsibling;//下一个兄弟 
  9.  

树的应用

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

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