Бинарное дерево

@TpukcTep · Регистрация: 18.06.2013

Доброго времени суток. Ребят, я не спец, требуется решить такую задачу:

Написать нерекурсивную программу, печатающую все вершины двоичного дерева. При реализации использовать стек отложенных заданий.Узлы дерева – символы латинского алфавита.
Дерево задается в файле в формате:
m [e [c [a], g [k] ], s [p [o,s], y ] ]
Рисунок, поясниющий пример:

Есть код:

Кликните здесь для просмотра всего текста

C++

struct node {
    char data;
    node *left, *right;
    int visited;
    node() : visited(0) {}
};
 
void print(node *root) {
    if (!root) {
        std::cout << "Tree is empty.";
        return;
    }
    std::stack <node *> stack;
    stack.push(root);
    root->visited = 1;
    node *cur;
    while (!stack.empty()) {
        cur = stack.top();
        if (cur->left && !cur->left->visited) {
            stack.push(cur->left);
            cur->left->visited = 1;
        } else if (cur->right && !cur->right->visited) {
            stack.push(cur->right);
            cur->right->visited = 1;
        } else {
            std::cout << cur->data << " ";
            stack.pop();
        }
    }
}

Компилятор ругается на то, что stack не является членом "std".
Помогите разрешить.
Извиняюсь за повторение темы, но не могу писать в прошлую.

@Vladimir. · 18.07.2013, 23:10

#include<stack>
?

@TpukcTep · 19.07.2013, 00:59 **[ТС]**

Как всё просто оказывается

Добавлено через 1 час 44 минуты
Теперь другая проблема

Дописал код:

Кликните здесь для просмотра всего текста

C++

struct node {
    char data;
    node *left, *right;
    int visited;
    node() : visited(0) {}
};
 
void print(node *root) {
    if (!root) {
        std::cout << "Tree is empty.";
        return;
    }
    std::stack <node *> stack;
    stack.push(root);
    root->visited = 1;
    node *cur;
    while (!stack.empty()) {
        cur = stack.top();
        if (cur->left && !cur->left->visited) {
            stack.push(cur->left);
            cur->left->visited = 1;
        } else if (cur->right && !cur->right->visited) {
            stack.push(cur->right);
            cur->right->visited = 1;
        } else {
            std::cout << cur->data << " ";
            stack.pop();
        }
    }
}
void main()
{
    setlocale(LC_ALL,"Russian");
    char* ifName = new char[1024];
    cout << "Введите входное имя файла " << endl;
    cin >> ifName;
    FILE* _if = fopen(ifName, "r");
    char* input = new char[2048];
    fscanf(_if, "%s\n", input);
    fclose(_if);
    const char *strpos = input;
    char c,b;
    node *cur;
    c = *strpos;
    cur->data = *strpos;
    c = *++strpos;
    for (int i=1;i<strlen(input);i++)
    {
        if (c == '[')
            c=*++strpos;
        if ((c >= 'a') && (c <= 'z'))
        {
            b=cur->back->data;
            if (b>c)
            {
                cur->left->data=c;
                c=*++strpos;
                cur->left;
            }
            else
            {
                cur->right->data=c;
                c=*++strpos;
                cur->right;
            }
        }
        if ((c == ']') || (c == ','))
        {
            cur->back;
            c=*++strpos;
        }
    }
    print(cur); 
}

Пишет ошибку во время выполнения, что cur используется без инициализации. Что ему вначале присвоить??

@Vladimir. · 19.07.2013, 01:26

1.Вы работаете с данными которых нет. У вас есть описание узлов Node, но нигде не создается объетов objNode.
2. Раз уж вы описали функцию печати узлов (по сути: traverse), то логично и остальной "интерфейс"(вставить, найти, удалить)описывать функциями. Вам будет легче разбираться в коде.
3. просто посмотреть:
сторонний ресурс
в частности

@nikkk · 12.07.2015, 10:19

У меня такое же задание(
Пытаюсь рекурсивно перевести строку m [e [c [a], g [k] ], s [p [o,s], y ] ] в структуру node
Но заполняется только левая часть. Посмотрите, пожалуйста, что я не так делаю?(

C++

Node* convert(char* str){
    Node* node = new Node;
    node->data = str[i];
    if (str[i + 1] == '['){
        i += 2;
        node->left = convert(str);
        return node;
    }
    if (str[i + 1] == ']'){
        i++;
        return node;
    }
    if (str[i + 1] == ','){
        i += 2;
        node->right = convert(str);
        return node;
    }
}

@Vladimir. 377 / 228 / 79 Регистрация: 24.11.2009 Сообщений: 695
	18.07.2013, 23:10	2
	*#include<stack>* ? 1

@Vladimir. 377 / 228 / 79 Регистрация: 24.11.2009 Сообщений: 695
	19.07.2013, 01:26	4
	1.Вы работаете с данными которых нет. У вас есть описание узлов Node, но нигде не создается объетов objNode. 2. Раз уж вы описали функцию печати узлов (по сути: traverse), то логично и остальной "интерфейс"(вставить, найти, удалить)описывать функциями. Вам будет легче разбираться в коде. 3. просто посмотреть: сторонний ресурс в частности 1

Опции темы