c - 具有巨大深度的有根树 - DFS 遍历算法性能

Question

今天，我学习了 3 个针对有根树的 DFS(深度优先搜索)遍历，即，中序、前序和后序遍历。

例如，如果我考虑先序遍历，

typedef struct SiblingTreeNode {
    struct SiblingTreeNode *parent;
    void *item;
    struct SiblingTreeNode *firstChild;
    struct SiblingTreeNode *nextSibling;
} Node;

typedef struct LCRSTree {
    Node *root;
    int size;
} Tree;


void preOrderTraverse(Node * node) {
    visit(node);

    if (node->firstChild) {
        printf("\n|");
        preOrderTraverse(node->firstChild);
    }

    if (node->nextSibling) {
        printf("-->");
        preOrderTraverse(node->nextSibling);
    }
}

void preOrder(Tree *tree) {
    preOrderTraverse(tree->root);
}

---

然后按以下顺序访问节点，

实际工作于 NMS(网络管理系统)应用程序，我们使用有根树(LCRS 表示)来维护网络元素(指标)的层次结构，其中叶节点的深度非常大.

渐近地，前序遍历的空间复杂度是O(d)，其中d是最低叶的深度。

在应用这 3 种遍历中的任何一种时，由于堆栈溢出，应用程序很可能会崩溃。

例如 - 如果您考虑访问节点序列(如上)，当您访问第 3 个节点时，调用堆栈从根到叶维护。

使用上面给定的 Tree 表示，在不维护显式数据结构(如堆栈)的情况下，如何在有根树上优化遍历算法？

注意:在构建时，Tree 看起来像 this

Answer 1

先序遍历有一个非递归的解决方案，就是递归使用调用栈insdead的栈数据结构。如果内存仍然是个问题，您可以设计一个堆栈来将其中的一些卸载到存储中，并在需要时重新加载。

void iterativePreorder() {
    TreeNode top;
    if (root == null)
        return;

    Stack<SiblingTreeNode> st = new Stack<SiblingTreeNode>();
    st.push(root);

    while (!st.empty()) {
        top = st.pop();
        //do traversal effect
        if (top.right != null)
            st.push(top.right);
        if (top.left != null)
            st.push(top.left);
    }
}