企业网站建设的三种方式,网页版微信二维码几分钟失效,wordpress需要多少运存,网站建设的公司怎么做文章目录8 树(上)8.1 引入8.2 树的基础知识8.3 树的存储结构8.3.1 双亲表示法8.3.2 孩子表示法8.4 二叉树8.4.1 基础知识8.4.2 高频考点8.4.3 二叉树的性质8.4.4 二叉链表8.4.5 树和二叉树的转换8.4.6 森林和二叉树的转换8.5 遍历8 树(上)
8.1 引入
我们在前面的章节中一直在…
文章目录8 树(上)8.1 引入8.2 树的基础知识8.3 树的存储结构8.3.1 双亲表示法8.3.2 孩子表示法8.4 二叉树8.4.1 基础知识8.4.2 高频考点8.4.3 二叉树的性质8.4.4 二叉链表8.4.5 树和二叉树的转换8.4.6 森林和二叉树的转换8.5 遍历8 树(上)
8.1 引入
我们在前面的章节中一直在谈一对一的线性结构可现实中还有很多一对多的情况需要处理。 一对一和一对多 为什么说前面学习的是一对一的线性结构从顺序表中我们可以看出一个结点总是跟在一个结点的后面栈、串、队列也皆是如此故我们说它们都是一对一的线性结构。 可是树却不是一对一的线性结构因为对于树来说其一个结点的后面可能跟着多个结点故它是一种一对多的线性结构。 8.2 树的基础知识
我们来讨论一下树。
物如其名树结构看起来就像一颗倒挂的是树。树实际上也是一个递归结构如果我们把A1称为父结点则A1下的A2、A3、A4就是它的子结点。那么对于A1来说其子结点有3个对于A2来说其也可能有子结点。 不同的术语 有时候不同的教材不同的地方有不同的术语如父子结点有时候也叫做双亲和孩子。 我们把某一结点的分支数量叫做结点的度。对于上图显然A1结点的度是3A7结点的度为0。我们把整棵树中所有结点拥有的最大分支数称为树的度如上图中树的度为3因为遍历树中所有结点度最大的那个结点度为3。
同理在上图中A5的祖先为A2和A1A1的子孙为A2~A7。
一棵树可以分为多个层。如下图所示 同一个双亲的结点互称兄弟如A2可以是A3的兄弟结点反过来A3是A2的兄弟结点这种表述也无误树的层数叫做树的高度或深度如上图中树的深度是3。结点从树的上面往下面数第几层即为结点的深度结点从下往上面数第几层即为结点的高度。如A1它从下往上数在第三层故A1结点高度为3而从上往下数第一层故其深度为1。
树的叶结点指的是若结点没有继续往下的分支了那么该结点即为叶结点。如上图中A5A6A3A4均为叶结点。 408科目10年05题 在一颗度为4的树T中若有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点则树T的叶结点个数为 10∗1(10个度为1)1∗2(1个度为2)10∗3(10个度为3)20∗4(20个度为4)12210*1(10个度为1)1*2(1个度为2)10*3(10个度为3)20*4(20个度为4) 12210∗1(10个度为1)1∗2(1个度为2)10∗3(10个度为3)20∗4(20个度为4)122123(总节点数)1011020叶结点123(总节点数) 1011020叶结点123(总节点数)1011020叶结点 故叶结点数为82。 8.3 树的存储结构
通过对前面的学习我们需要思考一下如何用代码实现树的顺序存储树提供了三种表示方法分别是双亲表示法、孩子表示法、孩子兄弟表示法。
8.3.1 双亲表示法
双亲表示法的重点在于我们存储的内容不仅仅是结点的数据而且还要存储其父节点是谁。故我们想到在结构体中定义两个数据一个用于存结点数据另一个用于存父节点在数组中的下标。
由于根结点是没有双亲的故我们约定根节点的双亲位置设置为-1。如下图所示 #define MAX_TREE_SIZE 100//结点结构
typedef struct
{Elem data;//结点数据int parent;//双亲位置
}PTNode;//树结构
typedef struct
{PTNode node[MAX_TREE_SIZE];int r,n;//根的位置和节点数
}这样的存储结构有一个好处我们可以根据结点中存储的双亲位置来找到它的双亲结点但是问题是如果你想要知道结点的孩子是什么就无能为力了你得遍历整个结构。
8.3.2 孩子表示法
如果树中含有多颗子树我们可以考虑使用多重链表。多重链表的意思就是每个链表节点中都包含有多个指针域每个指针域指向子树的根节点。但是这种表示法有一个问题就是每个子树的度是不一样的有些子树的度是1有些是2甚至于度为0。
对于上述的问题我们有两种不同的方案。
方案一
我们直接可以让树的度作为指针域的个数。我们知道树的度是树中所有结点的最大度数。这样的话子树的度小于树的度时我们把其余的指针域置空即可。如下所示 但是这种方案在于浪费内存。我们来看看方案二。
方案二
既然怕浪费那我们就按需分配。
我们在结构体定义时多加一个整形类型的变量degree用于记录度域即度的范围。如下所示 这种方案虽然避免了浪费空间但是却浪费了时间因为要维护度的数值。
既然上述方案都不太靠谱我们就用方案3的孩子表示法吧。具体办法是把每个结点的孩子结点排列用单链表作为存储结构。如果是叶子结点则单链表为空。
以上的文字可能有点晦涩难懂我们看图理解一下。 一开始我们用结构体定义两个变量。一个是结点数据一个是指针域其结构体看做是一个结点。而后将所有的结点存储一个数组中。如果一个结点有孩子那么其指针域指向存放其孩子的链表链表中存储的是关于该节点的所有孩子。
如上图所示A1是有三个孩子A2、A3、A4故其孩子链表中存放三个结点孩子链表的头指针存于数组的0号位数组的0号位存储的是一个结点的结构体结构体中有A1和其孩子链表的头指针。
8.4 二叉树
8.4.1 基础知识
在8.3.2 讲的孩子表示法中孩子链表中存储的结点是没有顺序之分的。也就是说传统的树没有任何约束度数可以任意孩子之间也没有次序。 为此我们引入了二叉树。二叉树规定每个节点的孩子最多只能有两个即度数2并且其孩子节点中左边的孩子叫做左孩子右边的叫右孩子。 二叉树也可以有多种情况如下图所示 如果一颗二叉树是满的比如一共三层每层都是满的。如下图所示 这个时候我们叫他满二叉树。
如果将一颗二叉树从下往上总右往左删除它们无论怎么删除它都是一颗完全二叉树。 也就是说如果一颗满二叉树少了A7但有A8其他不变那么这个二叉树就不是完全二叉树。并且满二叉树可以看做是完全二叉树的特别版。
8.4.2 高频考点
第一个比较常考的是关于求完全二叉树的高度。完全二叉树的高度由二叉树中的结点个数来决定。为了方便讲解我们先探究满二叉树的规律。通过列举或者通过高中的等比数列知识都是可以发现这个规律的。如下所示 也就是说一个高为h的满二叉树其结点为2h−12^h-12h−1。那么一个高位h的完全二叉树结点数肯定小于2h−12^h-12h−1且大于2h−1−12^{h-1}-12h−1−1。
我们可以将上述的不等式进行化简如下所示 至此我们可以导出完全二叉树的高度公式了。
有时候我们我们可能会见到不一样的公式这是因为在上述化简第二步时选择直接把1扔掉还是通过计算同时1的差异导致的。 408科目09年05题 已知一颗完全二叉树的第6层(设根为第1层)有8个叶结点则该完全二叉树的结点个数最多是 考虑到最多那么必然是这种情况 也就是说前五层结点数为2^5-1 31满6层的二叉树结点为2^6-1 63故第六层结点数为63-31 32又叶子结点为8故非叶子结点有32-8 24故这个完全二叉树的结点个数最多是6324*2111个 8.4.3 二叉树的性质
最简单的总分支数 总结点数-1这个很简单对于传统的树也是同样满足的。
设分支数为i的结点数为NiN_iNi则满足总结点数NN0N1N2N N_0N_1N_2NN0N1N2。同样地总分支数N−1N12N2N-1 N_12N_2N−1N12N2这个在我们前面学基础知识时就已经提到过了。
对于上述的方程我们可以解得N0N21N_0 N_21N0N21故叶子结点数 双分支结点数1这是一个非常重要的结论。有时考题里面会说二叉树含有空分支此时考题就更为灵活了需要注意一下。
对于一颗存储在数组的完全二叉树来说。 父结点位置如果为i则左孩子结点位置为2i1右孩子结点位置为2i2。
以上的规律在不同的学校考题中有所不同如果位序从1开始则左孩子结点位置为2i右孩子结点为2i1。
8.4.4 二叉链表
对于二叉树的链式存储来说和树的链式存储并无二致并且我们可以说明存放孩子结点的链表第一个结点为左孩子第二个结点为右孩子这完全没有问题。 但是我们可以回想我们使用孩子表示法的初衷。是由于每个子树度数的不确定性我们才使用这种方法但是现在二叉树确定了为何还要怎么搞岂不大材小用?
我们不如回归本心写一个结点结构体结构体中含有左右子结点的指针域和结点所含数据然后将所有结点放于数组中即可。 上述的结构我们称为二叉链表。
二叉链表实际上可以用在传统树的存储因为在之前的孩子表示法设计中某结点的孩子结点是作为链表接在结点的指针域中的所有孩子结点不需要都和父节点有关系只需要其中一个和父节点有关系即可。故我们可以改造传统树变成二叉链表能够存储的样子 以上这种表示方法我们称为孩子兄弟表示法。
8.4.5 树和二叉树的转换
前面说过的转换我们只是口头讲述并没有一种系统的方式来转换。
一种简单的方式是将兄弟结点用一条线连起然后只保留一条通往父节点的线其他多余的线删除如下图所示 删除线后我们把它掰成二叉树的模样即可。 如果想要将二叉树转为树只需要从根节点开始一条路从头走到尾途径的所有结点都加上一条线和根节点即可对于其他剩余的结点在也可以用同样的操作。如下图所示 然后掰回树。 8.4.6 森林和二叉树的转换 森林就是多棵树放在一起如果想要转换为二叉树只需将森林中的所有树先单颗转为二叉树。需要注意的是上图的第三颗树它看起来像是二叉树但我们不确定故我们也要对他做转化的工作全部转换后如下所示 全部的单树转换为二叉树后我们只需连接所有单树的根节点的右分支即可如下所示 同理如果想要将二叉树还原为森林只需将右分支删掉然后看看单树的根节点的右分支是否为空非空则继续删掉右分支为空则将所有单树还原为传统树即可。 408科目09年06题 将森林转换为对应的二叉树若在二叉树中结点u是结点v的父结点的父结点则在原来的森林中u和v可能具有的关系是 我们可以画出可能的二叉树如下所示 然后将按上述的方法还原结果u和v可能的关系有父子关系和兄弟关系。 8.5 遍历
遍历一词在如今才出现为何前面我们不提遍历因为前面一对一的线性结构的遍历过于简单只需从头到尾走一遍即可。
但是对于一对多的树我们要如何去遍历它呢
以二叉树为例我们需要制定一定的规则来访问。第一个遍历的想法是我们从上到下从左到右进行遍历如图所示 以上提到的这种思路我们叫做层次遍历也叫广度优先遍历。
我们还有第二种想法我们称为深度优先遍历。其又细分为先序、中序和后序遍历。
让我们来体会一下这个想法是怎么实现的。如下图所示 在这个过程中我们可以发现A2这个结点被走过三次如A1-A2-A4-A5-…这样就可以算一次遍历。但是我们如果说遍历是A4-A2-A5-A1-A6-A3…实际上也没有任何毛病。同样地A4-A5-A2-A6-A3-A1…也是可以的。
也就是说如果是先访问根节点然后先序遍历左子树最后遍历右子树则称为先序遍历如果是先遍历左子树然后访问根节点最后遍历右子树则称为中序遍历如果是先遍历左子树然后遍历右子树最后遍历根节点则称为后序遍历。
我们也可以换一种思考方式。如果一个结点第一次走过时就遍历它那么就是先序遍历如果走过第二次再遍历则称中序遍历如果走过第三次才遍历则称后序遍历。 408科目09年03题 答案明显是D。这里就不多解释了。 树的层次遍历和二叉树的差不多有差别的是深度优先遍历。如下所示 在树的遍历中每个节点就不一定是经过三次了故相对于前面的三种深度优先遍历方式这里只有两种即先序遍历和后序遍历。
我们前面说过树可以转换为二叉树。树的先序遍历和转换后的二叉树先序遍历是一样的而树的后序遍历和转换后的二叉树的中序遍历是一样的。 对于森林的遍历也很简单先序遍历指的就是从左到右对每一棵树进行先序遍历而后序遍历指的就是从左到右对每一棵树进行后序遍历。
同样的如果将森林转为二叉树其遍历的改变和树的改变是一样的。即森林的先序等效于转换后二叉树的先序森林的后序等效于二叉树的中序。
