Cấu trúc dữ liệu Tree
Tree là tập hợp nút kết nối bởi các cạnh. Mỗi nút chứa dữ liệu và tham chiếu đến các nút con.
Cây nhị phân tìm kiếm (BST)
BST là cây nhị phân mà nút giá trị nhỏ hơn lưu bên trái, giá trị lớn hơn lưu bên phải.
Ví dụ BST hợp lệ:
25 / \ 20 36 / \ / \ 10 22 30 40
Triển khai BST trong JavaScript.
Bước 1: Lớp Node
Lớp này đại diện cho một nút đơn lẻ trong BST. BST là tập hợp các nút lưu dữ liệu và tham chiếu con theo quy tắc trên.
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; };
Tạo instance Node mới:
const newNode = new Node(23);
Tạo nút với data=23, left/right=null.
Bước 2: Lớp Binary Search Tree:
class BinarySearchTree{ constructor(){ this.root = null; }; };
Tạo lớp BST, dùng new để tạo instance cây.
Bây giờ triển khai chèn nút vào đúng vị trí theo quy tắc BST.
Bước 3: Chèn nút vào BST
class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,newNode); }; }; }; };
Ví dụ
Toàn bộ code BST:
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,newNode); }; }; }; }; const BST = new BinarySearchTree(); BST.insert(1); BST.insert(3); BST.insert(2);