- /**
- 树的3中常见搜索方式
- 1.二叉树方式(每一层只有0和1)
- 2.满m叉树(每一层都有0 到m - 1)
- 3.子集树,也称为全排列树
- */
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <string>
- using namespace std;
- const int M = 20;
- int n, m;
- int ans[M];
- //二叉树
- void dfs_two(int cur){
- if(cur == n){
- for(int i = 0; i < n; i++){
- cout << ans[i] << " ";
- }
- cout << endl;
- return;
- }
- ans[cur] = 1;
- dfs_two(cur + 1);
- ans[cur] = 0;
- dfs_two(cur + 1);
- }
- //m叉树
- void dfs_m(int cur){
- if(cur == n){
- for(int i = 0; i < n; i++){
- cout << ans[i] << " ";
- }
- cout << endl;
- return ;
- }
- for(int i =0; i < n; i++){
- ans[cur] = i;
- dfs_m(cur + 1);
- }
- }
- bool vis[M];
- //子集树
- void dfs_sub(int cur){
- if(cur == n){
- for(int i = 0; i < n; i++){
- cout << ans[i] << " ";
- }
- cout << endl;
- return;
- }
- for(int i = 0; i < n; i++){
- if(false == vis[i]){
- vis[i] = true;
- ans[cur] = i;
- dfs_sub(cur + 1);
- vis[i] = false;
- }
- }
- }
- int main(){
- n = 5;
- memset(ans, -1, sizeof(ans));
- memset(vis, false, sizeof(vis));
- dfs_two(0);//二叉树搜索
- dfs_m(0);//满m叉树搜索
- dfs_sub(0);//子集树搜索
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/3107201410080.html
来源: http://www.codesnippet.cn/detail/3107201410080.html