具有巨大深度的根树-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（网络管理系统）应用程序中，我们使用根树（LCRSrepresentation）来维护网络元素（度量）的层次结构，其中叶节点的深度非常大。

渐近地，预序遍历的空间复杂度是O（d），其中d是最低叶的深度。

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

例如-如果考虑访问节点序列（如上所述），则在访问第三节点时从根到叶维护调用堆栈。

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

注意：在构造时，树如下所示

Answer 1

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

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);
    }
}