Binary cây tìm kiếm traversal so sánh hai con trỏ cho bình đẳng

Question

Tôi đang đọc cuốn sách các thuật toán Cormen (nhị phân chương cây tìm kiếm) và nó nói rằng có hai cách để đi qua cây mà không đệ quy:

sử dụng ngăn xếp và một giải pháp phức tạp hơn nhưng tao nhã mà không sử dụng ngăn xếp nhưng giả định rằng hai con trỏ có thể được thử nghiệm cho sự bình đẳng

tôi đã thực hiện các tùy chọn đầu tiên (sử dụng stack), nhưng không biết làm thế nào để impleme nt sau này. Đây không phải là một bài tập về nhà, chỉ cần đọc để giáo dục bản thân mình.

Bất kỳ manh mối nào về cách triển khai phiên bản thứ hai trong C#?

Answer 1

Điều chắc chắn. Bạn không nói loại traversal bạn muốn, nhưng đây là giả mã cho một traversal trong trật tự.

t = tree.Root; 
while (true) { 
    while (t.Left != t.Right) { 
    while (t.Left != null) { // Block one. 
     t = t.Left; 
     Visit(t); 
    } 
    if (t.Right != null) {  // Block two. 
     t = t.Right; 
     Visit(t); 
    } 
    } 

    while (t != tree.Root && (t.Parent.Right == t || t.Parent.Right == null)) { 
    t = t.Parent; 
    } 
    if (t != tree.Root) {  // Block three. 
    t = t.Parent.Right; 
    Visit(t); 
    } else { 
    break; 
    } 
} 

Để nhận đơn đặt hàng trước hoặc sau, bạn sắp xếp thứ tự các khối.

Answer 2

Giả sử rằng các nút trong cây là tham chiếu và giá trị là tham chiếu, bạn luôn có thể gọi tĩnh ReferenceEquals method on the Object class để so sánh xem liệu tham chiếu cho bất kỳ hai nút/giá trị nào giống nhau không.