问题描述
问题解答
回答1：这个其实不难，我修改了下代码，写了点注释，你可以看看。加了点输出语句，显示下搜索计算的过程
> ./a.out dudduduudu0 --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 => %dn', 0,0); return 0; } int i = 0; curTreeDep = curBtreeDep = -1; searchStack.push_back(nodeID); dfs(i, 0, 0); printf('%d => %dn', curTreeDep, curBtreeDep); return 0; }
