括弧付きのツリー越え

Question

私はプログラムの仕方を自分自身で教えてみることにしました。Pythonバージョンの「コンピュータ科学者のように考える方法」を通して自分のやり方を工夫しています。練習問題についての質問をするのをやめようとしましたが（全体的な問題は自分で解決することなので）、これは私に困惑しています。

Inorderトラバーサル（式1 + 2 * 3を使って作業する）とツリーをトラバースして各ノードを印刷する関数を導入した後の第20章では、「printTreeInorderを修正して、オペランドのペア "と呼びます。私はこうして出力が（1+（2）* 3）のように見えると仮定しています。

私は一般的に再帰関数に苦労しており、これを苦労しています。左と右の呼び出しの前後で括弧を挿入しようとしましたが、機能しませんでしたが、関数スタックが5つ深くなると思っています。

私はこれで正しいトラックに誰かを置くことができますか？ありがとう、

ビリー。

Answer 1

は、私は、このように出力が(1+(2)*3)のようになりますと仮定しています。

私は、これが出力されなければならないとは思わない。私は、出力がすべきだと思う。「オペランドのすべてのオペレータとのペアの周りに括弧を置きます：私にとって(1+(2*3))

これを表示する最も簡単な方法は、オブジェクト指向のアプローチている

レッツ。抽象クラスNodeは、抽象メソッドGetExpressionString()とフィールドTokenです。

NodeからクラスOperand継承をしてみましょう、それがTokenを返すようにGetExpressionString()を実装します。 （例えば、'1'または'2'または'3'）。

がNodeからクラスOperator継承をしてみましょう、フィールドタイプNodeのLeftとRightを持っており、それが'(' + Left.GetExpressionString() + Token + Right.GetExpressionString() + ')'を返すようにGetExpressionString()を実装します。たとえば、Left = '2',Right = '3'およびToken = '*'の場合、結果は'(2*3)'です。

expression = new Operator(
       Token='+', 
       Left=new Operand(Token='1'), 
       Right=new Operator(
         Token='*', 
         Left=new Operand(Token='2'), 
         Right=new Operand(Token='3'))) 

expression.GetExpressionString()リターン'(1+(2*3))'の呼び出しのためのその後

。 C++での

Answer 2

このコードは、あなたのために働く必要があります。

void inorder(node1 *start) 
{ 
    if(!(start->left==NULL && start->right==NULL)) 
    cout<<"("; 
    if(start->left!=NULL) 
    inorder(start->left); 
    cout<<start->value; 
    if(start->right!=NULL) 
    inorder(start->right); 
    if(!(start->left==NULL && start->right==NULL)) 
    cout<<")"; 
}