网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
数据结构吧 关注：104,529贴子：883,643
  • 10回复贴，共1页

家人们，关于二叉树的中序线索化

之前学python的时候看了cs61a，里面有一章递归，讲了递归分为基类构造，然后递归环节，最后检查。而之前遇到的例子我也都用这套思路畅通无阻。因为基类的构造一般都很简单，比如遍历树就是空树直接返回，斐波那契这种都很简单。
但是中序线索化这个基类不是太懂，虽然确实能读懂代码流程，但是这个思路的构造过程我不是很懂。有没有8u帮忙讲一讲这个算法的basecase构造环节如何思考（因为这里涉及到pre和p俩节点了，所以不知道basecase该咋抽象出来）


pre是一个全局变量，初始化为NULL,p为🌲的指针，没学过python基类是c里面的结构体吗？


递归函数别想复杂了，脑海中假装已经实现了这个递归函数，再在自己的函数中利用这个“实现过的递归函数”就大概可以弄明白了


那我有个疑惑，你可以替我解答吗，背景：数据结构的kruskal算法的时间复杂度为O(eloge)是边逆序排序的时间复杂度，它的查找和union的时间复杂度为O((v+e)α(v))其中α(v)是一个增长极其缓慢的函数。问题：为什么查找和union的时间复杂度为上述，而不是O((eα(v)+v)其中eα(v)是查找时间复杂度，v是遍历结点。详情可以看算法导论一书的27章关于最小生成树的kruskal算法，其中有讲到这个，但是数学功底薄弱的我看不太懂，可以为我解答一下疑惑吗？


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 10回复贴，共1页
分享到: