遍历n个节点能够形成的所有二叉树

时间:2022-12-15 11:27:24

帮师兄做的一个问题,就是求对n个不同节点能够形成所有的二叉树的形式,不考虑旋转对称性和同构。

问题描述:给定n个节点,查看能够有多少种不同的二叉树形成,并输出出来

算法描述:使用最基本的“分治法“(Divide and Conquer)思想,任选一个节点作为根节点,将剩余节点组成的集合进行分割(Partition),一部分放到左子树进行递归,另一部分放到右子树递归。重点为两部分:一部分使用二进制对集合进行分割,其实就是就集合的”幂集“,另一部分是如何存储。另外还可以进行暴力搜索。

测试用例:n=3,能够形成30种不同二叉树。

代码:

 1 #include <iostream>
2 #include <string>
3 #include <vector>
4 using namespace std;
5
6 vector< string > generate_tree(const vector< string > &nodes) {
7 if (nodes.empty()) {
8 return vector< string >{"*"};
9 } else if (1 == nodes.size()) {
10 return vector< string >{nodes[0]};
11 }
12 vector< string > trees, tmp, left, right, l_tree, r_tree;
13 for (size_t i = 0; i < nodes.size(); ++i) {
14 tmp = nodes;
15 tmp.erase(tmp.begin() + i);
16 for (size_t j = 0; j < 1<<tmp.size(); ++j) { // do set partition
17 left.clear();
18 right.clear();
19 for (size_t k = 0; k < tmp.size(); ++ k) {
20 if (!(j & (1<<k))) {
21 left.push_back(tmp[k]);
22 } else {
23 right.push_back(tmp[k]);
24 }
25 }
26 l_tree = generate_tree(left);
27 r_tree = generate_tree(right);
28 for (const string &l : l_tree) {
29 for (const string &r : r_tree) {
30 trees.push_back(nodes[i] + "(" + l + "," + r + ")");
31 }
32 }
33 }
34 }
35 return trees;
36 }
37
38 int main() {
39 vector< string > nodes{"A", "B", "C"};
40 vector< string > trees = generate_tree(nodes);
41 cout << trees.size() << endl;
42 for (auto &i : trees) {
43 cout << i << endl;
44 }
45 return 0;
46 }

由于使用c++11的特性,所以文件的编译命令为

g++ -std=c++11 generate_tree.cc


输出结果为

30
A(B(C,*),*)
A(B(*,C),*)
A(C(B,*),*)
A(C(*,B),*)
A(C,B)
A(B,C)
A(*,B(C,*))
A(*,B(*,C))
A(*,C(B,*))
A(*,C(*,B))
B(A(C,*),*)
B(A(*,C),*)
B(C(A,*),*)
B(C(*,A),*)
B(C,A)
B(A,C)
B(*,A(C,*))
B(*,A(*,C))
B(*,C(A,*))
B(*,C(*,A))
C(A(B,*),*)
C(A(*,B),*)
C(B(A,*),*)
C(B(*,A),*)
C(B,A)
C(A,B)
C(*,A(B,*))
C(*,A(*,B))
C(*,B(A,*))
C(*,B(*,A))

当n=4时,有336种

当n=5时,有5040种

相关文章