以下是C語言中二叉樹的三種遍歷方式(前序遍歷、中序遍歷和后序遍歷)的代碼實現:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// 創建新節點
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if(newNode == NULL) {
printf("內存分配失敗!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 前序遍歷
void preorderTraversal(Node* root) {
if(root != NULL) {
printf("%d ", root->data); // 先訪問根節點
preorderTraversal(root->left); // 再前序遍歷左子樹
preorderTraversal(root->right); // 最后前序遍歷右子樹
}
}
// 中序遍歷
void inorderTraversal(Node* root) {
if(root != NULL) {
inorderTraversal(root->left); // 先中序遍歷左子樹
printf("%d ", root->data); // 再訪問根節點
inorderTraversal(root->right); // 最后中序遍歷右子樹
}
}
// 后序遍歷
void postorderTraversal(Node* root) {
if(root != NULL) {
postorderTraversal(root->left); // 先后序遍歷左子樹
postorderTraversal(root->right); // 再后序遍歷右子樹
printf("%d ", root->data); // 最后訪問根節點
}
}
int main() {
// 創建二叉樹
Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// 前序遍歷二叉樹
printf("前序遍歷:");
preorderTraversal(root);
printf("\n");
// 中序遍歷二叉樹
printf("中序遍歷:");
inorderTraversal(root);
printf("\n");
// 后序遍歷二叉樹
printf("后序遍歷:");
postorderTraversal(root);
printf("\n");
return 0;
}
這段代碼首先定義了一個二叉樹節點的結構體 Node
,其中包含數據 data
、左子節點指針 left
和右子節點指針 right
。接著,定義了創建新節點的函數 createNode
,用于動態分配內存,并返回新節點。然后,分別實現了三種遍歷方式的函數:preorderTraversal
(前序遍歷)、inorderTraversal
(中序遍歷)和 postorderTraversal
(后序遍歷)。最后,在 main
函數中創建了一個二叉樹,并分別調用了三種遍歷函數,打印出遍歷結果。