Posted on 2012-08-03 09:18
C小加 阅读(10026)
评论(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树，后缀树等等，这将在日后写到。