数据结构篇——树（1）

发布于：2025-03-17 ⋅ 阅读:(22) ⋅ 点赞:(0)

一、引入

        树结构是一类重要的非线性数据结构且是一种以分支关系定义的层次结构。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用,如在操作系统中,用树来表示文件目录的组织结构,本章重点讨论二叉树的存储结构及其各种操作。

二、树和二叉树的定义

        2.1、树和二叉树的定义：

1、树的定义：

        树是n个结点的有限集（n>=0），当n=0时树为空树。对于非空树则有两个特点：

  1. 有且仅有一个称之为根的结点;
  2. 除根结点以外的其余结点可分为m(m>=0)个互不相交的有限集T 1,T2,···,Tm,其中每一个集合本身又是一棵树。并日称为根的子树。

例如 图5.1：

        在图中(a)是只有一个结点的树；(b)是有13个结点的树，其中A是根,其余结点分成3个互不相交的子集:T1={ B,E,F,K,L} ,T2={ C,G} ,T3={ D,H,I,J,M} $。T1、T2和T3都是根A的子树,且本身也是一棵树。例如T1,其根为B,其余结点分为两个互不相交的子集:T11={ E,K,L} ,T12={ F,B} 。T11和T12都是B的子树。而T11中E是根,{K }和{L}是E的两棵互不相交的子树,其本身又是只有一个根结点的树。 

2、二叉树的定义：

        二叉树(Binary Tree )是n(n >= 0)个结点所构成的集合,它或为空树(n=0);或为非空树,对于非空树T:

  1. 有且仅有一个称之为根的结点;
  2. 除根结点以外的其余结点分为两个互不相交的子集T1和T 2,分别称为T的左子树和右子树,且T1和T2本身又都是二叉树。

Tips:二叉树与树一样具有递归性质,二叉树与树的区别主要有以下两点:

  1. 二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点);
  2. 二叉树的子树有左右之分,其次序不能任意颠倒。

二叉树可以有5种基本形态,如图5.3所示：

2.2、树的基本术语

        在树这一节中特定的基本术语比较多，零零散散加起来有十四种之多，所以在这部分大家就主要得花功夫去理解记忆而不是死记硬背。来看看都有哪些术语吧。(在介绍中的例子都参考图5.1)

  1. 结点:树中的一个独立单元。包含一个数据元素及若干指向其子树的分支,如图5.1(b)中的A、B、C、D等。
  2. 结点的度:结点拥有的子树数称为结点的度。例如,A的度为3,C的度为1,F的度为0。
  3. 树的度:树的度是树内各结点度的最大值。图5.1(b)所示的树的度为3。
  4. 叶子:度为0的结点称为叶子或终端结点。结点K、L、F、G、M、I、J都是树的叶子。
  5. 非终端结点:度不为0的结点称为非终端结点或分支结点。除根结点之外,非终端结点也称为内部结点。
  6. 双亲和孩子:结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲。例如,B的双亲为A,B的孩子有E和F。
  7. 兄弟:同一个双亲的孩子之间互称兄弟。例如,H、I和J互为兄弟。
  8. 祖先:从根到该结点所经分支上的所有结点。例如,M的祖先为A、D和H。
  9. 子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L 和F。
  10. 层次:结点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加1。
  11. 堂兄弟:双亲在同一层的结点互为堂兄弟。例如,结点G与E、F、H、I、J互为堂兄弟
  12. 树的深度：树中结点的最大层次称为树的深度或高度。如上图(b)的深度为4。
  13. 有序树和无序树:如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。在有序树中最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。
  14. 森林:是(m >= 0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。由此,也可以用森林和树相互递归的定义来描述树。

三、树的性质

3.1、树的性质

树具有如下最基本的性质：

  1. 树中的结点数等于所有结点的度数加1。
  2. 度为m的树中第i层上至多有{m}^{i-1}个结点(i>=1)。
  3. 高度为h的m叉树至多有{m}^i-1/m-1个结点。
  4. 具有n个结点的m叉树的最小高度为[log_m(n(m-1)+1)]

3.2、二叉树的性质

二叉树有如下基本性质：

  1. 在二叉树上的第i层上至多有{2}^{i-1}个结点（i>=1）。
  2. 深度为k的二叉树至多有{2}^{k-1}个结点（k>=1）。
  3. 对任何一颗二叉树T，如果其终端结点为n0，度为2的结点数为n，2则n0=n2+1

四、树的存储结构 

4.1、树的存储结构

        在树的存储结构中主要有三种表示方法：双亲表示法、孩子表示法以及孩子兄弟表示法。下面让我们简单的来学习下这几种常见的存储结构吧。

1、双亲表示法：

        同样的是将一个自定义的结构体作为一个存储单元也就是一个结点，但每个结点除了数据域data之外还有一个指针域parent来指向其双亲的位置。具体的存储结构示意图如下：

代码描述：

#define MAXSIZE 100    //给数据串分配空间
typedef int TElemType;	//定义树结点的数据类型

typedef struct PTNode{
	TElemType data;	//数据域
	int parent;	//指针域
}PTNode;


typedef struct{
	PTNode nodes[MAXSIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;

        这种存储结构利用了每个结点（除根结点外）只有唯一的双亲性质。在这种存储结构下求结点的双亲和根十分方便，但求结点的孩子时就需要遍历整个结构。

2、孩子表示法：

        由于树的每个结点都可能有着很多个孩子，所以为了能完整的记录每个孩子的位置就得采用多重链表的方式。即每个结点有多个指针域，每一个指针分别指向一个孩子的根结点，此时连标中的结点就有了下图所示的格式：

 具体的结构示意图如下： 

        通过观察我们发现该结构的实现方式具体就是：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成-一个线性表，采用顺序存储结构，存放进一个一维数组中。

代码表示：

#define MAXSIZE 100    //分配数组空间
typedef struct CTNode{    //定义孩子的结点结构
	int child;
	struct CTNode *next;
}*ChildPtr;

typedef struct{    //定义每个孩子链表的头结点
	TElemType data;
	ChildPtr firstchild;
}CTBox;

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

        与双亲表示法相反,孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来,即将双亲表示和孩子链表合在一起。这个就由你来试试看吧。

3、孩子兄弟表示法 ：

        孩子兄弟表示法又叫做二叉树表示法，或二叉链表示法，就是用二叉链表做树的存储结构。链表中的结点的两个指针域分别指向我该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild和nextsibling其结点形式如下：

用代码作如下表示：

typedef struct CSNode{
    ElemType data;
    struct CSNode *fristchild,*nextsibling;
}CSNode,*CSTree;

下图为上文提到的图5.19中的树的孩子兄弟链表。利用这种结构能够方便的实现各种树的操作：


        这种存储结构的优点是它和二叉树的二叉链表表示完全一样,便于将一般的树结构转换为二叉树进行处理,利用二叉树的算法来实现对树的操作。因此孩子兄弟表示法是应用较为普遍的一种树的存储表示方法。 

        由于二叉树的存储结构涉及到几个特殊的二叉树类型，和篇幅限制，将在后续讨论学习。今天的学习就到此处吧。如果我的内容对你有帮助，在下就厚着脸皮讨个点赞关注。如果你有更好的想法，还望留在评论区让我来参考学习。我将不胜感激并努力创作出更好的内容。

        

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布