已知<C,F>,<D,G>,<D,H>,<B,E>,<A,B >,<B,C>,<B,D>是表示一棵树中具有父子关系的边,要求1.分别利用树形表示法、嵌套集合表示法、凹入表表示法和广义表表示法描述树结构;2.分别利用双亲表示法、孩子链表表示法、孩子兄弟表示法存储此树。
时间: 2024-10-29 21:11:52 浏览: 32
1、已知一棵树边的集合为(I,m),(I,n),(e,i),(b,e),(b,d),(a,b),
1. **树形表示法 (Preorder Traversal)**:
这种表示法通常从根节点开始,然后访问左子树,最后访问右子树。根据给定的关系,我们可以构建如下的树形结构:
- 根节点 A (因为 <A, B>)
- 子节点 B (A的孩子):有 C 和 D 子节点 (<B, C>, <B, D>)
- 子节点 C (B的孩子)
- 子节点 D (B的孩子),并且 D 有 G 和 H 子节点 (<D, G>, <D, H>)
- 子节点 E (B的另一个孩子)
2. **嵌套集合表示法 (Nested Set Model)**:
这里每个节点包含自身ID以及其所属的最小和最大ID范围。例如:
```
{A: [1, 4], B: [2, 3], C: [3, 3], D: [4, 4], E: [4, 4], G: [], H: []}
```
3. **凹入表表示法 (Inverted Index or Level Order Index)**:
表示每个节点及其对应的层级。例如:
```
[
{0: [A]},
{1: [B, C]},
{2: [D]},
{3: [E]},
{4: [G]},
{5: [H]}
]
```
4. **广义表表示法 (Generalized List or Tree Adjoining Grammar)**:
类似于前序遍历序列,但可以包含子表作为元素,如 `[A, [B, [C]], [D, [G, H], E]]`
5. **双亲表示法 (Parent Pointer Method)**:
每个节点包含一个指向其直接父节点的指针。对于上述树结构,每个节点不会直接存储其他孩子的信息,而是通过路径找到它们。
6. **孩子链表表示法 (Child Linkage Method)**:
可能的形式是:
- A -> B -> C
- B -> D -> G -> null
- B -> D -> H -> null
- B -> E -> null
7. **孩子兄弟表示法 (Sibling Pointer Method or Sibling Linkage Method)**:
每个节点除了常规的数据外还包含指向同级下一个节点的指针。由于给定关系并不完整,假设每个节点都有这样的链接:
- A -> B
- B -> C
- C -> next (无后续节点)
- B -> D
- D -> G -> next (next为H)
- D -> H -> next (end of level)
- B -> E -> next (end of level)
阅读全文