2014 dxdy logo

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

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




 
 Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 09:49 
Аватара пользователя
Добрый день всем!
Никак не могу допилить программу, прошу вашей помощи. Нужно реализовать программу обхода бинарного дерева. Обход в обратном порядке (спускаемся в левые ветви, потом в правые, потом поднимаемся наверх). Рекурсивным образом реализовал. Стековым ну никак не могу. Те примеры, что в интернете, работают некорректно: выдаются ветви в порядке возрастания, а не в обратном порядке. Где какое условие добавить, чтобы всё работало корректно?
Реализация стека верная, проверял на обычных числах (помещал их в стек и доставал), реализация рекурсивным способом верная. По идее прога запрашивает данные у пользователя, но чтобы не вводить каждый раз - в 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 
Поменять местами right и left. (Неожиданно, правда?)

 
 
 
 Re: Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 12:48 
Аватара пользователя
warlock66613 в сообщении #1362907 писал(а):
Поменять местами right и left. (Неожиданно, правда?)

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

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

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

 
 
 
 Re: Си. Обратный обход бинарного дерева с помощью стека
Сообщение21.12.2018, 15:25 
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 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group