Làm cách nào để in tất cả các nút lá của cây nhị phân từ trái sang phải trong JavaScript?

Sự thể hiện trực quan của các khái niệm được thảo luận được thể hiện trong hình dưới đây:

Hướng dẫn này giải thích quy trình in tất cả các nút lá của cây nhị phân bằng cách bao gồm các phần được đề cập bên dưới:

• Làm thế nào để xác định các nút lá?
• Làm cách nào để in tất cả các nút lá của cây nhị phân từ trái sang phải trong JavaScript?
• Mẹo bổ sung: In các nút lá của cây nhị phân từ hướng phải sang trái
• Phần kết luận

Làm thế nào để xác định các nút lá?

Các ' lá cây nút ” là những nút không có nút con hoặc cụ thể là có nút “ chiều cao ' của ' 0 ”. Nếu nút có “ chiều cao ' lớn hơn ' 0 ” thì nút đó có thể là nút bên trong hoặc nút gốc. Các ' lá cây ” các nút thường được quay lại để xác định nguồn ban đầu nơi nút này được tạo ra. Nó chủ yếu được sử dụng trong các thuật toán tìm kiếm hoặc tìm lỗi để tìm ra nguyên nhân gây ra lỗi hoặc sự cố.

Làm cách nào để in tất cả các nút lá của cây nhị phân từ trái sang phải trong JavaScript?

Có hai cách tiếp cận “ đệ quy ' Và ' lặp đi lặp lại ” để chọn tất cả các nút lá có sẵn trong cây nhị phân được cung cấp ở vị trí mong muốn “ bên trái ' ĐẾN ' Phải ' phương hướng. Việc triển khai thực tế các phương pháp này được thể hiện trong các phần được nêu dưới đây:

• In đệ quy tất cả các nút lá của cây nhị phân từ trái sang phải
• In tất cả các nút lá của cây nhị phân bằng phương pháp lặp

Cách 1: In đệ quy tất cả các nút lá của cây nhị phân từ trái sang phải

Cách tiếp cận đệ quy chọn tất cả các nút trong một thuật toán tìm kiếm theo chiều sâu cách đầu tiên đi qua toàn bộ các nút bên trái, sau đó là nút giữa và các nút bên phải cuối cùng. Hoạt động này được thực hiện đệ quy cho mọi nút và khi không còn duyệt qua “ lá cây ” các nút được xác định. Để hiểu rõ hơn về khái niệm này, hãy truy cập đoạn mã dưới đây:

Giải thích về khối mã trên được nêu dưới đây:

• Đầu tiên, tạo một lớp có tên “ nút ”, tạo ra một nút mới và đặt giá trị của nó thành “ 0 ”. Đính kèm “ bên trái ' Và ' Phải ” các nút bên được đặt thành “ vô giá trị ” theo mặc định bằng cách sử dụng hàm tạo của lớp.
• Tiếp theo, xác định một “ displayLeafNodes() ” hàm chấp nhận một tham số duy nhất của “ Nút gốc ”. Giá trị tham số này được coi là nút hiện được chọn của cây nhị phân.
• Bên trong hàm, “ nếu như Câu lệnh ” được sử dụng để kiểm tra xem “ Nút gốc ” có rỗng hay không. Trong trường hợp ' vô giá trị ” quá trình thực thi tiếp theo đã dừng lại đối với nút đó. Trong trường hợp khác, rootNode “ bên trái ' Và ' Phải ” các nút bên được kiểm tra “ vô giá trị ”. Nếu cả hai đều là null thì giá trị của “ nút ” được in.
• Nếu “ bên trái ' hoặc ' Phải nút ” không phải là “null”, sau đó chuyển phía đó của nút cho “ displayLeafNodes() ” cho phép toán đệ quy.
• Xác định một hàm mới có tên là “ provNode() ” chấp nhận tham số duy nhất của “ giá trị ”. Bên trong hàm tạo một phiên bản mới của “ Nút ” lớp có tên “ nút tạm thời ”. Gán tham số “ giá trị ” làm giá trị cho thuộc tính lớp “ nội dung ” và đặt “ bên trái ' Và ' Phải ” nút bên tới “ vô giá trị ” theo mặc định.
• Cuối cùng, tạo một đối tượng có tên “ Nút gốc ' cho ' provNode() ” và truyền giá trị nút làm tham số hàm này. Tạo các nút bên trái và bên phải bằng cách thêm “ bên trái ' Và ' Phải ” từ khóa có “rootNode” và gán giá trị cho chúng bằng cùng một hàm “ provNode() ”.
• Các ' bên trái ” nghĩa là vị trí bên trái của nút gốc và “ trái.trái ” vị trí có nghĩa là bên trái của bên trái, cách tiếp cận tương tự được áp dụng trong trường hợp “ Phải ' Và ' Phải ”
• Sau khi xác định cây, chuyển “rootNode” làm đối số cho “ displayLeadNodes() ” để chọn và in tất cả các nút lá của cây đã tạo.

Đầu ra được tạo sau khi biên dịch xác nhận rằng nút lá của cây được cung cấp đã được truy xuất và in trên bảng điều khiển:

Phương pháp 2: In tất cả các nút lá của cây nhị phân bằng phương pháp lặp

