树

发表于 更新于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 6 分钟

定义

树是由n个结点组成的有限集。n=0时称为空树。且对于非空树：

  • 有且仅有一个特定的称为根的结点；

  • 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。

基本术语

树

结点：一个数据元素+若干指向子树的分支

结点拥有的子树数（或分支数）称为结点的度。

  • 结点A的度是3，C的是1，G的是零。度为零的结点称为叶子结点/终端结点。K，L，F，G，M，I，J是叶子结点。度不为零的结点称为分支结点/非终端结点。

结点的子树的根称为该结点的孩子，该结点称为孩子的双亲

  • D的孩子是H，I和J；D的双亲是A。

同一个双亲的孩子是兄弟。

  • H，I和J是兄弟。

双亲在同一层的结点称为堂兄弟

结点的祖先是从根到该结点所经过的所有结点。

  • M的祖先是A、D和H。

结点的子孙是该结点下层子树中的任意结点。

  • B的子孙为E、F、K和L。

结点的层次

  • 从根到该结点的层数（根结点为第一层）。

树的深度

  • 指所有结点最大的层数（Max{各结点的层数}）。

树的度

  • 所有结点度的最大值（Max{各结点的度}）。
  • 上图中树的度为3

有序树

  • 结点各子树从左至右有序，不能互换（左为第一）
  • 家谱

无序树

  • 结点各子树可互换位置
  • 机构

森林

  • 指m棵互不相交的树的集合

任何一棵非空树是一个二元组Tree =（root，F）

  • root 被称为根结点，F 被称为子树森林

树的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ADT树(tree )

Data
    树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关

Operation

    InitTree (&T) :构造空树T。
    DestroyTree (&T) :销毁树T。
    CreateTree ( &T, definition) :按definition中给出树的定义来构造树。ClearTree(&T):若树T存在，则将树T清为空树。
    TreeEmpty (T):若T为空树，返回true,否则返回false.
    TreeDepth(T) :返回T的深度。
    Root (T) :返回T的根结点。
    Value (T,cur e): cur e是树T中一个结点，返回此结点的值。
    Assign (T,cur _e,value) :给树T的结点cur_ e赋值为value。
    Parent (T,cur e):若cur_ e是树T的非根结点，则返回它的双亲，否则返回空。LeftChild(T,cur e):若cur_ e是树T的非叶结点，则返回它的最左孩子，否则返空。
    Rightsibling (T,cur e) :若cur_ e有右兄弟，则返回它的右兄弟，否则返回空。InsertChild(&T,&p,i,c):其中p指向树T的某个结点，i为所指结点P的度加上1，非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。
    DeleteChild(&T,&p,i) :其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i棵子树。
endADT

树的存储结构

说到存储结构，就会想到我们前面章节讲过的顺序存储和链式存储两种结构。

先来看看顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的，对于树这样多对的结构呢?

树中某个结点的孩子可以有多个，这就意味着，无论按何种顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系，你想想看，数据元素挨个的存储，谁是谁的双亲，谁是谁的孩子呢?简单的顺序存储结构是不能满足树的实现要求的。

不过充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构的表示。我们这里要介绍三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。

data | parent |
1
2
3
4
5
6
7
8
9
10
#define MAX_TREE_SIZE 100
typedef int TElemType;      /*树结点的数据类型，目前暂定为int*/
typedef struct PTNode{      /*结点结构*/
     TElemType  data;       /*结点数据*/
      int  parent;          /*双亲位置*/
}PTNode;
typedef struct{             /*树结构*/
    PTNode nodes[MAX_TREE_SIZE];    /*结点数组*/
    int r,n;                /*根的位置和结点数*/
}PTree；

孩子表示法

每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们把这种方法叫做多重链表表示法。

结点同构

  • 结点的指针个数相等，为树的度D
  • 缺点：容易造成空间浪费
data | child1 | child2 | … | childD |

结点不同构

  • 结点指针个数不等，为该结点的度d
  • 缺点：操作不方便
data | degree | child1 | child2 | … | childd|
1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAX_TREE_SIZE 100
typedef struct CTNode {
    int child;              /*孩子结点的序号*/
    struct CTNode *next;    /*孩子结点的指针域*/　　
} *ChildPtr;                /*孩子链表的结点*/
typedef struct {
    ElemType data;          /* 结点的数据元素*/
    ChildPtr firstchild;    /* 孩子链表头指针*/
} CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; 　            /* 结点数和根结点的位置*/　　
} CTree;                    /*树结构*/

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

data | firstchild | rightsib |
1
2
3
4
typedef struct CSNode{
    ElemType data;
    struct CSNode * firstson,* nextsibling;	
}CSNode,*CSTree;

树关联二叉树及其他内容待到二叉树完成

欢迎批评指正！