Рекурсивный обход дерева порядка
Нет необходимости в явном стеке для в порядке обхода дерева в глубину . Рекурсия использует стек вызовов процесса как неявную структуру данных. Код, который вы предоставили, практически делает это, хотя кажется, что он объединяет push / pop стека и рекурсивные вызовы и пренебрегает исследованием правого поддерева root.
Вот минимальный пример:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
int data;
struct node *left;
struct node *right;
};
void printInOrder(struct node *root) {
if (root) {
printInOrder(root->left);
printf("%d\n", root->data);
printInOrder(root->right);
}
}
struct node *newNode(int data) {
struct node *result = malloc(sizeof(*result));
memset(result, 0, sizeof(*result));
result->data = data;
return result;
}
void freeTree(struct node *root) {
if (root) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
int main() {
/* 0
/ \
1 2
/ \
3 4
/ \ / \
5 6 7 8 */
struct node *root = newNode(0);
root->left = newNode(1);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->left->left = newNode(5);
root->left->left->right = newNode(6);
root->left->right = newNode(4);
root->left->right->left = newNode(7);
root->left->right->right = newNode(8);
printInOrder(root);
freeTree(root);
return 0;
}
Итеративное прохождение по дереву inorder
Если вам нужно сделать это итеративно, вам предстоит гораздо больше работы, чем рекурсивной версии.
Первый вариант разработки - сделать ли стек внутренним по отношению к функции printInOrder и использовать простой массив, или написать класс стека. Написание стекового класса - это гораздо больше работы, но его можно использовать повторно (похоже, вы уже пошли по этому пути).
Что касается существующего заголовка функции, то немного странно заставлять вызывающую функцию выделять его. ресурсы, которые должны быть внутренними для вызова функции;в идеале printInOrder - это общий черный ящик без сохранения состояния, которому звонящий может доверить свою работу, не вызывая побочных эффектов .
Представьте себе, что вы делаете несколько вызовов printInOrder, используя один и тот же стекЭто может привести к неожиданным результатам или к тому, что вызывающему абоненту придется беспокоиться о распределении / освобождении этого стека.
Алгоритм обхода также становится более сложным. Вместо того, чтобы печатать данные узла в цикле, нам нужно поместить их в стек и перейти к его левому потомку, повторяя, пока текущий узел не станет нулевым. Затем мы можем напечатать вершину стека и сделать текущий узел правым дочерним узлом только что напечатанного узла. Повторяйте до тех пор, пока стек не будет исчерпан.
Вот итерационный алгоритм с внутренним стеком и работает как раскрывающийся пример кода выше:
void printInOrder(struct node *root) {
int capacity = 4;
int top = 0;
struct node **stack = malloc(sizeof(*stack) * capacity);
for (stack[top] = root; top >= 0;) {
for (root = stack[top--]; root; root = root->left) {
if (top >= capacity &&
!(stack = realloc(stack, sizeof(stack) * (capacity *= 2)))) {
fprintf(stderr, "%s [%d] realloc failed\n", __FILE__, __LINE__);
exit(1);
}
stack[++top] = root;
}
if (top >= 0) {
root = stack[top--];
printf("%d\n", root->data);
stack[++top] = root->right;
}
}
free(stack);
}
Вот версия, которая использует стеккласс. Логика намного чище, но мы ввели зависимость.
stack.h
#ifndef STACK_H
#define STACK_H
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
struct stack {
int top;
int capacity;
void **entries;
};
struct stack *createStack(int capacity) {
if (capacity <= 0) return NULL;
struct stack *s = malloc(sizeof(*s));
s->top = -1;
s->capacity = capacity;
s->entries = malloc(sizeof(*s->entries) * capacity);
return s;
}
bool empty(struct stack *s) {
return s->top < 0;
}
void freeStack(struct stack *s) {
free(s->entries);
free(s);
}
void *pop(struct stack *stack) {
if (stack->top < stack->capacity / 2 - 1) {
stack->entries = realloc(stack->entries,
sizeof(stack->entries) *
(stack->capacity /= 2));
if (!stack->entries) {
fprintf(stderr, "%s [%d] realloc failed\n", __FILE__, __LINE__);
exit(1);
}
}
return stack->entries[stack->top--];
}
void push(struct stack *stack, void *data) {
if (stack->top >= stack->capacity) {
stack->entries = realloc(stack->entries,
sizeof(stack->entries) *
(stack->capacity *= 2));
if (!stack->entries) {
fprintf(stderr, "%s [%d] realloc failed\n", __FILE__, __LINE__);
exit(1);
}
}
stack->entries[++stack->top] = data;
}
#endif
main.c
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
struct node {
int data;
struct node *left;
struct node *right;
};
void printInOrder(struct node *root) {
struct stack *stack = createStack(4);
for (push(stack, root); !empty(stack);) {
for (root = pop(stack); root; root = root->left) {
push(stack, root);
}
if (!empty(stack)) {
root = pop(stack);
printf("%d\n", root->data);
push(stack, root->right);
}
}
freeStack(stack);
}
struct node *newNode(int data) {
struct node *result = malloc(sizeof(*result));
memset(result, 0, sizeof(*result));
result->data = data;
return result;
}
void freeTree(struct node *root) {
if (root) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
int main() {
/* 0
/ \
1 2
/ \
3 4
/ \ / \
5 6 7 8 */
struct node *root = newNode(0);
root->left = newNode(1);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->left->left = newNode(5);
root->left->left->right = newNode(6);
root->left->right = newNode(4);
root->left->right->left = newNode(7);
root->left->right->right = newNode(8);
printInOrder(root);
freeTree(root);
return 0;
}