Chuyển cây nhị phân

Question

Làm thế nào để chuyển một cây nhị phân (không phải là một cây cân bằng) trên hai hệ thống khác nhau một cách hiệu quả, giữ lại cấu trúc hoàn chỉnh của nó?

Answer 1

Cách rõ ràng là chuyển đổi cây nhị phân của bạn thành một mảng các nút, thay thế mỗi con trỏ trong cây gốc bằng chỉ mục thành một nút trong mảng. Sau đó, bạn có thể truyền mảng đó và đầu kia tạo lại một cây có cấu trúc giống hệt nhau.

Answer 2

Cấu trúc này đưa ra dưới đây

[x] 
/ \ 
[L] [R] 
    \ 
    [P] 

có thể được dịch một cách dễ dàng vào

(X,(L,-,(P,-,-)),(R,-,-)) 

Ngoài ra, đọc một bài đăng bởi Eric Lippert.

LƯU Ý: Tôi cảm thấy, điều tương tự sẽ hoạt động cho các cây tùy ý. Có ý kiến ​​gì không?

Answer 3

Xác định chức năng tuần tự hóa.

void serialize(FILE *f, my_tree *node, _Bool is_root) { 
    if (node == NULL) { 
     fputc(no_child, f); 
     return; 
    } 

    if (! is_root) fputc(data_prefix, f); 
    write_data(f, node->data); 
    fputc(data_terminator, f); 

    write_data(node->left_child); 
    write_data(node->right_child); 
} 

void deserialize_node(FILE *f, my_tree *node) { 
    node->data = read_data_field(f); 

    if (fgetc(f) != no_child) { 
     node->left_child = calloc(1, sizeof(my_tree)); 
     deserialize(f, node->left_child, false); 
    } 

    if (fgetc(f) != no_child) { 
     node->right_child = calloc(1, sizeof(my_tree)); 
     deserialize(f, node->right_child, false); 
    } 
} 

Hãy đến với suy nghĩ của nó, chương trình này đơn giản (nơi data_terminator và no_child phải là ký tự đơn) cho phép cả hai data_terminator và no_child để được bình đẳng.

Answer 4

Vấn đề chính với điều này là bạn phải thay thế con trỏ hoặc tham chiếu từ biểu diễn bộ nhớ của bạn bằng một thứ khác có thể được sử dụng để biểu thị rõ ràng nút đã được trỏ tới.

 foo 
    / \ 
cat  zebra 
    \ 
    dog 

Một cách để làm điều này là trao đổi con trỏ cho khóa - giống như chỉ mục mảng hơn con trỏ thích hợp.

1 2 "foo" 
3 _ "cat" 
_ _ "zebra" 
_ _ "dog" 

Trong đại diện này lĩnh vực đầu tiên là số dòng (tính bắt đầu từ 0, đó là nút gốc) của trẻ bên trái, lĩnh vực thứ hai là con bên phải, và lĩnh vực thứ ba là giá trị. Cây được sắp xếp theo thứ tự bảng chữ cái. Điều này có vẻ đơn giản, nhưng có thể khó thực sự.

Cách tiếp cận tương tự sẽ đặt khóa trong mỗi mục nhập thay vì dựa vào vị trí. Phương pháp này có thể sử dụng các con trỏ ban đầu như các phím và mã đọc sẽ phải xây dựng một bảng dịch/biểu tượng để chuyển đổi giữa các khóa và các con trỏ mới.

