二叉樹是一種常見的數據結構，廣泛應用于計算機科學中。它由節點組成，每個節點最多有兩個子節點，分別稱為左子節點和右子節點。本文將介紹如何在C語言中實現二叉樹的基本操作，包括創建、插入、遍歷、查找和刪除等。
在C語言中，二叉樹可以通過結構體來定義。每個節點包含數據域和兩個指針域，分別指向左子節點和右子節點。
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
創建一個二叉樹通常從根節點開始，然后逐步添加子節點。我們可以通過遞歸的方式來創建二叉樹。
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
插入節點的操作通常根據二叉搜索樹（BST）的規則進行。對于二叉搜索樹，左子節點的值小于父節點，右子節點的值大于父節點。
struct TreeNode* insertNode(struct TreeNode* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
二叉樹的遍歷方式主要有三種：前序遍歷、中序遍歷和后序遍歷。
前序遍歷的順序是：根節點 -> 左子樹 -> 右子樹。
void preOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
中序遍歷的順序是：左子樹 -> 根節點 -> 右子樹。
void inOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
后序遍歷的順序是：左子樹 -> 右子樹 -> 根節點。
void postOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
在二叉樹中查找一個節點，通常使用遞歸的方法。
struct TreeNode* searchNode(struct TreeNode* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchNode(root->left, data);
} else {
return searchNode(root->right, data);
}
}
刪除節點的操作相對復雜，需要考慮多種情況：節點沒有子節點、節點有一個子節點、節點有兩個子節點。
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
if (root == NULL) return root;
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// 節點沒有子節點或只有一個子節點
if (root->left == NULL) {
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
}
// 節點有兩個子節點，找到右子樹的最小節點
struct TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
// 將最小節點的值復制到當前節點
root->data = temp->data;
// 刪除右子樹的最小節點
root->right = deleteNode(root->right, temp->data);
}
return root;
}
在程序結束時，需要釋放二叉樹占用的內存，防止內存泄漏。
void freeTree(struct TreeNode* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
以下是一個完整的示例代碼，展示了如何創建、插入、遍歷、查找和刪除二叉樹節點。
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct TreeNode* insertNode(struct TreeNode* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
void preOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
void inOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
void postOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
struct TreeNode* searchNode(struct TreeNode* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchNode(root->left, data);
} else {
return searchNode(root->right, data);
}
}
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
if (root == NULL) return root;
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
if (root->left == NULL) {
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
}
struct TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
void freeTree(struct TreeNode* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
struct TreeNode* root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("In-order traversal: ");
inOrderTraversal(root);
printf("\n");
printf("Pre-order traversal: ");
preOrderTraversal(root);
printf("\n");
printf("Post-order traversal: ");
postOrderTraversal(root);
printf("\n");
struct TreeNode* found = searchNode(root, 40);
if (found != NULL) {
printf("Node 40 found\n");
} else {
printf("Node 40 not found\n");
}
root = deleteNode(root, 20);
printf("In-order traversal after deleting 20: ");
inOrderTraversal(root);
printf("\n");
freeTree(root);
return 0;
}
本文介紹了如何在C語言中實現二叉樹的基本操作，包括創建、插入、遍歷、查找和刪除節點。通過這些操作，我們可以有效地管理和操作二叉樹數據結構。希望本文對你理解和使用二叉樹有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
