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

Question

今天，我学习了 3 个针对有根树的 DFS（深度优先搜索）遍历，即，中序、预序和 Post 序遍历。

比如我考虑先序遍历，

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 表示）来维护网络元素的层次结构（指标），叶节点的深度非常好巨大.

渐近地，space前序遍历的复杂度为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);
    }
}

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

Rooted tree with huge depth - DFS Traversal algorithm performance

c

algorithm

tree

traversal

data-structures