《大话数据结构》树

1.与树相关的常见概念

1）树的定义

对树的定义，还需要强调两点：

1）n>0的时候，根节点是唯一的，不可能存在多个根节点

2）m>0的时候，子树的个数没有限制，但他们一定都shi是互不相交的

子树

2.树结构中的常用概念

1）结点度

结点拥有的子树数目称为结点的度（Degree）；

内部的结点：我们可以称为子结点，也可以称之为B，D，G，H，I是A的子树

树的度是树内各结点的度的最大值。

2）结点间的关系

结点的子树的根称为该结点的孩子（Child），相应得，该结点称为孩子的双亲（Parent）;

 

eg：D，B，A都是H的祖先；D，G，H，I是B的子孙。

3）树的深度（Depth）或高度

有序树：如果将树中结点的各子树看成从左到右是有序的，不能互换的，则称该树是有序树

3.树的存储结构

表示方法总共有：双亲表示法，孩子表示法，孩子兄弟表示法

1）双亲表示法

核心idea：在每个结点中，每个结点除了知道自己是谁，还知道他的双亲在哪

 

data:数据域，存储结点的数据信息

parent：指针域，存储该结点的双亲在数组中的下标

//node结构
MAX_SIZE=100
typedef struct node
{
    int data;//node数据
    int parent;//双亲位置
}pnode;

//树结构
typedef struct
{
    pnode nodes[MAX_SIZE];//node数组 
    int r,n;//根的位置及结点数
}tree;

约定：根结点的位置域设置为-1，所有的node都存在双亲的位置，再增加一个node，

还可以增加右兄弟域，来体现兄弟关系，操作是：如果它存在右兄弟，则记录右兄弟的下标

2）孩子表示法

用多重链表，即：每个结点有多个指针域，其中每个指针指向一颗子树的根结点

方案1

data是数据域，child1到child2是指针域，用来指向该结点的孩子结点

具体的结构如下所示：

缺点：这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域都是空的。

方案2

每个结点指针域的个数=该结点的度

data是数据域，

degree为度域，也就是存储该结点的孩子结点的个数；

child1到childd为指针域，指向该结点的各个孩子的结点。

具体结构如下图所示，

缺点：这种方法克服了消费空间的缺点，空间利用率提高了，到那时由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上会带来时间上的损耗

2）孩子表示法

具体结构如下图所示，

上面涉及了两种结点结构

一个是孩子链表的孩子结点

child：数据域，存储某个结点在表头数组中的下标

next：指针域，存储指向某结点的下一个孩子结点的指针

另一个是表头数组的表头结点

data：数据域，存储某结点的数据信息

firstchild：头指针域，存储该结点的孩子链表的头指针

//孩子表示法结构定义

#define MAX_TREE_SIZE 100

//孩子结点
typedef struct chlnode
{
    int child;
    struct chlnode *next;
}chlnode; 

//表头结构
typedef struct
{
    int data;
    chlnode firstchild;
}chlbox;

//树结构
typedef struct
{
    chlbox nodes[MAX_TREE_SIZE];//结点数组
    int r,n;//根的位置和结点数
}tree;

3.孩子兄弟表示法

结点结构如下表所示，

data：数据域

firstchild：指针域，存储该结点的第一个孩子结点（左子结点）的存储地址；

rightsib：指针域，存储该结点的右兄弟结点的存储地址

//定义代码

typedef struct snode
{
    int data;
    struct snode *firstchild,*rightsib;
}snode;

缺点：给查找每个结点的某个孩子带来了方便，但是想要找某个结点的双亲，这个表示法是有缺陷的