Rumah > Soal Jawab > teks badan
PHPz2017-04-17 15:34:27
这个其实不难,我修改了下代码,写了点注释,你可以看看。
加了点输出语句,显示下搜索计算的过程
> ./a.out
dudduduudu
0 --d-> 1 [T(0),BT(0),son_nu(1)]
0 <-u-- 1
0 --d-> 2 [T(1),BT(1),son_nu(2)]
2 --d-> 3 [T(1),BT(2),son_nu(1)]
2 <-u-- 3
2 --d-> 4 [T(2),BT(3),son_nu(2)]
2 <-u-- 4
0 <-u-- 2
0 --d-> 5 [T(2),BT(4),son_nu(3)]
0 <-u-- 5
2 => 4
修改的代码如下
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 100100;
char s[N];
int curTreeDep, curBtreeDep; // 当前一般树和二叉树的深度
// ======>>> 添加输出部分,可删除
int nodeID = 0;
std::vector<int> searchStack;
int tabscount = 0;
// <<<===== 添加输出部分结束
void dfs(int &i, int treeDep, int btreeDep)
{
// 以传入的深度与当前深度中的较大者为当前深度
curTreeDep = max(curTreeDep, treeDep);
curBtreeDep = max(curBtreeDep, btreeDep);
// 第几个子(当前搜索到的节点是)
int son_nu = 1;
while(s[i])
{
// d 为往下搜索,说明访问的是一个子节点
if(s[i] == 'd'){
// ======>>> 添加输出部分,可删除
for(int i = 0; i< tabscount;++i){
printf(" ");
}
++tabscount;
printf("%d --d-> %d [T(%d),BT(%d),son_nu(%d)]\n",
searchStack.back(),++nodeID,
curTreeDep,curBtreeDep,son_nu);
searchStack.push_back(nodeID);
// <<<===== 添加输出部分结束
// 递归下去继续访问
dfs(++i, treeDep + 1, btreeDep + son_nu);
// 当上面调用完成,说明是遇到了 u
// 也就是向上访问父节点
// 所以这里son_nu要加1,表示再次遇到d的时候
// 这个访问节点是第几个孩子
++son_nu;
}
else{
// ======>>> 添加输出部分,可删除
--tabscount;
for(int i = 0; i< tabscount;++i){
printf(" ");
}
int sid = searchStack.back();
searchStack.pop_back();
printf("%d <-u-- %d \n",searchStack.back(),sid);
// <<<===== 添加输出部分结束
++i; // i自增,下一个
return; // 递归结束控制
}
}
}
int main()
{
if(scanf("%s", s) < 1){
printf("%d => %d\n", 0,0);
return 0;
}
int i = 0;
curTreeDep = curBtreeDep = -1;
searchStack.push_back(nodeID);
dfs(i, 0, 0);
printf("%d => %d\n", curTreeDep, curBtreeDep);
return 0;
}