Bài viết trước mình đã giới thiệu cơ bản về đánh giá thuật toán với Big-O, cài đặt cấu trúc dữ liệu Linked list, bài viết này mình sẽ tiếp tục với cấu trúc dữ liệu dạng cây (tree).

Nội dung:
+ Giới thiệu về cấu trúc dữ liệu dạng cây
+ Phân loại
+ Cài đặt và thao tác

Giới thiệu cấu trúc cây
Nhìn chung một cấu trúc dữ liệu dạng cây được kết hợp từ nhiều nodes với nhiều nodes con. Node đầu tiên/ trên cùng được gọi là node gốc (root node) trong bài viết này chúng ta sẽ khám phá nhiều kiểu về cây khác nhau như là cây nhị phân, cây tìm kiếm nhị phân, cây tìm kiếm nhị phân tự cân bằng (self-balancing binary)…cây sẽ có dạng cơ bản:

Khối mã để triển khai một node tree như sau:
function TreeNode(value) {
this.value = value;
this.children = [];
}
Cây nhị phân (binary tree):
cây nhị phân là kiểu cây mà chỉ có hai node con trái và phải.

Cài đặt node cây nhị phân:
function BinaryTreeNode (value){
this.value = value;
this.left = null;
this.right = null;
}
Một cây nhị phân luôn luôn có một node gốc, được khỏi tạo là null trước khi bất kì phần tử nào được chèn vào cây.
function BinaryTree () {
this._root = null;
}
Duyệt cây:
Duyệt qua một mảng là đơn giản: truy cập node cây sử dụng chỉ số và tăng chỉ số cho đến khi chỉ số chạm tới kích thước giới hạn. Với cây,con trỏ trái và con trỏ phải , phải tuân theo thứ tự của mỗi phần tử trong cây. Có nhiều cách để làm việc này, các kĩ thuật duyệt phổ biến nhất là duyệt theo thứ tự trước, duyệt theo thứ tự sau, duyệt bên trong và duyệt theo thứ tự cấp độ của node (duyệt những node ngang hàng nhau trước.)
Duyệt theo thứ tự trước hay duyệt hàng trước ( Pre-order Traversal ):
Duyệt hàng trước duyệt qua các node theo thứ tự sau: root (node hiện tại), trái, phải. Trong hình bên dưới bạn nhìn thấy rằng 42 là root node nên nó được duyệt trước, khi đó tiếp tục qua bên trái, khi đó node trái (41) của node gốc được cân nhắc là root node, root node mới (41) được in, khi đó tiếp tục duyệt node bên trái của node này là 10, nên 10 sẽ được set là node gốc mới, nhưng sẽ không thể tiếp tục vì không có node con, khi đó 40 được duyệt bởi vì là node bên phải của node 41, việc xử lý như vậy tiếp tục và toàn bộ thứ tự các node trong cây được duyệt:

với đệ quy việc cài đặt là dễ dàng, trường hợp base để chấm dứt đệ quy khi node là null. Ngược lại nó sẽ in ra giá trị node và khi đó gọi hàm đệ quy bên con trái và khi đó con phải của nó:
BinaryTree.prototype.traversePreOrder = function() {
traversePreOrderHelper(this._root);

function traversePreOrderHelper(node) {
if (!node) return;
console.log(node.value);
traversePreOrderHelper(node.left);
traversePreOrderHelper(node.right);
}
}
Điều này cũng có thể được hoàn thành với việc duyệt, nhưng khó hơn để cài đặt:
BinaryTree.prototype.traversePreOrderIterative = function() {
//create an empty stack and push root to it
var nodeStack = [];
nodeStack.push(this._root);

// Pop all items one by one. Do following for every popped item
// a) print it
// b) push its right child
// c) push its left child
// Note that right child is pushed first so that left is processed first
while (nodeStack.length) {
//# Pop the top item from stack and print it
var node = nodeStack.pop();
console.log(node.value);

//# Push right and left children of the popped node to stack
if (node.right) nodeStack.push(node.right);
if (node.left) nodeStack.push(node.left);
}
}
đây là kết quả:: [42, 41, 10, 40, 50, 45, 75]
Duyệt theo thứ tự trong ( In-Order Traversal ):
Duyệt các node theo thứ tự sau: trái, gốc (current node), phải.
Thứ thự duyệt:

Duyệt trong cũng được cài đặt dễ dàng với đệ quy. Trường hợp chấm dứt đệ quy là khi node là null. Trong trường hợp không phải cơ bản, gọi hàm đệ quy bên con trái, in node gốc, và khi đó gọi đệ quy bên con phải.

BinaryTree.prototype.traverseInOrder = function() {
traverseInOrderHelper(this._root);

function traverseInOrderHelper(node) {
if (!node) return;

traverseInOrderHelper(node.left);
console.log(node.value);
traverseInOrderHelper (node.right);
}
}

BinaryTree.prototype.traverseInOrderIterative = function() {
var current = this._root,
s = [],
done = false;

while (!done) {
// Reach the left most Node of the current Node
if (current != null) {
// Place pointer to a tree node on the stack
// before traversing the node's left subtree
s.push(current);
s.push(current);
current = current.left;
} else {
if (s. length) {
current = s.pop();
console.log(current.value);
current = current.right;
} else {
done = true;
}
}
}
}
Kết quả của quá trình duyệt: [10, 41, 40, 42, 45, 50, 75].
Duyệt thứ tự trước (Post-order Traversal ):
duyệt thứ tự trước duyệt các node theo thứ tự sau: trái, phải, gốc.
Thứ tự duyệt:

BinaryTree.prototype.traversePostOrder = function() {
traversePostOrderHelper(this._root);

function traversePostOrderHelper(node) {
if (node.left) traversePostOrderHelper(node.left);
if (node.right) traversePostOrderHelper(node.right);
console.log(node.value);
}
}

BinaryTree.prototype.traversePostOrderIterative = function() {
// Create two stacks
var s1 = [], s2 = [];

// Push root to first stack
s1.push(this._root);

//# Run while first stack is not empty
while (s1.length) {
// Pop an item from s1 and append it to s2
var node = s1.pop();
s2.push(node);

// Push left and right children of removed item to s1
if (node.left) s1.push(node.left);
if (node.right) s1.push(node.right);
}
// Print all elements of second stack
while (s2.length) {
var node = s2.pop();
console.log(node.value);
}
}
kết quả in: [10, 40, 41, 45, 75, 50, 42].
Duyệt theo cấp của node ( Level-Order Traversal ):
kiểu duyệt này hay còn được biết đến như duyệt theo bề ngang của cây ( breadth first search (BFS) ):