Algorithm cho Tree Traversal

Question

Cập nhật:
tôi thấy nhiều hơn một ví dụ về những gì tôi đang cố gắng để kéo off: Managing Hierarchical Data in MySQL. Tôi muốn làm điều đó nhưng bằng JavaScript bởi vì tôi đang xây dựng một ứng dụng nhận các nhận xét có cấu trúc phân cấp, cụ thể hơn là reddit.com. Nếu bạn có phần mở rộng Khá JSON trên trình duyệt web chrome của bạn, hãy truy cập reddit và nhấp vào một chuỗi nhận xét và sau đó thêm .json vào url để xem tôi đang phân tích cú pháp gì.
Tôi nhận được dữ liệu JSON tốt, chỉ phân tích cú pháp thông qua các nhận xét và thêm HTML thích hợp để hiển thị lồng nhau của nó.
Ý tưởng về giải pháp?

---

OLD câu hỏi:
tôi đang làm việc trên một chương trình và tôi đã đi đến một phần mà tôi cần phải tìm ra logic trước khi tôi viết mã. Tôi đang lấy dữ liệu ở định dạng cây nhưng với khả năng của một số nút con cho mỗi nút cha và cây duy nhất tôi có thể tìm dữ liệu trên cây có trọng số hoặc cây nơi có nhiều nút nhất có hai nút con. Vì vậy, tôi đang cố gắng để tìm ra các thuật toán để đánh giá mỗi nút của cây như thế này:

startingParent[15] // [# of children] 
    child1[0] 
    child2[5] 
     child2ch1[4] 
     ... 
     child2ch5[7] 
    child3[32] 
    ... 
    child15[4] 

Bây giờ khi tôi cố gắng viết ra như thế nào thuật toán của tôi sẽ làm việc tôi sẽ viết lồng nhau cho/vòng lặp while nhưng tôi cuối cùng viết một vòng lặp cho mỗi cấp độ của chiều cao của cây cho dữ liệu động và cây có chiều cao không xác định với số lượng không xác định của trẻ em trên mỗi nút điều này không hoạt động. Tôi biết rằng vào một thời điểm nào đó, tôi đã học được cách đi qua một cái cây như thế này nhưng nó đã hoàn toàn thoát khỏi tôi ngay bây giờ. Bất cứ ai biết làm thế nào điều này được thực hiện trong điều khoản của vòng?

Answer 1

Nếu bạn không sử dụng đệ quy, bạn cần cấu trúc dữ liệu phụ trợ. Một hàng đợi sẽ cung cấp cho bạn một bề rộng đầu tiên, trong khi một chồng sẽ cung cấp cho bạn một chiều sâu đầu tiên đi qua. Dù bằng cách nào nó trông gần như thế này:

structure <- new stack (or queue) 
push root onto structure 
while structure is not empty 
    node <- pop top off of structure 
    visit(node) 
    for each child of node 
    push child onto structure 
loop 

Wikipedia Tham khảo

• Queue
• Stack

Answer 2

Sử dụng đệ quy, chứ không phải vòng lặp.
Breadth first search
Depth first search
Những sẽ giúp bạn bắt đầu với những gì bạn đang cố gắng để hoàn thành

Answer 3

Chỉ cần sử dụng đệ quy như

def travel(node): 
    for child in node.childs: 
     # Do something 
     travel(child) 

Answer 4

Mã đơn giản nhất đối với hầu hết duyệt cây thường là đệ quy. Đối với một cây đa chiều giống như cây của bạn, thường dễ nhất là có một vòng lặp nhìn vào mỗi con trỏ đến một đứa trẻ và tự gọi chính nó với nút đó làm đối số, cho tất cả các nút con.