Chương trình C++ thực hiện duyệt trung tự (inorder) đệ 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 trung tự (inorder) của cây tìm kiếm nhị phân thăm các nút theo thứ tự: (Trái, Gốc, Phải).

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

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

Duyệt trung tự (Inorder): 1 4 5 6 8

Chương trình thực hiện duyệt trung 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 inorder(struct node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->data << " ";
    inorder(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 trung tự của cây tìm kiếm nhị phân: ";
  inorder(root);
  return 0;
}

Kết quả đầu ra

Duyệt trung tự của cây tìm kiếm nhị phân: 1 2 3 4 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 inorder() nhận gốc của cây nhị phân và in các phần tử theo trung tự. Đây là hàm đệ quy:

void inorder(struct node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->data << " ";
    inorder(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 inorder() với gốc của cây và hiển thị tất cả giá trị theo trung tự:

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