Pre-order Traversal sau khi đặt hàng

Question

Nếu việc duyệt qua đơn đặt hàng trước của cây tìm kiếm nhị phân là 6, 2, 1, 4, 3, 7, 10, 9, 11, cách nhận thông báo chuyển hàng sau?

Answer 1

Bạn được cung cấp thông tin đặt hàng trước của cây, được xây dựng bằng cách thực hiện: đầu ra, đi qua trái, đi ngang phải.

Khi quá trình truyền tải thứ tự đến từ BST, bạn có thể suy ra sự truyền tải theo thứ tự (di chuyển sang trái, đầu ra, sang phải) từ quá trình truyền tải theo thứ tự bằng cách sắp xếp các số. Trong ví dụ của bạn, quá trình truyền tải theo thứ tự là 1, 2, 3, 4, 6, 7, 9, 10, 11.

Từ hai lần truyền, chúng tôi có thể xây dựng cây gốc. Hãy sử dụng một ví dụ đơn giản cho việc này:

• Pre-order: 2, 1, 4, 3
• In-theo thứ tự: 1, 2, 3, 4

Các pre-order traversal cung cấp cho chúng tôi gốc của cây như 2. Traversal theo thứ tự cho chúng ta biết 1 rơi vào cây con bên trái và 3, 4 rơi vào cây con bên phải. Cấu trúc của cây con bên trái là tầm thường vì nó chứa một phần tử duy nhất. Sự đi ngang của cây con phải được suy ra bằng cách lấy thứ tự của các phần tử trong cây con này từ quá trình truyền tải thứ tự ban đầu: 4, 3. Từ đó chúng ta biết gốc của cây con bên phải là 4 và từ sự truyền tải trong trật tự (3, 4) chúng ta biết rằng 3 rơi vào cây con bên trái. Cây cuối cùng của chúng tôi trông giống như thế này:

2 
/\ 
1 4 
/
    3 

Với cấu trúc cây, chúng ta có thể đi ngang qua hàng cây: đi qua trái, đi ngang phải, đầu ra. Đối với ví dụ này, traversal bài theo đơn đặt hàng là 1, 3, 4, 2.

Để khái quát các thuật toán:

1. Yếu tố đầu tiên trong traversal đặt hàng trước là gốc rễ của cây. Các phần tử nhỏ hơn gốc tạo thành cây con bên trái. Các phần tử lớn hơn gốc tạo thành cây con bên phải.
2. Tìm cấu trúc của cây con trái và phải bằng cách sử dụng bước 1 với truyền tải đơn đặt hàng trước bao gồm các phần tử chúng tôi đã tạo ra trong cây con được đặt theo thứ tự chúng xuất hiện trong đơn đặt hàng ban đầu traversal.
3. Traverse cây kết quả theo thứ tự sau để nhận thông tin về trật tự sau được liên kết với lần truyền tải đơn đặt hàng đã cho.

Sử dụng thuật toán trên, quá trình truyền tải thứ tự được liên kết với truyền tải đơn đặt hàng trước trong câu hỏi là: 1, 3, 4, 2, 9, 11, 10, 7, 6. Bắt đầu bên trái như một bài tập.

Answer 2

Đặt hàng trước = xuất các giá trị của cây nhị phân theo thứ tự của nút hiện tại, sau đó là cây con trái, sau đó là cây con bên phải.

Đặt hàng sau = xuất các giá trị của cây nhị phân theo thứ tự của cây con trái, sau đó là cây con bên phải, nút hiện tại.

Trong số nhị phân tìm kiếm cây, giá trị của tất cả các nút trong cây con trái nhỏ hơn giá trị của nút hiện tại; và giống nhau cho cây con phải. Do đó nếu bạn biết bắt đầu một kết xuất trước của một cây tìm kiếm nhị phân (nghĩa là giá trị của nút gốc), bạn có thể dễ dàng phân hủy toàn bộ kết xuất vào giá trị nút gốc, các giá trị của các nút con trái và các giá trị của các nút của cây con phải.

Để xuất cây theo thứ tự sau, đệ quy và sắp xếp lại được áp dụng. Nhiệm vụ này được để lại cho người đọc.

Answer 3

Dựa trên câu trả lời của Ondrej Tucny. Áp dụng cho BST chỉ
dụ:

 20 
    /\ 
    10 30 
    /\ \ 
    6 15 35 

Preorder = 20 10 6 15 30 35
bài viết = 6 15 10 35 30 20

Đối với một BST, Trong Preorder traversal; phần tử đầu tiên của mảng là 20. Đây là gốc của cây của chúng ta. Tất cả các số trong mảng có ít hơn 20 hình thành subtree trái của nó và số lượng lớn hơn tạo thành subtree quyền.

//N = number of nodes in BST (size of traversal array) 
int post[N] = {0}; 
int i =0; 

void PretoPost(int pre[],int l,int r){ 
    if(l==r){post[i++] = pre[l]; return;} 
    //pre[l] is root 
    //Divide array in lesser numbers and greater numbers and then call this function on them recursively 
    for(int j=l+1;j<=r;j++) 
     if(pre[j]>pre[l]) 
      break; 
    PretoPost(a,l+1,j-1); // add left node 
    PretoPost(a,j,r); //add right node 
    //root should go in the end 
    post[i++] = pre[l]; 
    return; 
} 

Vui lòng sửa tôi nếu có lỗi.

Answer 4

