如何在树中链接同一级别的所有节点
Dima Kozyr
我有一棵二叉树：
struct node
{
int n; // value of node
struct node *left; // left subtree
struct node *right; // right subtree
struct node *level; // level pointer (node “to the right”)
}
最初，级别字段设置为NULL。
我毫不费力地编写了一个函数，该函数将在一棵树中的同一层链接所有节点（不仅来自示例，而且来自任何给定的树）。
void linkSameLevel(struct node *t);
对于包含n个节点的深度为d的树，我如何知道函数的运行时间和内存使用情况？
这是我所拥有的：
这是我需要的：
虚幻灵魂007
为此，可以使用两个队列和BFS遍历。并维护两个指针currNode和prevNode。
- 在Q1中推根。
- 从Q1开始并进行初始化
prevNode = null。 - 从第一季度开始，然后对其进行初始化
currNode。在第二季度中推送currNode的子代。 - 现在，如果
prev != null，则prevNode与链接currNode。 - 现在
prevNode = currNode。 - 从第3步重复进行，直到Q1不为空。
当Q1为空时。将Q2设置为Q1，将Q1设置为Q2（新的Q2将为空）并设置
prevNode = null。转到步骤3。void linkSameLevel(node *root) { if (root = null) return; queue<node *> Q1, Q2; Q1.push(root); node *currNode; node *prevNode; prevNode = null; do { while (!Q1.empty()) { node *currNode = Q1.pop(); Q2.push(currNode.left); Q2.push(currNode.right); if (prevNode != null) prevNode.level = currNode; prevNode = currNode; } swap(Q1, Q2); } while (!Q1.empty); }
还可以看一下水平订单遍历
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
如何在MongoDB中的嵌入式文档中获得同一级别的所有字段
- 2
如何在Perl中使用XML :: LibXML访问处于同一级别的具有相同标签的节点？
- 3
Selenium / Python：如何在与另一个类处于同一级别的某个类中捕获按钮的所有实例？
- 4
Python scrapy：如何通过检测同一级别的类来抓取链接？
- 5
如何在同一级别的组件之间传递内容？
- 6
如何获得具有相同属性的同一级别的元素或数据列表？
- 7
如何在两个组件处于同一级别的情况下使用前向引用引用dom节点
- 8
如何在DOT中将节点放置在同一级别上？
- 9
是否可以在doxygen中与主/索引页面处于同一级别的两个链接
- 10
从同一级别的不同目录中删除具有相同名称的子目录
- 11
如何将Java文件编译到与Java文件处于同一级别的目录中？
- 12
解析与beautifulsoup4中的html标记处于同一级别的文本
- 13
如何在d3js中创建下一级别的流程图
- 14
使用D3.JS在同一级别上显示所有叶子
- 15
当所有子模块处于同一级别时，git-svn分支
- 16
使用D3.JS在同一级别上显示所有叶子
- 17
如何在同一级别上对齐TextField和Text
- 18
如何在同一级别使用不同的键解析JSON数组
- 19
使用mongodb聚合根据条件从数组以及同一级别的其他字段中获取对象
- 20
同一级别中的3列
- 21
从同一级别的另一个模块导入Python模块
- 22
折叠时更改同一级别的前一个图标
- 23
折叠时更改同一级别的前一个图标
- 24
XSLT 1.0将同一级别上具有相同值的多个相同节点分组
- 25
树命令列出一级所有文件
- 26
OWL对象属性域/范围限制为同一级别的类
- 27
将pathlib的relative_to用于同一级别的目录
- 28
WPF ContentPresenter覆盖同一级别的其他控件
- 29
与导航栏位于同一级别的公司名称
我来说两句