Một cách khác để đi về việc này là với một cây lisp-esque: (foo (cat() (chó()()) (ngựa vằn()()))

định dạng để xem dễ dàng:

(foo 
    (cat 
    () 
     (dog 
     () 
     () 
    ) 
    ) 
    (zebra 
     () 
     () 
    ) 
) 

Điều này có thể dễ dàng tạo ra bằng cách truyền tải đơn giản theo thứ tự. Nó cũng có thể được đọc bằng trình phân tích cú pháp đệ quy rất đơn giản. Bạn cũng có thể thay đổi điều này để giảm kích thước các nút lá theo định dạng được tuần tự hóa bằng cách bỏ qua số nil hoặc () hoặc bất kỳ thứ gì bạn đã chọn cho con trỏ NULL.

Phương pháp khác, tương tự như phương pháp đầu tiên, là lưu trữ tất cả các cây trong một đoạn bộ nhớ có thể được đổ vào và đọc lại từ đĩa.Các con trỏ trong này sẽ liên quan đến phần đầu của bộ nhớ này, chứ không phải là các con trỏ tuyệt đối. Đây sẽ là một cách nhanh chóng cho hai chương trình trên cùng một loại máy (sử dụng cùng chiều rộng bộ nhớ CPU) để chia sẻ cây (hoặc các đồ thị khác), nhưng có khả năng khó thực hiện.

Phiên bản lisp-esqe này rất dễ triển khai, nhưng không dễ dàng mở rộng đến những thứ không phải là cây, nơi có thể có tham chiếu tuần hoàn hoặc nhiều hơn một phụ huynh cho một nút cụ thể, mặc dù nó có thể được làm. Nó cũng không dễ dàng mở rộng để xử lý lưu trữ nhiều hơn một cấu trúc trong một tập tin cụ thể.

Phiên bản chỉ mục vị trí dòng hoạt động cho hầu hết các loại biểu đồ, nhưng việc lưu trữ nhiều cấu trúc trong một tệp cụ thể sẽ cần phải thay đổi định dạng này một chút.

Bất kể bạn chọn gì, bạn sẽ cần đảm bảo rằng bạn có thể xử lý tất cả các giá trị có thể có mặt dưới dạng dữ liệu nút. Ví dụ: nếu dữ liệu nút có thể chứa ", ) hoặc \n thì có thể gây ra sự cố ở một số định dạng mà tôi đã hiển thị và các ký tự đó sẽ cần phải được thoát. Bạn có thể tiền tố các lĩnh vực với chiều dài của họ hoặc sử dụng bố trí cấu trúc liên tục để tài khoản cho điều này, mặc dù.

Bạn cũng sẽ cần đảm bảo rằng bất kỳ trường nhị phân nào được lưu trữ theo kiểu nhất quán cuối cùng nếu bạn định chia sẻ dữ liệu giữa các loại máy khác nhau. Bạn cũng sẽ muốn dữ liệu này có kích thước nhất quán (sử dụng các loại stdint.h chứ không phải int và dài) và một biểu diễn kinh điển cho những thứ như số dấu phẩy động.

Answer 5

Tiếp cận 1: Chúng ta có thể đi qua cây hai lần:

1. Lần đầu tiên để có được những InOrder Traversal
2. SecondTime để có được những PostOrder Traversal

Bây giờ Bằng cách sử dụng hai danh sách những khách tại điểm hẹn chúng tôi có thể tái tạo cây nhị phân như sau:

public class ConstructBinaryTreeFromInorderAndPostorder { 

    int index; 

    public TreeNode buildTree(List<Integer> inOrder, List<Integer> postOrder) { 
     index = postOrder.size() - 1; 
     if (postOrder.size() == 1) 
      return new TreeNode(postOrder.get(0)); 

     return constructTree(inOrder,postOrder, 0, postOrder.size() - 1); 
    } 


    public TreeNode constructTree(List<Integer> inOrder, List<Integer> postOrder, int start, int end) { 

     if (start > end) { 
      return null; 
     } 
     TreeNode root = new TreeNode(postOrder.get(index--)); 

     if (start == end) { 
      return root; 
     } 
     int indexInInorder = search(inOrder, start, end, root.val); 

     root.right = constructTree(inOrder, postOrder, indexInInorder + 1, end); 
     root.left = constructTree(inOrder, postOrder, start, indexInInorder - 1); 


     return root; 
    } 


    public int search(List<Integer> inOrder, int strt, int end, int value) { 
     int i = 0; 
     for (i = strt; i <= end; i++) { 
      if (inOrder.get(i) == value) 
       return i; 
     } 
     return i; 
    } 

    public static void main(String[] args) { 
     List<Integer> inorder = Arrays.asList(2, 1, 3); 
     List<Integer> postOrder = Arrays.asList(2, 3, 1); 
     System.out.println(new ConstructBinaryTreeFromInorderAndPostorder().buildTree(inorder,postOrder)); 
    } 
} 

Để Lấy InOrder Traversal:

public class InorderTraversal { 
    void inOrderTraversal2(TreeNode node) { 
     if (node == null) { 
      return; 
     } 
     inOrderTraversal2(node.left); 
     System.out.println(node.val); 
     inOrderTraversal2(node.right); 
    } 
} 

Để Lấy PostOrder Traversal:

public class PostOrderTraversal { 

    void postOrderTraversal(TreeNode node) { 
     if (node == null) { 
      return; 
     } 
     postOrderTraversal(node.left); 
     postOrderTraversal(node.right); 
     System.out.println(node.val); 
    } 
} 

Phương pháp 2: Chúng ta có thể tiết kiệm không gian bằng cách lưu trữ Preorder traversal và một dấu hiệu cho null con trỏ. Để điểm đánh dấu cho null con trỏ là '-1'

Input: 
    12 
    /
    13 
Output: 12 13 -1 -1 

Input: 
     20 
    / \ 
    8  22 
Output: 20 8 -1 -1 22 -1 -1 

Input: 
     20 
    / 
     8  
    /\ 
    4 12 
    /\ 
    10 14 
Output: 20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1 

Input: 
      20 
     / 
     8  
    /
    10 
    /
    5 
Output: 20 8 10 5 -1 -1 -1 -1 -1 

Input: 
      20 
      \ 
      8 
       \ 
       10 
       \ 
        5 
Output: 20 -1 8 -1 10 -1 5 -1 -1