2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 09:49 
Аватара пользователя


29/09/14
28
Добрый день всем!
Никак не могу допилить программу, прошу вашей помощи. Нужно реализовать программу обхода бинарного дерева. Обход в обратном порядке (спускаемся в левые ветви, потом в правые, потом поднимаемся наверх). Рекурсивным образом реализовал. Стековым ну никак не могу. Те примеры, что в интернете, работают некорректно: выдаются ветви в порядке возрастания, а не в обратном порядке. Где какое условие добавить, чтобы всё работало корректно?
Реализация стека верная, проверял на обычных числах (помещал их в стек и доставал), реализация рекурсивным способом верная. По идее прога запрашивает данные у пользователя, но чтобы не вводить каждый раз - в main помещаю значения в дерево прямо в коде. Рекурсивную оставил для сравнения работы. Реализация стекового способа в процедуре stacky(). Если кто подскажет, что у меня не так, буду премного благодарен.
Сейчас результат работы программы такой:
========================================
P:\Program Files\MinGW\mingw64\bin>gcc program2.c
P:\Program Files\MinGW\mingw64\bin>a.exe
----------------------
Now walk around the tree in the reverse order:
- in a recursive manner
1
4
6
5
3
10
12 <- have only one not empthy link
9 <- have only one not empthy link
7
Number of nodes with only one not empthy link: 2
- in a stack manner
1
3
4
5
6
7
9
10
12
P:\Program Files\MinGW\mingw64\bin>
========================================
код: [ скачать ] [ спрятать ]
Используется синтаксис C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 200

typedef struct node {
                int data;
                struct node *left;
                struct node *right;
                struct node *parent;
        } node;
       
node *Tree = NULL;
node *Top = NULL;
node *Node = NULL;

int count;

int addNode (int lem) {
        // Определяем элемент в памяти
        Node = (node*) malloc(sizeof(node));
        Node->data = lem;
        Node->left = NULL;
        Node->right = NULL;
        Node->parent = NULL;
        // Если он первый, инициализируем дерево
        if (Top == NULL) {
                Top = Node;
        } else {
                Tree = Top;
                // Пока не найдём свободное место
                while (Tree != NULL) {
                        //Если совпадают - заменяем
                        if (Tree->data == lem) {
                                Tree->data = Node->data;
                                break;
                        }
                        // Если больше - идём в правую ветку
                        if (Tree->data < lem) {
                                if (Tree->right != NULL) {
                                        Tree = Tree->right;
                                } else {
                                        Tree->right = Node;
                                        Node->parent = Tree;
                                        break;
                                }
                        }
                        // Если меньше - идём в левую ветку
                        if (Tree->data > lem) {
                                if (Tree->left != NULL) {
                                        Tree = Tree->left;
                                } else {
                                        Tree->left = Node;
                                        Node->parent = Tree;
                                        break;
                                }
                        }
                } //of while
        } //of else
        return 0;
}

void recursiv(node *Tree) {
    if (Tree != NULL) {
        recursiv(Tree->left);
        recursiv(Tree->right);
        printf("%d", Tree->data);
                if ( ((Tree->right) && (!Tree->left)) || ((!Tree->right) && (Tree->left)) ) {
                        printf("\t<- have only one not empthy link");
                        count++;
                }
                printf("\n");
    }
}

typedef struct {
        node *buf[MAX_SIZE];            // Буфер стека
        unsigned size;                                  // Указатель
} stackArray;

void initstackArray(stackArray *stack) {
        stack->size = 0;
}

static void stacky(stackArray *stack, node *Tree){
        node *TreeOld = NULL;
        while ((Tree != NULL) || (stack->size != 0)) {
                if (stack->size != 0) {
                        //pop(stack, Tree);
                        if (stack->size == 0) {
                                exit(2);
                        }
                        stack->size--;                                                 
                        Tree = stack->buf[stack->size];
                        printf("%d\n",Tree->data);
                        Tree=Tree->right;
                }
                while (Tree!=NULL) {                   
                        //push(stack, Tree);
                        if (stack->size == MAX_SIZE) {
                                exit(1);
                        }
                        stack->buf[stack->size] = Tree;
                        stack->size++; 
                        //
                        Tree=Tree->left;
                }
        }
}

int main () {
        int num;
       
        //printf("Hello!\nLet's start filling the tree. To do this, enter the elements.\n");
        //printf("After each item press Enter. To complete the entry, enter END\n");
        do {
                addNode(7);
                addNode(9);
                addNode(3);
                addNode(1);
                addNode(5);
                addNode(4);
                addNode(6);
                addNode(12);
                addNode(10);
                num = 0;
                /* scanf("%d",&num);
                if (num != 0) {
                        addNode(num);
                } */

        } while (num != 0);
        printf("----------------------\nNow walk around the tree in the reverse order:\n");
       
        printf("- in a recursive manner\n");
        count = 0;
        Tree = Top;
        recursiv(Tree);
       
        printf("- in a stack manner\n");
        count = 0;
        Tree = Top;
        stackArray stack;
        initstackArray(&stack);
        stacky(&stack,Tree);
        return 0;
}
 

 Профиль  
                  
 
 Re: Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 12:43 
Заслуженный участник


02/08/11
6874
Поменять местами right и left. (Неожиданно, правда?)

 Профиль  
                  
 
 Re: Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 12:48 
Аватара пользователя


29/09/14
28
warlock66613 в сообщении #1362907 писал(а):
Поменять местами right и left. (Неожиданно, правда?)

Поменял right на left и left на right в процедуре. В результате получается неверный обход:
12
10
9
7
6
5
4
3
1

 Профиль  
                  
 
 Re: Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 13:50 


27/08/16
9426
FirstKarmeliy в сообщении #1362867 писал(а):
потом поднимаемся наверх
Потом корень поддерева, после обхода всех его потомков, сначала левых, потом правых.

С реализацией вашего стека мне разбираться лень, если вы не произвели функциональную декомпозицию своего кода, выделив элементарные операции в отдельные функции.

 Профиль  
                  
 
 Re: Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 15:25 
Заслуженный участник


02/08/11
6874
FirstKarmeliy, ну раз с наскока не получилось, остаётся открыть книжку с нужным алгоритмом (или просто википедию):
Используется синтаксис Pascal
iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // если правый потомок существует и обход пришёл из левого потомка, двигаемся вправо
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()

и закодировать этот алгоритм. Тот, что у вас в программе, на правильный не похож.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group