C语言二叉树学习笔记

---

目录

• 树的基本概念
• 二叉树的定义与类型
• 二叉排序树（BST）
• 二叉树的遍历
• 二叉树的操作
• 总结

---

树的基本概念

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;
}

---

总结

核心知识点

1. 二叉树结构：每个节点最多两个子节点，分为左子树和右子树。
2. 二叉排序树（BST）：左小右大的特性，支持高效查找、插入和删除。
3. 遍历方式：
   • 前序：根→左→右
   • 中序：左→根→右
   • 后序：左→右→根
4. 内存管理：使用malloc动态分配节点内存，用free释放内存。

注意事项

• 平衡性：BST的性能依赖于树的平衡，极端情况下可能退化为链表（时间复杂度变为O(n)）。
• 递归操作：遍历和操作通常使用递归实现，需注意递归终止条件。

---

练习题

1. 实现一个函数，计算二叉树的深度（高度）。
2. 编写代码，判断一棵二叉树是否为二叉排序树（BST）。