Duyệt cây là quá trình đi qua tất cả nút trong cây. Từ gốc (root) là nút đầu tiên đến tất cả các nút được liên kết. Có 3 cách duyệt cây:
1. Duyệt trung thứ tự:
Thuật toán:
Bước 1: Duyệt cây con bên trái, gọi InOrder(root.left)
Bước 2: Duyệt root
Bước 3: Duyệt cây con bên phải, gọi InOrder(root.right)
Code Java:
javaCopy
// Print inorder traversal of given tree.
void printInorderTraversal(Node root)
{
if (root == null)
return;
//first traverse to the left subtree
printInorderTraversal(root.left);
//then print the data of node
System.out.print(root.data + " ");
//then traverse to the right subtree
printInorderTraversal(root.right);
}
Dùng: cho tìm kiếm kiếm cây nhị phân.
2. Duyệt tiền thứ tự:
Thuật toán:
Bước 1: Duyệt root
Bước 2: Duyệt cây con bên trái, gọi InOrder(root.left)
Bước 3: Duyệt cây con bên phải, gọi InOrder(root.right)
Code Java:
javaCopy
// Print preorder traversal of given tree.
void printPreorderTraversal(Node root)
{
if (root == null)
return;
//first print the data of node
System.out.print(root.data + " ");
//then traverse to the left subtree
printPreorderTraver...
