Cây nhị phân có chứa cây khác không?

Question

Được rồi, tôi đã được hỏi câu hỏi này trong một cuộc phỏng vấn hôm nay và nó như sau:

"Cho biết một cây nhị phân có trong cây nhị phân khác hay không (chứa ngụ ý cả về cấu trúc và giá trị của các nút)"

tôi nghĩ đến phương pháp sau đây:

Flatten cây lớn như:

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}} 

(tôi đã thực sự viết mã cho điều này, {-} ngụ ý có sản phẩm nào lef t hoặc phải phụ cây, mỗi cây con được kèm theo trong ngoặc {})

Bây giờ cho cây con nhỏ chúng ta cần phải phù hợp với mô hình này:

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}} 

nơi {.*} biểu thị một sản phẩm nào hay không trống cây con.

Vào thời điểm đó tôi nghĩ, đây sẽ là một mô hình regex tầm thường phù hợp với vấn đề trong java nhưng tôi bị giật. Thực ra bây giờ tôi cảm thấy, tôi vừa chuyển đổi vấn đề (tạo ra một con quái vật khác).

Có một lớp lót regex đơn giản nào phù hợp với các mẫu này không? Tôi hiểu có thể có các cách tiếp cận khác để giải quyết vấn đề này và điều này có thể không phải là cách tốt nhất. Tôi tự hỏi liệu điều này có thể giải quyết được không.

Answer 1

Tôi không chắc người phỏng vấn có ý nghĩa gì bằng cách "chứa bên trong một cây nhị phân khác". Nếu người phỏng vấn đã yêu cầu một phương pháp để kiểm tra xem A có phải là cây con của B hay không, thì đây là một phương pháp không yêu cầu regex ở tất cả:

• Làm phẳng cây A và B sử dụng đặt hàng trước để lấy chuỗi, nói , Preá và preB
• Flatten cây A và B sử dụng inorder traversal để có được chuỗi, nói, INA INB và
• Hãy chắc chắn bao gồm null lá trong chuỗi như tốt (sử dụng khoảng trắng chẳng hạn)
• Kiểm tra nếu preA là chuỗi con của preB AND inA là chuỗi con của inB

Lý do bạn muốn bao gồm các lá rỗng là vì khi nhiều nút có cùng giá trị, đơn đặt hàng trước và inorder có thể không đủ. Dưới đây là một ví dụ:

  A 
     A  A 
    B  B  C 
C   D  B 
D   C  D 

Bạn cũng có thể kiểm tra này:

checking subtrees using preorder and inorder strings

Cũng đọc để biết thêm về đặt hàng trước và inorder traversals cây nhị phân:

http://en.wikipedia.org/wiki/Tree_traversal

Bây giờ, nếu anh ấy KHÔNG có nghĩa là chỉ các subtrees, vấn đề có thể trở nên phức tạp hơn tùy thuộc vào người phỏng vấn có nghĩa là "một phần". Bạn có thể xem câu hỏi dưới dạng một vấn đề đẳng cấu đồ thị (cây chỉ là một tập hợp con của biểu đồ) và đây là NP-complete.

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

Có thể có cách tiếp cận tốt hơn kể từ khi cây được nhiều hơn nữa hạn chế và đơn giản hơn đồ thị.

Answer 2

Bạn có thể thực hiện điều này bằng cách sử dụng kiểm tra chuỗi con như được mô tả trong các câu trả lời khác và chỉ sử dụng một truyền tải (đặt hàng trước, theo thứ tự hoặc đặt hàng), miễn là bạn đang in toàn bộ của mỗi nút trong cây, không chỉ giá trị của chúng. Ví dụ, một cây nhị phân là một trong hai

• cây rỗng, mà chúng tôi sẽ in như null, hoặc
• một giá trị và hai cây, mà chúng tôi in như (value left-tree right-tree), nơi left-tree và right-tree được thay thế bởi các đại diện của các subtrees trái và phải.

Mỗi cây bây giờ có một rõ ràng đại diện được in, và do đó, một cây T là một cây con của một cây S khi và chỉ khi chuỗi đại diện của T là một chuỗi con của chuỗi đại diện của S.

Ví dụ, cây

A 
/\ 
    B C 
/\ 
D E 

được biểu diễn dưới dạng

(A (B (D null null) (E null null)) (C null null)) 

và bạn có thể kiểm tra xem các subtrees của cây này có các chuỗi

(A (B (D null null) (E null null)) (C null null)) 
(B (D null null) (E null null)) 
(D null null) 
(E null null) 
(C null null) 

mỗi trong số đó là một chuỗi con của chuỗi cho toàn bộ cây. Tất nhiên, chỉ có những trường hợp biểu diễn chuỗi các giá trị ảnh hưởng đến việc tuần tự hóa các cây (ví dụ, các chuỗi giá trị chứa dấu cách, hoặc dấu ngoặc đơn, & c.), Do đó, để làm cho điều này mạnh mẽ, bạn ' d muốn thực hiện các biện pháp thích hợp với dấu phân tách hoặc thoát.

Cũng lưu ý rằng không phải mọi chuỗi là chuỗi con của cây tương ứng với chuỗi con của cây. Ví dụ, chuỗi null) (E là một chuỗi con của cây, nhưng không tương ứng với cây con của cây; chỉ khi một chuỗi s là đại diện của một cây t điều đó có nghĩa rằng nếu s là một chuỗi con của chuỗi s' của một cây t' rằng t là một cây con của t '.

Answer 3

Nói đúng, regex không được trang bị để xử lý các dấu ngoặc lồng nhau. Có thể kết hợp lồng nhau bằng cách sử dụng recursive regular expressions, nhưng công cụ regex của Java không hỗ trợ các biểu thức đệ quy.Trong PERL hoặc PHP, bạn có thể sử dụng mẫu như sau:

{(?:(?R)|-)}\w{(?:(?R)|-)} 

để khớp với cấu trúc cây, nhưng bạn vẫn không thể chỉ định giá trị của nút con ở các cấp cụ thể.

Vì vậy, rất tiếc, không có một dòng regex dễ dàng nào giải quyết được vấn đề này. Regex không phải là công cụ bạn cần cho công việc này.

Để trả lời câu hỏi này, tôi muốn giới thiệu xây dựng cây lớn và cây nhỏ, sau đó gọi largeTree.contains(smallTree) sử dụng các lớp sau:

public class BTreeNode 
{ 

public String value; 
public BTreeNode left; 
public BTreeNode right; 

public bool contains(BTreeNode tree) 
{ 
    bool retVal = visit(tree, this); 

    if (!retVal && left != null) 
    retVal = left.contains(tree.left); 

    if (!retVal && right != null) 
    retVal = right.contains(tree.right); 

    return retVal; 
} 

private bool visit(BTreeNode small, BTreeNode large) 
{ 
    bool retVal; 

    if (small == null) 
    { 
    retVal = true; 
    } 
    else if (small.value.equals(large.value)) 
    { 
    retVal = visit(small.left, large.left) && visit(small.right, large.right); 
    } 
    else 
    { 
    retVal = false; 
    } 

    return retVal; 
} 

} 

Trường hợp xấu nhất, một traversal của cây nhỏ sẽ được thực hiện cho mỗi nút của cây lớn, là O(m * log n) trong đó m là kích thước của cây lớn và n là kích thước của cây nhỏ. trường hợp xấu nhất có thể đạt được khi mọi phần tử của cả cây lớn và cây nhỏ đều bằng nhau, và cây nhỏ thực sự là một nút lớn hơn cây lớn.