二叉树递归的可视化

Question

编写一个递归函数，显示由xs、0和1组成的字符串表示的所有二进制(以2为基数)数。x表示可以是0或1的数字。例如，字符串xx代表数字00、01、10、11。

代码可以工作，但是我很难将中间步骤可视化。有人能帮我演练一下吗?

void get_first_x(char *line,char *line2,char *line3);
void display(char *line);
int main(int argc, const char * argv[]) {
    char line[256];
    printf("Binary number: ");
    scanf("%s",line);
    display(line);
    return 0;
}

void display(char *line){

    char line2[80];
    char line3[80];
    if(strchr(line,'x') == NULL)
    {
        printf("%sn",line);
        return;
    }
   get_first_x(line,line2,line3);

    display(line2);
    display(line3);
  }
   void get_first_x(char* line,char* line2,char *line3) {
    char* check;
    check = strchr(line,'x');
    *check = '0';
    strcpy(line2,line);
    *check = '1';
    strcpy(line3,line);
}//replacement of x with 0 and 1. One argument produces 2 strings

这是我的看法

1st call     display(xx)
2nd call       display(0x)
3rd call          display(00) { print statement/ return}
                     display(1x)
                        display(01) { print statement/return}
                          display(10) { print statement/return}
                           recursion exits
 Input: xx
 output: 00,01,10,11
 I'm not understanding something...here

Answer 1

您实现的是这样的(在伪代码中):

display(line) {
  if no_x_in(line) {
     print(line)  // instance output and recursion stop 
  } 
  display(replace_first_x_with_0(line))  // recursive call
  display(replace_first_x_with_1(line))  // recursive call
}

• 如果line中的字符串不再包含x符号，则可以输出该字符串并停止递归下降。

• 如果不存在，则将问题实例从具有n倍x符号的line简化为具有n - 1多个x符号的两个较小的实例，

  • 用0符号替换x和
  • 将x符号替换为1符号。

，它们各自导致递归调用。由于在有限的输入字符串中只有有限的x符号，因此递归调用将在某个点停止，并且生成的调用树也是有限的。

对于您的示例，调用树是这样的:

display('xx') -> issues calls to display('0x') and display('1x')
|
+-> display('0x') -> issues calls to display('00') and display('01')
|   |
|   +-> display('00') -> output, stop
|   +-> display('01') -> output, stop
|
+-> display('1x') -> issues calls to display('10') and display('11')
    |
    +-> display('10') -> output, stop
    +-> display('11') -> output, stop