Các ' lặp đi lặp lại ” là cách tiếp cận hiệu quả nhất, nó sử dụng khái niệm “ xô ' Và ' nhạc pop ” để chọn “ lá cây ' điểm giao. Những điểm chính hoặc hoạt động của phương pháp này được nêu dưới đây:

Giải thích về đoạn mã trên được viết dưới đây:

• Đầu tiên, tạo một “ Nút ” lớp nhận một tham số duy nhất “ giá trị ” được đặt làm giá trị của nút mới được tạo và bên trái và bên phải được đặt thành null. Giống như thực hiện trong ví dụ trên.
• Tiếp theo, tạo một hàm “ displayLeafNodes() ” chấp nhận một tham số duy nhất là “ Nút gốc ”. “rootNode” này được coi là cây nhị phân và tính trống của nó được kiểm tra trước tiên.
• Nếu nút không trống thì danh sách trống có tên “ danh sách ” được tạo ra và “ Nút gốc ” tham số được chèn vào nó bằng cách sử dụng “ xô() ' phương pháp.
• Sau đó, “ trong khi() ” được sử dụng để thực thi cho đến hết độ dài của “ danh sách ”. Bên trong vòng lặp, phần tử nằm ở dưới cùng của cây hoặc “ danh sách ” được xóa bằng cách sử dụng “ nhạc pop() ' phương pháp.
• Hiện nay, sự tồn tại của “ bên trái ' Và ' Phải ” các bên của “rootNode” được kiểm tra và nếu cả hai bên không tồn tại thì có nghĩa là nó không có nút con. Sau đó, nút này sẽ được hiển thị trên màn hình và được xác định là nút lá.
• Nếu có một nút ở bên trái hoặc bên phải nghĩa là nó có nút con. Sau đó ' bên trái ' Và ' Phải ” nút được đẩy vào “ danh sách ” để biết thêm thao tác tìm nút lá.
• Cuối cùng, tạo cây nhị phân tùy chỉnh bằng cách chuyển các giá trị nút làm tham số cho “ Nút ” hàm tạo lớp. Sau khi tạo, chuyển cây “rootNode” làm đối số cho “ displayLeafNodes() ' chức năng.

Đầu ra được tạo sau khi biên dịch cho thấy các nút lá của cây được cung cấp đã được in:

Mẹo bổ sung: In các nút lá của cây nhị phân từ hướng phải sang trái

Để truy xuất tất cả các nút lá không có nút con trong “ Phải ' ĐẾN ' bên trái ” hướng, cách tiếp cận đệ quy được khuyên dùng nhiều nhất do tính dễ dàng của nó. Ví dụ: cùng một cây được thảo luận trong các phần trên sẽ được sử dụng để truy xuất nút lá nhưng trong phần “ Phải ” đến “ bên trái ” hướng, như hình dưới đây:

Đoạn mã nêu trên hoạt động như thế này:

• Đầu tiên là lớp “ Nút ” được tạo bằng cách sử dụng hàm tạo mặc định để thêm một nút mới vào cây giống như liên kết được thực hiện trong các ví dụ trên.
• Tiếp theo, “ displayLeadNodes() ” được tạo để chấp nhận một tham số duy nhất là “ Nút gốc ”. Tham số này được kiểm tra cho “ vô giá trị ” điều kiện thông qua “ nếu như ' tuyên bố.
• Nếu nút được cung cấp không đúng thì “ bên trái ' Và ' Phải ” các nút bên được kiểm tra “ vô giá trị ' tình trạng. Nếu cả hai đều rỗng thì nút đó sẽ được xác định là “ lá cây ” nút và được in trên trang web.
• Sau đó, vượt qua “ Phải ' Và ' bên trái “ nút của “ Nút gốc ” đến “ displayLeafNodes() ' chức năng.
• Phân bổ vị trí của mỗi nút bằng cách tạo các phiên bản bằng cách sử dụng “ mới ” từ khóa và “ Nút() ” constructor và chỉ định vị trí làm tham số của hàm tạo.
• Các ' bên trái ” nghĩa là vị trí bên trái của nút gốc và “ left.left ”vị trí có nghĩa là trái hoặc trái. Cách tiếp cận tương tự cũng được áp dụng trong trường hợp “ Phải ' Và ' Phải ”.
• Cuối cùng, vượt qua “ Nút gốc ” như một lập luận cho “ displayLeafNode() ' chức năng.

Đầu ra được tạo ra cho thấy các nút lá được in theo hướng từ phải sang trái.

Đó là tất cả về việc in tất cả các nút lá của cây nhị phân theo bất kỳ hướng mong muốn nào.

Phần kết luận

Để in tất cả các nút lá của cây nhị phân, hãy tạo một lớp ngẫu nhiên để tạo và gán giá trị cho các nút cây. Tiếp theo, tạo một hàm ngẫu nhiên chấp nhận một nút duy nhất của cây theo hệ thống phân cấp từ trên xuống dưới. Hàm này chứa nhiều “ nếu như ” điều kiện kiểm tra xem “ nút ” không trống và không có nút nào trong “ bên trái ' Và ' Phải ” hướng thì nút đó được coi là “ lá cây ” nút và được hiển thị trên bảng điều khiển. Hướng dẫn này đã giải thích quy trình in tất cả các nút lá của cây nhị phân từ trái sang phải hoặc phải sang trái.