这个其实不难，我修改了下代码，写了点注释，你可以看看。
加了点输出语句，显示下搜索计算的过程

> ./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  #include  #include  #include  using namespace std; const int N = 100100; char s[N]; int curTreeDep, curBtreeDep; // 当前一般树和二叉树的深度 // ======>>> 添加输出部分，可删除 int nodeID = 0; std::vector 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; }