中企动力网站报价科技公司起名字大全免费

当前位置： 首页 > news >正文

中企动力网站报价,科技公司起名字大全免费,潘家园网站建设公司,wordpress中文主题排行引入 我们现在提倡节约型杜会#xff0c; 一切都应该节约为本。对待我们的程序当然也不例外#xff0c;能不浪费的时间或空间#xff0c;都应该考虑节省。我们再观察团下图的二叉树#xff08;链式存储结构)#xff0c;会发现指针域并不是都充分的利用了#xff0c;有许…引入 我们现在提倡节约型杜会 一切都应该节约为本。对待我们的程序当然也不例外能不浪费的时间或空间都应该考虑节省。我们再观察团下图的二叉树链式存储结构)会发现指针域并不是都充分的利用了有许多的空指针域的存在这实在不是好现象应该要想办法利用起来。通常对于这种情况的常用做法就是使其存储某些数据方便某种操作 举个我们之前学习单链表的时候我们在学习单链表的时候采用的是带头结点的链式存储结构。通常头结点的数据域是不存储数据的但是我们可以令其存储当前链表的长度。因为单链表的特殊性当我们需要知道链表的长度时就需要从头到尾遍历链表时间复杂度为O(n)但是如果我们在头结点的数据域存储当前链表的长度就可以使上述操作的时间复杂度变成O(1)。 回到二叉树的讨论中首先我们要来看着这空指针有多少个呢对于一个有n个结点的二叉树每个结点有指向左右孩子的两个指针域所以一共是 2n 个指针域。而 n个结点的二叉树一共有 n -1条分支线数也就是说其实是存在 2n  - (n -1)  n 1个空指针域。如上图二叉树的结构示意图所示共有10个结点11个空指针域。这些空间不存储任何事物白白的浪费着内存的资源。那对于二叉树该如何利用这些空间资源 线索二叉树的定义 回想之前讲述的二叉树的遍历前、中、后、层序遍历)。我们在做遍历时比如上图二叉树的结构示意图做中序遍历时得到了H-D-I-B-J-E-A-F-C-G 这样的字符序列遍历过后我们可以知道结点I的前驱结点是D后继结点是B结点F的前驱结点是A后继结点是C。也就是说我们可以很清楚的知道任意一个结点它的前驱和后继是哪一个。可是这是建立在已经遍历过的基础之上的。在二叉链表上我们只能知道每个结点指向其左右孩子结点的地址而不知道某个结点的前驱是谁后继是谁。要想知道必须遍历一次。以后每次需要知道时都必须先遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢那将是多大的时间上的节省。 综合刚才两个角度的分析后我们可以考虑利用那些空地址存放指向结点在某种遍历次序下的前驱和后继结点的地址。就好像 GPS 导航仪一样我们开车的时候哪怕我们对具体目的地的位置一无所知但它每次都可以告诉我从当前位置的下一步应该走向哪里。这就是我们现在要研究的问题。 我们把这种指向前驱和后继的指针称为线索加上线索的二叉链表称为线索链表相应的二叉树就称为线索二叉树(Threaded Binary Tree) 。 我们把这棵二叉树进行中序遍历后1、将这棵二叉树的所有空指针域中的lchild改为指向当前结点的前驱。因此H的前驱是NULL(图中)I的前驱结点是D(图中)J的前驱结点是B(图中③)F的前驱结点是A(图中④)G的前驱结点是C(图中⑤)。一共5个空指针域被利用。2、将所有的空指针域中的rchild改为指向它的后继结点。于是我们就可以通过指针知道H的后继结点是DI的后继结点是 BJ的后继结点是EE的后继结点是AF的后继结点是CG的后继结点因为不存在而指向 NULL。此时共有6个空指针域被利用。总共加起来11个空指针域全部利用 通过上图的右图所示(空心箭头为前驱结点实心黑箭头为后继结点)就更容易看出其实线索二叉树等于是把一棵二叉树转变成了一个双向链表这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。 线索二叉树的结构实现 结点结构实现 现在我们已经知道了线索二叉树的概念和实现的思路但问题并没有彻底解决。我们如何知道某一结点的lchild 是指向它的左孩子还是指向前驱结点rchild 是指向右孩子还是指向后继结点比如E结点的lchild是指向它的左孩子该结点的rchild 却是指向它的后继结点A。显然我们在决定lchild 是指向左孩子还是前驱结点rchild 是指向右孩子还是后继上是需要一个区分标志的。因此我们在每个结点再增设两个标志域lTag和rTag。注意lTag和rTag的类型没有明确的限制按照自己的编程习惯来。通常使用0、1这种布尔值类型。 关于线索二叉树的结点定义如下(C/C混编) using TBTree_Type int; typedef struct TBNode {TBTree_Type val;struct TBNode* lChild;struct TBNode* rChild;PointerTag lTag;PointerTag rTag;}TBNode; 成员变量解释 lTag为0时指向该结点的左孩子为1时指向该结点的前驱结点。rTag为0时指向该结点的右孩子为1时指向该结点的后继结点。 其中关于PointerTag的类型其实是对枚举类型的封装而已 typedef enum { Link, //Link 0Thread //Thread 1 } PointerTag; 因此对于图6-10-1的二叉链表图可以修改为下图所示的样子 线索化 现在关于线索二叉树的结点结构已经给出那么假设现在给你一颗二叉树的根结点那么你要怎么将其变成线索二叉树我们之前已经提过其实线索二叉树等于是把一棵二叉树转变成了一个双向链表而我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。 线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继结点的信息只有在遍历该二叉树时才能得到所以线索化的过程就是在遍历的过程结点中修改空指针的过程。 现在以中序遍历线索化为例总体的实现思路如下结点空指针域前驱的填入需要知道刚刚访问的结点后继的填入需要知道下一个访问的结点所以可以用一个 pre 指针专门用于记录刚刚访问的结点也就是现在访问的结点的上一个结点)。总体实现思路如下 如果当前结点的左孩子为空那么就将当前结点的左孩子指向prev同时修改当前结点左孩子的标记那么当前结点的前驱节点就存储完成后继结点的存储会比较复杂一点需要判断prev的右孩子是否为空如果为空那么就将prev的右孩子指向当前结点同时修改prev右孩子的标记 代码实现如下 int inorder_thread(TBNode* root, TBNode* prev) {if (root nullptr)return;inorder_thread(root-lChild, prev);if (root-lChild nullptr){root-lTag Thread;root-lChild prev;}if (prev ! nullptr prev-rChild nullptr){prev-rTag Thread;prev-rChild root;}prev root;inorder_thread(root-rChild, prev); } 形参解释 root二叉树的根结点prev指向刚刚访问过的结点也就是现在访问的结点的上一个结点 【注意】关于prev指向谁如果不理解一定要去画图理解 如果有学过C的话这份代码没有什么难度没学过的话我重点提一下形参的TBNode* prev‘’代表引用就是给变量起别名。不理解也没关系直接用二级指针TBNode* prev替代、或者使用全局变量。 我们还是来演示一段代码的执行逻辑。从二叉树的根结点开始此时prev指向空指针NULL)因为当前一个结点都还没有访问接下来直接递归根结点的左子树中序遍历的次序)找到中序遍历的第一个结点‘H’此时的root指向结点为‘H’的结点prev还是为NULL判断root的左孩子是否为空如果为空那么就将root的左孩子指向prevroot-lChild prev)再将左孩子的结点的标记lTag变成1root-lTag Thread)只是当前结点的前驱结点就存储完成了 由于当前prev为空指针域因为中序遍历的第一个访问的结点为H‘没有比它更早访问的了。接下来将prev指向root因外要去遍历当前结点root的右子树因为root的右子树为空直接回到结点D这时prev的右孩子为空那么就将prev的右孩子指向当前结点root prev-rChild root)同时修改prev的右孩子的标记prev-rTag Thread)再将prev指向当前结点root因为下一步要去遍历root的右子树了。 不画了剩下的步骤一样只要注意prev的改动即可。 遍历操作 有了线索二叉树后我们对它进行遍历时发现其实就等于是操作一个双向链表结构。 和双向链表结构一样在二叉树线索链表上添加一个头结点如下图所示并令其 lchild 域的指针指向二叉树的根结点(图中的①)其rchild 域的指针指向中序遍历时访问的最后一个结点(图中的②)。反之令二叉树的中序序列中的第一个结点中Ichild 域指针和最后一个结点的rchild 域指针均指向头结点(图中的③和④)。这样定义的好处就是我们既可以从第一个结点起顺后继结点进行遍历也可以从最后一个结点起顺前驱结点进行遍历。 代码实现如下 void thread_inorder(TBNode head) {TBNode* root head-lChild;//根结点while (root ! head){while (root-lTag Link)//查找遍历的第一个结点{root root-lChild;}while (root-rTag Thread root-rChild ! head){printf(%c , root-val);root root-rChild;}root root-rChild; //root进入它的右子树} } 从这段代码也可以看出它等于是一个双向链表的扫描所以时间复杂度为 O(n)。由于它充分利用了空指针域的空间(这等于节省了空间)又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。所以在实际问题中如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继那么采用线索二叉链表的存储结构就是非常不错的选择。说实话我几乎就没有用过线索二叉树话又说回来你可以不用但是不能不会。可以作为一种拓展知识吧。