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