1

私は現在、再帰に頭を悩ませようとしているので、c++の教科書を選んで読み始めました。再帰の章の最初の数ページは理解しやすかったのですが、それから私には意味のない項目にたどり着きました。 

 int height(node *p)
 {
    if(p==NULL)
       return 0;
    else{
   return 1 + max(height(p->llink),height(p->rlink));

  }

maxが2つの値のうち最大のものを私に与える場合、maxはどのようにして返される高さから引数を取得しますか。誰かが助けてくれるなら、私はそれを大いに感謝します.....

4

2 に答える 2

6

再帰を理解するには、再帰的に考える必要があります。

  • 空の木の高さは0であることがわかります
  • 一般的な空でないツリーの高さは1+最長のサブツリーの高さ（左からまたは右からのサブツリーの場合があります）であることが理解できます。

これから始めて、コードを簡単に理解することができます。木を描くと、何が起こるかがわかります。あなたが例えば持っているなら

     A
    / \
   B   C
  / \  
 D   E
  • height(A)戻ります1 + max(height(B), height(C))
  • height(B)戻ります1 + max(height(D), height(E))
  • height(C)戻ります1 + max(height(NULL), height(NULL)) = 1
  • height(D)戻ります1 + max(height(NULL), height(NULL)) = 1
  • height(E)戻ります1 + max(height(NULL), height(NULL)) = 1

それで

height(A) = 1 + max(height(B), height(C)) =
= 1 + max(1 + max(height(D),height(E)), 1) =
= 1 + max(1 + 1, 1) = 1 + max(2, 1) = 3

（私はへの呼び出しを省略しましheight(NULL)た。なぜなら、それらは自明に0であり、そうでなければ、あまりにも冗長になっていたからです。）

于 2012-11-01T18:50:05.820 に答える
2

関数への引数は、関数呼び出しの前に評価されます。

したがって、同等の例は次のようになります（おそらくもっと意味がありますか？）：

int height(node *p)
 {
    if(p==NULL)
       return 0;
    else{
       int heightLeftSubtree = height(p->llink);
       int heightRightSubtree = height(p->rlink);
       return 1 + max(heightLeftSubtree, heightRightSubtree);
    }
 }
于 2012-11-01T18:54:55.683 に答える