树的定义

树是用来处理一对多的数据结构树是n(n>=0)个节点的有限集 n = 0， 叫做空树n > 0： 根节点是唯一的子树的个数没有限制，但是一定是不相交的

树的度

节点拥有的子树数量称为节点的度 。 根据各个节点的度的不同，节点可以分为：

叶子节点(Leaf) [也叫做终端节点]： 度为0的节点分支节点[也叫做非终端节点]： 度不为0 内部节点： 除了根节点之外，分支节点也叫做内部节点

树的度是树内各节点的度的最大值

节点间关系

当前节点的子树的根称为该节点的孩子（子节点）当前节点称为其子节点的双亲 【因为当前节点只有一个，所以叫做双亲节点，而不是父/母节点】同一个双亲的孩子之间互称为兄弟节点的祖先是从根节点到当前节点所经分支上的所有节点。 比如下图， 相对于H节点，D，B，A都是它的祖先以某节点为根的子树中任一节点都称为该节点的子孙。比如B的子孙有D，G，H，I

树的层

节点的层(level)： 从根节点开始，根节点为第一层，跟的孩子为第二层。。。 若某节点为第i层，则其子树的跟就在第i+1层其双亲在同一层的节点互为堂兄弟。 比如下图中的，D，E，F是堂兄弟，G，H，I，J是堂兄弟树中节点的最大层次称为树的深度。比如下图中树的深度为4

树的有序性

如果树中结点的各子树从左向右是有序的，子树间不能互换位置，则称该树为有序树，否则为无序树。

树的表示方法

双亲表示法

取一块连续的内存空间，在层次每个节点的同时，各自都附加一个记录其父节点位置的变量

在树结构中，除了树根外，每个结点都只有一个父结点（又叫“双亲结点”）。 #define tree_size 100//宏定义树中结点的最大数量 #define TElemType int//宏定义树结构中数据类型 typedef struct PTNode{ //节点结构 TElemType data;//节点数据 int parent;//双亲位置下标 }PTNode; typedef struct { // 树结构 PTNode nodes[tree_size];//节点数组 int r,n;//根的位置下标和结点数 }PTree;

例如，使用双亲表示法存储图 1（A）中的树结构时，数组存储结果为（B）：

当算法中需要在树结构中频繁地查找某结点的父结点时，使用双亲表示法最合适。当频繁地访问结点的孩子结点时，双亲表示法就很麻烦，采用孩子表示法就很简单

孩子表示法

孩子表示法： 把每个节点的孩子节点排列起来，以单链表作存储结构，则n个节点有n个孩子链表，如果是叶子节点则单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存放进一个一维数组中

#define TElemType int #define Tree_Size 100 //孩子表示法 typedef struct CTNode{ int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标 struct CTNode * next; }*ChildPtr; typedef struct { TElemType data;//结点的数据类型 ChildPtr firstchild;//孩子链表的头指针 }CTBox; typedef struct{ CTBox nodes[Tree_Size];//存储结点的数组 int n,r;//结点数量和树根的位置 }CTree;

使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点。

双亲孩子表示法

将双亲表示法和孩子表示法结合起来

孩子兄弟表示法

使用链式存储结构存储普通树。链表中每个结点由 3 部分组成： 其中孩子指针域，表示指向当前结点的第一个孩子结点，兄弟结点表示指向当前结点的下一个兄弟结点。

#define ElemType int typedef struct CSNode{ ElemType data; struct CSNode * firstchild,*nextsibling; }CSNode,*CSTree;

通过孩子兄弟表示法，普通树转化为了二叉树，所以孩子兄弟表示法又被称为“二叉树表示法”或者“二叉链表表示法”。

树的双亲表示法、孩子表示法和孩子兄弟表示法

比较

树与线性表

树与森林

一棵树为树，两棵树及以上则称为森林