Hello phần lớn người, vào series này mình đang tổng vừa lòng lại một số cấu trúc dữ liệu với giải thuật thịnh hành trong Javascript và phân chia sẽ đến những bạn.
Bạn đang xem: Cấu trúc dữ liệu và giải thuật javascript
Bài viết này nhằm mục đích bắt đầu cho một số trong những bạn chuẩn bị phỏng vấn xin vấn đề về cấu trúc dữ liệu cùng giải thuật.
Xem thêm: Cá Dứa Có Phải Là Cá Bông Lau, 【 Cách Phân Biệt Khô Thật Giả】
Cụ thể, trong bài viết này bản thân sẽ giới thiệu 3 cấu trúc dữ liệu với giải thuật:
StackQueueBinary search tree1. Stack
Stack là một cấu tạo dữ liệu đường tính tuân theo nguyên tắc LIFO (Last In First Out) hoặc FIFO (First In Last Out). Gồm 2 phép tính chính trong stack.
Push - Thêm một trong những phần tử lên đầu stackPop - rước ra một phần tử được thêm sớm nhất ( bộ phận đầu stack)
Chúng ta hãy xem code kiểm tra dưới đây
class Node contructor(value) this.value = value; this.prev = null; class Stack contructor() this.top = null; push(value) let node = new Node(value); node.prev = this.top; this.top = node; pop() if (this.top) let value = this.top.value; this.top = this.top.prev; else return "Stack is empty" let stack1 = new Stack();stack1.push(1);stack1.push(2);stack1.push(3);console.log(stack1.pop()); // 3console.log(stack1.pop()); // 2console.log(stack1.pop()); // 1console.log(stack1.pop()); // stack is empty
2. Queue
Queue cũng là kết cấu dữ liệu tuyến tính. Queue tuân theo nguyên tắc FIFO. Có 2 phép tính thiết yếu trong Queue:Enqueue - Thêm một trong những phần tử vào thời gian cuối QueueDequeue - Xoá 1 phần tử từ đầu Queue
class Node constructor(val) this.value = val; this.next = null; class Queue constructor() this.head = null; this.tail = null; enqueue(val) // lớn tail let node = new Node(val); if (!this.head) //if queue is empty, point head và tail to lớn this new node this.head = this.tail = node; else this.tail.next = node; this.tail = node; // make new node as tail dequeue() // from head if (this.head) let val = this.head.value; this.head = this.head.next; return val; else return "Queue is empty"; let q1 = new Queue();q1.enqueue(1);q1.enqueue(2);q1.enqueue(3);console.log(q1.dequeue()); // 1console.log(q1.dequeue()); // 2console.log(q1.dequeue()); // 3console.log(q1.dequeue()); // Queue is empty
3. Binary tìm kiếm Tree
Binary search tree là 1 trong cây kiếm tìm kiếm nhị phân bao gồm thứ từ hoặc được sắp đến xếp.Có root nodeMỗi node (bao có root node) sẽ có một khoá lớn lớn hơn tất cả các khoá của cây nhỏ bên trái của node và nhỏ dại các khoá vào cây nhỏ bên đề nghị node
Chèn phần tử
Đầu tiên, khoá của node bắt đầu được đối chiếu với root node (node gốc)Nếu khoá của node mới nhỏ hơn root node thì node new sẽ được đối chiếu với khoá của node con bên trái root nodeNếu khoá của node mới to hơn khoá của root node thì node bắt đầu sẽ được so sánh với khoá của node bên nên root nodeTiến trình này sẽ tiến hành lặp cho tới khi node mơi được đối chiếu với node lá và nó được cung ứng bên đề nghị hoặc bên trái node con, tuỳ thuộc vào khoá của nó. Nếu như khoá của nó nhỏ dại hơn khoá của node lá thì nó sẽ được chèn vào làm node bé bên trái của node lá, trái lại sẽ là bên nên của node láDuyệt phần tử
Có 3 cách duyệt một cây nhị phân phổ biến nhất
Pre-order (Node ->Left->Right)In-order(Left->Node->Right)Post-order(Left->Right->Node)Việc phê chuẩn theo thứ tự của cây nhị phân sẽ luôn luôn dẫn mang lại danh sách những node sẽ được sắp xếp tăng dần. Ở đây, mình sẽ xúc tiến duyệt theo lắp thêm tự:Duyệt cây con bên trái bằng phương pháp gọi hàm đệ quy printNodeIn ra khoá node hiện nay tạiDuyệt cây bé bên phải bằng cách gọi hàm đệ quy printNodeclass Node constructor(val) this.value = val; this.left = null; this.right = null; class BinarySearchTree { constructor() this.root = null; // root node insertNode(parentNode, newNode) { if (newNode.value trên đây, là phân tách sẽ của chính bản thân mình về 3 cấu tạo dữ liệu và lời giải trong Javascript, hi vọng bài viết sau mình đã tổng thích hợp được một số cấu trúc, giải thuật khác để rất có thể share đến những bạn, cảm ơn mọi tín đồ đã theo dõi nội dung bài viết :v