bạn được cung cấp kết quả truyền tải đơn đặt hàng trước. sau đó đặt các giá trị vào một cây tìm kiếm nhị phân phù hợp và chỉ cần thực hiện theo thuật toán tra cứu thứ tự sau cho BST thu được.

Answer 5

Tôi biết điều này là cũ nhưng có giải pháp tốt hơn.

Chúng tôi không phải tạo lại BST để nhận đơn đặt hàng sau từ đơn đặt hàng trước.

Đây là một mã đơn giản python mà hiện nó một cách đệ quy:

import itertools 

def postorder(preorder): 
    if not preorder: 
     return [] 
    else: 
     root = preorder[0] 
     left = list(itertools.takewhile(lambda x: x < root, preorder[1:])) 
     right = preorder[len(left) + 1:] 
     return postorder(left) + postorder(right) + [root] 

if __name__ == '__main__': 
    preorder = [20, 10, 6, 15, 30, 35] 
    print(postorder(preorder)) 

Output:

[6, 15, 10, 35, 30, 20] 

Giải thích:

Chúng ta biết rằng chúng ta đang ở pre-order . Điều này có nghĩa là gốc nằm ở chỉ mục 0 của danh sách các giá trị trong BST. Và chúng ta biết rằng các yếu tố sau gốc là:

• đầu tiên: các yếu tố ít hơn root, thuộc cây con trái của gốc
• thứ hai: các yếu tố lớn hơn root, thuộc cây con bên phải của thư mục gốc

Sau đó, chúng tôi chỉ gọi đệ quy hàm trên cả hai nhánh (thứ tự vẫn được đặt trước) và sau đó là chuỗi left + right + root (đây là thứ tự sau).

Answer 6

Nếu bạn đã được đặt hàng trước và bạn muốn chuyển đổi nó thành đặt hàng trước. Sau đó, bạn nên nhớ rằng trong một BST để luôn luôn cung cấp cho các con số theo thứ tự tăng dần. Do đó bạn có cả Inorder cũng như preorder để xây dựng một cây.

preorder: 6, 2, 1, 4, 3, 7, 10, 9, 11

inorder: 1, 2, 3, 4, 6, 7, 9, 10, 11

Và postorder của nó: 1 3 4 2 9 11 10 7 6

Answer 7

đây đặt hàng trước traversal của một cây tìm kiếm nhị phân được đưa ra trong mảng. Vì vậy, yếu tố thứ nhất của mảng đặt hàng trước sẽ gốc của BST.Chúng tôi sẽ tìm thấy phần bên trái của BST và phần bên phải của BST. Tất cả các phần tử trong mảng đặt trước sẽ nhỏ hơn gốc sẽ là nút trái và Tất cả các phần tử trong mảng đặt hàng trước lớn hơn thì gốc sẽ là nút phải.

#include <bits/stdc++.h> 
using namespace std; 
int arr[1002]; 
int no_ans = 0; 
int n = 1000; 
int ans[1002] ; 
int k = 0; 

int find_ind(int l,int r,int x){ 
    int index = -1; 
    for(int i = l;i<=r;i++){ 
     if(x<arr[i]){ 
      index = i; 
      break; 
     } 
    } 
    if(index == -1)return index; 
    for(int i =l+1;i<index;i++){ 
     if(arr[i] > x){ 
      no_ans = 1; 
      return index; 
     } 
    } 
    for(int i = index;i<=r;i++){ 
     if(arr[i]<x){ 
      no_ans = 1; 
      return index; 
     } 
    } 
    return index; 

} 

void postorder(int l ,int r){ 

    if(l < 0 || r >= n || l >r) return; 
    ans[k++] = arr[l]; 
    if(l==r) return; 
    int index = find_ind(l+1,r,arr[l]); 
    if(no_ans){ 
     return; 
    } 
    if(index!=-1){ 
     postorder(index,r); 
     postorder(l+1,index-1); 
    } 
    else{ 
     postorder(l+1,r); 
    } 
} 

int main(void){ 

    int t; 
    scanf("%d",&t); 
    while(t--){ 
     no_ans = 0; 
     int n ; 
     scanf("%d",&n); 

     for(int i = 0;i<n;i++){ 
      cin>>arr[i]; 
     } 
     postorder(0,n-1); 
     if(no_ans){ 
      cout<<"NO"<<endl; 
     } 
     else{ 

      for(int i =n-1;i>=0;i--){ 
       cout<<ans[i]<<" "; 
      } 
      cout<<endl; 
     } 
    } 

    return 0; 
} 

Answer 8

Như chúng ta biết preOrder theo chuỗi gốc, trái, phải.

Để xây dựng cây chúng ta cần phải làm theo vài steps- cơ bản:

câu hỏi của bạn bao gồm loạt 6, 2,1,4,3,7,10,9,11

points- :

1. số đầu tiên của phim sẽ là root (mẹ) tức là 6

2. Tìm số đó là lớn hơn 6 như vậy trong loạt bài này 7 là lần đầu tiên số lượng lớn trong serie này s như vậy nút bên phải sẽ được bắt đầu từ đây và để lại cho số này (7) là subtrees trái của bạn.

     6 
        / \ 
        2  7 
       /\  \ 
       1 4  10 
        / /\ 
        3  9 11 

3.same cách làm theo các quy tắc cơ bản của BST tức trái, rễ, phải

hàng loạt các bài theo thứ tự sẽ là L, R, N tức là 1,3,4,2,9, 11,10,7,6