Các hoán vị có thể có của đầu vào BST

Question

Tôi có một chuỗi, tức là "CPHBDZ". Bằng cách chèn (theo thứ tự này) thư cho một BST tôi sẽ có:

C 
/\ 
B P 
/\ 
    H Z 
/
D 

Nếu chúng ta thay đổi thứ tự của chuỗi để "CBPHDZ" chúng tôi sẽ có được cây giống hệt nhau. Và tôi phải tìm và liệt kê tất cả các hoán vị của chuỗi đầu vào cung cấp cùng BST. Tôi đã nghĩ ra cách tính một số hoán vị nhưng tôi không thể tìm ra bất kỳ thuật toán nào thực sự tìm thấy chúng.

Answer 1

Giả sử bạn không làm bất kỳ phép quay nào (v.v) để cân bằng cây, bạn có thể lấy được câu trả lời từ cấu trúc của cây: các nút mới luôn được thêm dưới dạng con cháu của các nút hiện có, vì vậy bất kỳ nút nào cao hơn trong cây phải đứng trước con cháu của nó, nhưng có thể được sắp xếp lại theo ý muốn với "đồng nghiệp" của nó (bất cứ thứ gì không phải là cha mẹ của nó cũng không phải là hậu duệ). Ví dụ, vì bạn có C làm gốc của cây, C phải là mục đầu tiên được đọc từ luồng. Vì hậu duệ của nó là B và P, mục tiếp theo trong đầu vào phải là một trong hai mục đó. B không có con cháu nào, nhưng P có hai: H và Z, vì vậy chúng phải được đọc sau P, nhưng có thể theo thứ tự bất kỳ theo số B. Tương tự, Z có thể theo bất kỳ thứ tự nào đối với H và D, nhưng H phải đứng trước D.

Chỉnh sửa: Khi tạo tất cả các hoán vị đó, một cách đơn giản (gian lận) sẽ là sử dụng Prolog. Về cơ bản, bạn mã hóa các phụ thuộc đó là "sự kiện", và nó sẽ tạo ra tất cả các hoán vị phù hợp với những sự kiện đó. Trong thực tế (không có ý định chơi chữ), đây là một mô tả khá rõ về những gì Prolog đang làm.

Tự mình làm, có thể bạn muốn thực hiện hầu hết công việc đệ quy. Một thứ tự hợp lệ là một gốc, theo sau là bất kỳ sự xen kẽ nào của các đơn đặt hàng hợp lệ của con cháu của nó.

Theo như cách thực hiện đan xen, bạn sẽ (ví dụ) tạo một thứ tự hợp lệ của cây con bên trái và một thứ tự hợp lệ của cây con bên phải. Đặt chúng lại với nhau thành một mảng với tất cả các mục từ cây con bên trái lúc đầu, và tất cả các mục từ cây con bên phải ở cuối. Để trình diễn, giả sử cây cũng chứa một số A (như là hậu duệ của số B bạn hiển thị). Trong một mảng, dữ liệu của chúng tôi từ các cây con của chúng ta sẽ trông giống như:

B A P H Z D 

Sau đó chúng tôi bắt đầu từ mục cuối cùng từ các cây con bên trái, và "đi" từng qua mảng bên phải, tạo một hoán vị mới mỗi lần:

B P A H Z D 
P B A H Z D 
B P H A Z D 
P B H A Z D 
P H B A Z D 
[ ... ]  

Đối với mỗi đơn hàng có giá trị của cây con bên trái, bạn cần phải làm tất cả những interleavings với mỗi đơn hàng có giá trị của cây con bên phải (và gửi lại cho cha mẹ, mà sẽ làm y hệt).

Answer 2

Trong Python,

tree = { 
    'C' : ['B', 'P'], 
    'P' : ['H','Z'], 
    'H' : ['D']} 

def f(tree, ready): 
    if not ready: 
     return [[]] 
    else: 
     rv = [] 
     for r in ready: 
      for rest in f(tree, 
          [n for n in ready if r != n] + tree.get(r, [])): 
       rv.append([r] + rest) 
     return rv 

for o in f(tree, 'C'): 
    print ''.join(o)