C语言二叉树学习笔记

树的基本概念

1. 什么是树？

树：一种非线性数据结构，由节点和边组成，模拟分层关系。
核心术语：
- 根节点：树的顶层节点（唯一）。
- 子节点/双亲节点：一个节点的直接下层节点称为子节点，该节点称为子节点的双亲节点。
- 叶子节点：没有子节点的节点。
- 节点的度：节点的子节点数量。
- 树的深度/高度：树中节点的最大层次（根节点为第1层）。

2. 树的特点

递归结构：每个子树本身也是一棵树。
应用场景：文件系统、组织结构、数据库索引等。

二叉树的定义与类型

1. 什么是二叉树？

二叉树：每个节点最多有2个子节点（左子节点和右子节点）。
特点：
- 子树有明确的左右之分。
- 可以为空树（没有节点）。

2. 特殊二叉树类型

类型	定义
满二叉树	深度为`k`的二叉树有`2^k - 1`个节点，每层节点数达到最大值。
完全二叉树	除最后一层外，其他层是满的，且最后一层节点从左到右连续（无中间空缺）。

二叉排序树（BST）

1. BST的定义

性质：
1. 左子树所有节点的值 < 根节点的值。
2. 右子树所有节点的值 > 根节点的值。
3. 左右子树也是BST。

2. BST的优势

高效查找：利用二分法思想，时间复杂度为O(log n)（平衡情况下）。

二叉树的遍历

1. 前序遍历（根→左→右）

void preOrder(struct Node* root) {if (root != NULL) {printf("%d ", root->data); // 访问根节点preOrder(root->left);      // 遍历左子树preOrder(root->right);     // 遍历右子树}
}

示例：遍历顺序为 A → B → D → H → I → E → J → C → F → G。

2. 中序遍历（左→根→右）

void inOrder(struct Node* root) {if (root != NULL) {inOrder(root->left);       // 遍历左子树printf("%d ", root->data); // 访问根节点inOrder(root->right);      // 遍历右子树}
}

示例：遍历顺序为 H → D → I → B → J → E → A → F → C → G。

3. 后序遍历（左→右→根）

void postOrder(struct Node* root) {if (root != NULL) {postOrder(root->left);     // 遍历左子树postOrder(root->right);    // 遍历右子树printf("%d ", root->data); // 访问根节点}
}

示例：遍历顺序为 H → I → D → J → E → B → F → G → C → A。

二叉树的操作

1. 创建二叉树

#include <stdlib.h>struct Node {int data;struct Node* left;struct Node* right;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}

2. 插入节点（BST）

struct Node* insertBST(struct Node* root, int data) {if (root == NULL) {return createNode(data); // 创建新节点}if (data < root->data) {root->left = insertBST(root->left, data); // 插入左子树} else if (data > root->data) {root->right = insertBST(root->right, data); // 插入右子树}return root;
}

3. 查找节点（BST）

struct Node* searchBST(struct Node* root, int key) {if (root == NULL || root->data == key) {return root; // 找到节点或空树}if (key < root->data) {return searchBST(root->left, key); // 左子树查找} else {return searchBST(root->right, key); // 右子树查找}
}

4. 删除节点（BST）

struct Node* deleteNode(struct Node* root, int key) {if (root == NULL) return root;if (key < root->data) {root->left = deleteNode(root->left, key); // 左子树删除} else if (key > root->data) {root->right = deleteNode(root->right, key); // 右子树删除} else {// 找到目标节点if (root->left == NULL) {struct Node* temp = root->right;free(root);return temp;} else if (root->right == NULL) {struct Node* temp = root->left;free(root);return temp;}// 左右子树均存在，找右子树的最小节点替换struct Node* temp = root->right;while (temp->left != NULL) {temp = temp->left;}root->data = temp->data;root->right = deleteNode(root->right, temp->data);}return root;
}