赞
踩
为了将多叉树的结点间“孩子兄弟”的信息以二叉树的形式保存下来,我们需要借助二叉树的左右两个子节点作为区分“孩子兄弟”的标记。
右图中结点 1 的左子节点是 4 表示 4 是 1 的 “孩子”, 4 的 左子节点是 7 表示 7 是 4 的左子节点,接着 4 的右子节点是 3 表示 3 是 4 的兄弟,即 1 的子节点,以此类推……不过要注意的是根节点 1 的左子节点可以是它“孩子”中的任何一个,没有要求,即不一定要和 4 相连,也可以和 2、3 中的其中一个相连。
- #include <iostream>
- #include <cstring>
- using namespace std;
- struct BT{
- int l;
- int r;
- }tree[100];
- int main(){
- memset(tree, 0, sizeof(tree)); // 初始化
- int m, a, b;
- cin >> m; // 有 m 条信息
- for (int i = 1; i <= m; i++){
- cin >> a >> b; // a 是 b 的子节点
- if (!tree[b].l) // b 的左子节点还有位置
- tree[b].l = a;
- else{ // b 的左子节点没有位置了,a 可以存在 b 的左子节点的右子节点上
- int tmp = b;
- while (tree[tmp].r) tmp = tree[tmp].r; // 循环找出空位,存放a;
- tree[tmp].r = a;
- }
- }
- return 0;
- }
好了,以上就是本期文章的全部内容了。。。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。