1

我正在尝试使用 C 中的堆栈实现深度优先搜索。但是，我很难弄清楚应该如何使用堆栈。我只能将每个树节点的值压入堆栈。如何推送节点本身，以便我可以回溯并找到前一个节点的子节点？

void printorder(struct node* node, struct stack *pt) {
  if (node == NULL) {
    return;
  }

  if (!(node == NULL) || node->visited = false) {
    push(pt,node->data); //pushing root to stack
    int v = pop(&pt);
    printf("Value of pushed node %d",v);
    node->visited = true;
    push(pt,node->left->data);
  }
}

int main(void) {
  struct stack *pt = newStack(9); //Creating new stack with max capacity 9 (amount of nodes we have total)
  struct node *root = newNode(4); //creating root of tree with value 4
  root->left = newNode(7);
  root->right =newNode(98);
  root->left->left = newNode(28);
  root->left->left->left = newNode(77);
  root->left->left->right = newNode(23);
  root->left->right = newNode(86);
  root->left->right->left = newNode(3);
  root->left->right->right = newNode(9);
  printorder(root,pt);    
  return 0;
}
4

1 回答 1

0

递归中序树遍历

顺序、深度优先的树遍历不需要显式堆栈。递归使用进程的调用堆栈作为隐式数据结构。您提供的代码实际上是这样做的，尽管它似乎将堆栈推送/弹出和递归调用混为一谈，并且忽略了对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;
}

迭代中序树遍历

如果您确实需要迭代地执行此操作，那么您将比递归版本做更多的工作。

第一个设计选择是使堆栈在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;
}
于 2019-11-08T20:12:14.553 回答