Xây dựng Cây từ các đường truyền Inorder đã cho và Đặt hàng trước trong C ++

Chúng tôi được cung cấp các trình duyệt Inorder và Preorder của một cây nhị phân. Mục đích là tạo một cây từ các đường truyền đã cho.

Inorder traversal - Trong kiểu duyệt cây này, cây con bên trái được truy cập đầu tiên, sau đó là nút và cuối cùng là cây con bên phải.

Inorder (rễ cây)

Đặt hàng trước truyền tải - Trong kiểu duyệt cây này, nút được truy cập đầu tiên, sau đó là cây con bên trái và cuối cùng là cây con bên phải.

Đặt hàng trước (gốc cây)

Đường đi ngang qua inorder và đặt hàng trước của cây bên dưới được đưa ra -

Xây dựng Cây từ các đường truyền Inorder đã cho và Đặt hàng trước trong C ++

Inorder

2-3-4-5-6-8-10

4-3-2-5-8-6-10

Bây giờ chúng ta sẽ xây dựng lại cây ở trên cho các lần đặt hàng trước và các đường đi ngang qua đặt hàng trước.

2-3-4-5-6-8-10

5-3-2-4-8-6-10

Như chúng ta biết rằng việc đặt hàng trước sẽ truy cập vào nút gốc đầu tiên sau đó giá trị đầu tiên luôn đại diện cho gốc của cây. Từ dãy 5 trên là gốc của cây.

5 -3-2-4-8-6-10

Từ tính năng duyệt inorder ở trên, chúng ta biết rằng cây con bên trái của một nút được duyệt trước khi nó được theo sau bởi cây con bên phải của nó. Do đó, tất cả các giá trị ở bên trái của 5 trong inorder thuộc về cây con bên trái của nó và tất cả các giá trị ở bên phải thuộc về cây con bên phải của nó.

2-3-4 ← 5 → 6-8-10

Xây dựng Cây từ các đường truyền Inorder đã cho và Đặt hàng trước trong C ++

Đặt hàng trước truyền đi của cây con bên trái là 3 -2-4. Vì vậy, 3 trở thành gốc.

Đường ngang Inorder được chia nhỏ hơn thành 2 ← 3 → 4

Xây dựng Cây từ các đường truyền Inorder đã cho và Đặt hàng trước trong C ++

Đặt hàng trước truyền của cây con bên phải là 8 -6-10. Vì vậy, 8 trở thành gốc.

Đường ngang Inorder được chia nhỏ hơn thành 6 ← 8 → 10

Xây dựng Cây từ các đường truyền Inorder đã cho và Đặt hàng trước trong C ++

Vì vậy, theo cách này, chúng tôi đã xây dựng cây ban đầu từ các đường truyền đặt hàng trước và đặt hàng trước.