树形结构的3中搜索方式示例分享

2026-01-16 16:36:47 作者：用户投稿

复制代码代码如下:
/**
树的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;
  }
}
}