Двоичное дерево — Печать только левых веток — Использование PostOrder Traverse

Question

Двоичное дерево — Печать только левых веток — Использование PostOrder Traverse

Привет!
Я хотел бы знать, что может быть условием оператора if, чтобы все левые ветви двоичного дерева могли быть напечатаны с использованием обхода после заказа.

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";

}

}

0

binary-tree c++cout postorder

Решение

Другие решения

здесь идет код для прохождения заказа

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

1

Попробуй это

 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;
}

0

if(!bt->left()==NULL)
cout << bt->left()->getData() << "\t";

0

Источник

Accepted Answer

Я понимаю, что вы хотите посетить только узлы, которые были видны из левой ветви. Поскольку это почтовый заказ, вы должны посетить их, когда вернетесь на нужную ветку. Таким образом, как сказал πάντα ῥεῖ, вы можете использовать логический флаг, указывающий, из какого типа ветви вы обнаружили узел.

Таким образом, возможный путь будет следующим:

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

2