Chương trình C++ thực hiện duyệt tiền tự (preorder) đệ quy của cây nhị phân

Duyệt cây (tree traversal) là một dạng duyệt đồ thị, liên quan đến việc kiểm tra hoặc in mỗi nút trong cây đúng một lần. Duyệt tiền tự (preorder) của cây tìm kiếm nhị phân thăm các nút theo thứ tự: (Gốc, Trái, Phải).

Ví dụ về duyệt tiền tự của một cây nhị phân:

Cho cây nhị phân như sau:

Duyệt tiền tự (Preorder): 6 4 1 5 8

Chương trình thực hiện duyệt tiền tự đệ quy:

Ví dụ

#include <iostream>
using namespace std;

struct node {
  int data;
  struct node *left;
  struct node *right;
};

struct node *createNode(int val) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->data = val;
  temp->left = temp->right = NULL;
  return temp;
}

void preorder(struct node *root) {
  if (root != NULL) {
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

struct node* insertNode(struct node* node, int val) {
  if (node == NULL) return createNode(val);
  if (val < node->data)
    node->left = insertNode(node->left, val);
  else if (val > node->data)
    node->right = insertNode(node->right, val);
  return node;
}

int main() {
  struct node *root = NULL;
  root = insertNode(root, 4);
  insertNode(root, 5);
  insertNode(root, 2);
  insertNode(root, 9);
  insertNode(root, 1);
  insertNode(root, 3);
  cout << "Duyệt tiền tự của cây tìm kiếm nhị phân: ";
  preorder(root);
  return 0;
}

Kết quả đầu ra

Duyệt tiền tự của cây tìm kiếm nhị phân: 4 2 1 3 5 9

Trong chương trình trên, cấu trúc node tạo nút của cây. Đây là cấu trúc tự tham chiếu vì chứa con trỏ kiểu struct node:

struct node {
  int data;
  struct node *left;
  struct node *right;
};

Hàm createNode() tạo nút temp và cấp phát bộ nhớ bằng malloc. Giá trị val lưu vào data của temp. NULL gán cho con trỏ left và right:

struct node *createNode(int val) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->data = val;
  temp->left = temp->right = NULL;
  return temp;
}

Hàm preorder() nhận gốc của cây nhị phân và in các phần tử theo tiền tự. Đây là hàm đệ quy:

void preorder(struct node *root) {
  if (root != NULL) {
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

Hàm insertNode() chèn giá trị vào cây nhị phân tại vị trí đúng. Nếu nút là NULL, gọi createNode. Ngược lại, tìm vị trí phù hợp trong cây:

struct node* insertNode(struct node* node, int val) {
  if (node == NULL) return createNode(val);
  if (val < node->data)
    node->left = insertNode(node->left, val);
  else if (val > node->data)
    node->right = insertNode(node->right, val);
  return node;
}

Trong hàm main(), nút gốc được định nghĩa là NULL. Sau đó chèn các nút với giá trị cần thiết vào cây tìm kiếm nhị phân:

struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);

Cuối cùng, gọi hàm preorder() với gốc của cây và hiển thị tất cả giá trị theo tiền tự:

cout << "Duyệt tiền tự của cây tìm kiếm nhị phân: ";
preorder(root);