|
|
|
知识路径： > 计算机科学基础 > 常用数据结构 > 树 > 树和二叉树 >
|
|
考试要求：掌握
相关知识点：11个
|
|
|
|
|
求集合{1, 2, …,n}的幂集是一个经典的问题。解决这个问题的最典型做法就是递归调用，传统的做法这里不再讨论。
|
|
|
|
如何利用树型结构这个参照系来设计求集合{1, 2, …,n}的幂集算法是我们讨论的重点。对于给定的集合{1,2,3,4}，按幂集集合中的元素个数和字典次序建立的树如下图所示。
|
|
|
|
|
|
|
|
为保持集合中元素的字典次序，可采用两种方法来求集合{1, 2, 3, 4｝的幂集集合，其一是采用前序遍历树；其二是按层次遍历树。特别要注意的是在设计求集合的幂集时并不建立真正的树，而是在考生的心中建立这样一个虚拟的树，并以这棵树为参照系。下面给出这两种方法的算法。
|
|
|
|
|
|
|
|
|
|
|
|
可见，灵活地应用树型结构及其遍历操作的思路，能有效地解决实际应用问题。
|
|
|
|
|
|
|
|
