Правильный вид бинарного дерева

Question

Вид бинарного дерева справа - это набор узлов, видимых при просмотре дерева с правой стороны.

My функция:

void rightView(Node *root)
{
if(root!=NULL)
    cout<<root->data<<" ";
while(root!=NULL)
{
    if(root->right!=NULL)
    {root=root->right; cout<<root->data<<" ";}

    else
    {
        root=root->left;

        if(root==NULL)
            break;
        else
            cout<<root->data<<" ";
    }
}
}

Для дерева выше, я получаю правильное представление как 58 68 63 67. Однако правильный ответ будет 58 68 63 67 3. Это произойдет, когда я перейду к 67, я вижу, что мой узел не имеет левого или правого потомка и выходит из l oop. Однако из-за этого поведения я пропустил потенциальные узлы, которые l ie на более низких уровнях. Также обратите внимание, что если бы узел 3 был дочерним по отношению к узлу 67, я получил бы правильный ответ.

Есть ли способ, которым я могу немного подправить свой код, когда я думал выполнить эту операцию без использования очереди?

PS - Я не очень хорошо выражаю свои проблемы в письменной форме. Пожалуйста, не будь враждебным.

Answer 1

Вот идея: итерация по глубине дерева и отслеживание на каждой итерации всех узлов на этой глубине. Убедитесь, что они отсортированы слева направо.

На каждой итерации: отобразите данные самого правого узла и создайте список узлов для следующей итерации.

Кроме того, я предлагаю вам очистить немного вашего кода. Например, вот тот же код, который вы опубликовали, но «очистили»:

void rightView(Node *root)
{
    while(root!=NULL)
    {
        cout<<root->data<<" ";

        if(root->right!=NULL)
            root=root->right;
        else
            root=root->left;
    }
}