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

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

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

Duyệt hậu tự (Postorder): 1 5 4 8 6

Chương trình thực hiện duyệt hậu 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 postorder(struct node *root) {
  if (root != NULL) {
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
  }
}

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 hậu tự của cây tìm kiếm nhị phân: ";
  postorder(root);
  return 0;
}

Kết quả đầu ra

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

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 postorder() nhận gốc của cây nhị phân và in các phần tử theo hậu tự. Đây là hàm đệ quy:

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

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 postorder() với gốc của cây và hiển thị tất cả giá trị theo hậu tự:

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