c++ - 二分木 - 左の分岐のみを出力 - PostOrder Traverse を使用 - C++

Question

やあ！if ステートメントの条件が何であるかを知りたいので、バイナリ ツリーのすべての左ブランチを postorder traverse を使用して出力できます。

template <class dataType>
void PrintLeft (BinaryTree <dataType> * bt) {

 if (!(bt == NULL))

 {

    //traverse left child

    PrintLeft (bt->left());

    //traverse right child

    PrintLeft (bt->right());

    //visit tree

    if(/*no idea what goes here*/)

    cout << bt->getData() <<"\t";

 }

}

Answer 1

左の分岐から見たノードだけにアクセスしたいということですね。ポストオーダーなので、正しいブランチに戻ったら訪問する必要があります。したがって、πάντα ῥεῖ が言ったように、ノードを発見したブランチのタイプを示すブール値フラグを使用できます。

したがって、可能な方法は次のようになります。

using Node = BinaryTree <int>; // or another type supporting << operator

void printLeft(Node * root, bool from_left)
{
  if (root == nullptr) // empty tree?
    return; 

  printLeft(root->left, true); // this node must be visited in postorder
  printLeft(root->right, false); // this one must not be visited in postorder

  if (from_left) //  was root seen from a left arc?
    cout << root->getData() << "\t"; // visit only if was seen from a left branch
}

根っこに曖昧さがあります。左のブランチから到達していないため (右からも) 到達していないため、印刷してはいけないと思います。

したがって、最初の呼び出しは次のようになります。

printLeft(root, false);

検証と同じように、このツリーの場合:

アルゴリズムは、次のシーケンスを左ポストオーダー トラバーサルとして生成します。

0 1 4 3 8 9 12 11 16 18

Answer 2

ここにポストオーダートラバースのコードがあります

void postorder(BinaryTree *bt)
{
    if(bt!=NULL)
    {
        postorder(t->lp);
        postorder(t->rp);
        //No Code Goes Here
        cout<<bt->data<<"\t";
    }
}

Answer 3

これを試してください

 void leftViewUtil(struct node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;

    // If this is the first node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }

    // Recur for left and right subtrees
    leftViewUtil(root->left, level+1, max_level);
    leftViewUtil(root->right, level+1, max_level);
}

// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

// Driver Program to test above functions
int main()
{
    struct node *root = newNode(12);
    root->left = newNode(10);
    root->right = newNode(30);
    root->right->left = newNode(25);
    root->right->right = newNode(40);

    leftView(root);

    return 0;
}