- vừa được xem lúc

[DSA] Trees Traversal

0 0 3

Người đăng: Tri Lương

Theo Viblo Asia

Giới thiệu

Trees Traversal (duyệt cây) là cách để lấy tất cả các node của cây. Không như các kiểu dữ liệu linear như linked list, array, queue, stack chỉ lấy dữ liệu theo một chiều, trees có thể lấy tất cả các node theo nhiều cách khác nhau.

Có 2 cách duyệt cây:

  • Depth First traversal (DFS)
    • Preorder traversal
    • Inorder traversal
    • Postorder traversal
  • Breadth First traversal (BFS)

image.png

Tiếp tục các đoạn code trong phần [DSA] Binary Search Trees ta tiến hành các cách duyệt cây nhị phân (Trees traversal)

Bread first traversal (BFS)

image.png

 BFS() { let data = []; let queue = []; let node = this.root; queue.push(node); while (queue.length) { node = queue.shift(); data.push(node.value); if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } return data; }

Depth first traversal

Preorder

image.png

 DFSPreOrder() { var data = []; function traversal(node) { data.push(node.value); if (node.left) { traversal(node.left); } if (node.right) { traversal(node.right); } } traversal(this.root); return data; }

Postorder

image.png

 DFSPostOrder() { var data = []; function traversal(node) { if (node.left) { traversal(node.left); } if (node.right) { traversal(node.right); } data.push(node.value); } traversal(this.root); return data; }

Inorder

image.png

 DFSInOrder() { var data = []; function traversal(node) { if (node.left) { traversal(node.left); } data.push(node.value); if (node.right) { traversal(node.right); } } traversal(this.root); return data; }

Bình luận

Bài viết tương tự

- vừa được xem lúc

Nhập môn lý thuyết cơ sở dữ liệu - Phần 1 : Tổng quan

# Trong bài viết này mình sẽ tập trung vào chủ đề tổng quan về Cơ sở dữ liệu. Phần 1 lý thuyết nên hơi chán các bạn cố gắng đọc nhé, chắc lý thuyết mới làm bài tập được, kiến thức còn nhiều các bạn cứ

0 0 112

- vừa được xem lúc

Cấu trúc dữ liệu và giải thuật: Danh sách liên kết đơn (Singly Linked List)

Danh sách liên kết là 1 cấu trúc dữ liệu được sử dụng để lưu trữ 1 tập hợp các dữ liệu. Danh sách liên kết có các tính chất sau:.

0 0 54

- vừa được xem lúc

Bạn đang lưu dữ liệu dạng cây vào CSDL theo cách nào?

Dữ liệu dạng cây (tree data structure) là dạng dữ liệu rất thường thấy ở các ứng dụng. Những chỗ bạn từng bắt gặp có dùng cấu trúc dạng cây có thể là:.

0 0 82

- vừa được xem lúc

Sự khác nhau giữa biến tham chiếu kiểu List và ArrayList trong Java là gì?

1. Đặt vấn đề.

0 0 47

- vừa được xem lúc

8 kiểu cấu trúc dữ liệu mà mọi lập trình viên cần phải biết.

Trong lĩnh vực Khoa học máy tính, cấu trúc dữ liệu được định nghĩa là những cách để tổ chức và lưu trữ dữ liệu trong máy tính để chúng ta có thể thực hiện các hoạt động trên dữ liệu được lưu trữ đó mộ

0 0 32

- vừa được xem lúc

Data structures: Arrays

Tổng quan:. Tiếp theo trong series Data structures and Algorithms, hôm nay mình sẽ giới thiệu đến các bạn một loại Cấu trúc dữ liệu đơn giản và hay gặp nhất, đó là Array.

0 0 47