Cách duyệt mà không cần sử dụng đệ quy n Cây chẻ đôi?

Cách đệ quy:

di chuyển ngang (Nút nút)
{
    if(nút == null)
        return;

    for(Node con : node.getChilds()) {
        đi ngang qua(con);
    }
}

câu trả lời hay nhất

Những gì bạn đang làm về cơ bản là một DFS của cây. Bạn có thể sử dụng ngăn xếp để loại bỏ đệ quy:

di chuyển ngang (Nút nút) {
    nếu (nút==NULL)
        return;

    ngăn xếp stk;
    stk.push(nút);

    while (!stk.empty()) {
        Nút trên cùng = stk.pop();
        for (Nút con trong top.getChildren()) {
            stk.push(con);
        }
        quá trình (trên cùng);
    }
}

Nếu bạn muốn BFS sử dụng hàng đợi:

di chuyển ngang (Nút nút) {
    nếu (nút==NULL)
        return;

    hàng đợique;
    que.addRear(nút);

    trong khi (!que.empty()) {
        Nút phía trước = que.deleteFront();
        for (Nút con ở phía trước.getChildren()) {
            que.addRear(con);
        }
        quá trình (phía trước);
    }
}

Nếu bạn muốn duyệt theo cách khác, bạn phải làm theo cách tiếp cận tương tự, mặc dù sử dụng cấu trúc dữ liệu khác để lưu trữ các nút. Có thể là hàng đợi ưu tiên (nếu bạn muốn đánh giá một hàm tại mỗi nút và sau đó xử lý nút đó dựa trên giá trị đó).

Về thuật toán - duyệt cây n-ary mà không đệ quy, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/5987867/