数据结构学习笔记 ：树与二叉树详解

目录

1. 树的基本概念
2. 二叉树的定义与特性
3. 二叉树的存储结构
   3.1 顺序存储
   3.2 链式存储
4. 二叉树遍历
5. 特殊二叉树类型
6. 总结与应用场景

---

一、树的基本概念

核心定义

• 树：由根节点和若干子树构成的层次结构。
• 叶子节点（终端节点）：没有子节点的节点。
• 分支节点：有子节点的节点（根节点除外）。
• 树的高度：节点所在层次的最大值。
• 节点的度：子节点的数量；树的度：所有节点度的最大值。

树的性质

1. 树中的结点数等于所有结点的度数之和加1。
2. 度为m的树的第i层最多有m^(i-1)个节点。
3. 满二叉树与完全二叉树的特殊性质（见后文）。

---

二、二叉树的定义与特性

二叉树的定义

• 二叉树：每个节点最多有两个子节点（左子树和右子树）。
• 五种形态：
  1. 空树；
  2. 只有根节点；
  3. 根节点+左子树；
  4. 根节点+右子树；
  5. 根节点+左子树+右子树。

---

三、二叉树的存储结构

1. 顺序存储（数组实现）

#include <stdio.h>
#include <stdbool.h>
#define MaxSize 100
typedef int ElemType;typedef struct Tree {ElemType data[MaxSize]; // 数据域bool flag[MaxSize];     // 标记节点是否有效
} Tree;// 初始化
void InitTree(Tree *t) {for (int i = 0; i < MaxSize; i++) {t->flag[i] = false;}
}// 插入节点（构建二叉排序树）
bool insert_node(Tree *t, ElemType e) {int i = 1;while (i < MaxSize) {if (t->flag[i]) {if (t->data[i] >= e) {i = 2 * i; // 左子树方向} else {i = 2 * i + 1; // 右子树方向}} else {t->flag[i] = true;t->data[i] = e;return true;}}return false;
}// 查找节点
int find_tree(Tree *t, ElemType e) {int i = 1;while (i <= MaxSize) {if (t->flag[i]) {if (t->data[i] > e) {i = 2 * i; // 左子树方向} else if (t->data[i] < e) {i = 2 * i + 1; // 右子树方向} else {return i; // 找到返回编号}} else {return -1; // 未找到}}return -1;
}

---

2. 链式存储（动态节点）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElemType;typedef struct BitNode {ElemType data;struct BitNode *lchild, *rchild;
} BitNode, *BitTree;// 新建节点
BitNode* newnode(ElemType e) {BitNode* node = (BitNode*)malloc(sizeof(BitNode));if (!node) return NULL;node->data = e;node->lchild = node->rchild = NULL;return node;
}// 插入节点（构建二叉排序树）
bool insert_node(BitTree *t, BitNode *new) {if (*t == NULL) { // 空树插入根节点*t = new;return true;}BitNode *p = *t;while (1) {if (new->data < p->data) { // 左子树方向if (p->lchild == NULL) {p->lchild = new;return true;}p = p->lchild;} else if (new->data > p->data) { // 右子树方向if (p->rchild == NULL) {p->rchild = new;return true;}p = p->rchild;} else {return false; // 数据重复}}
}

---

四、二叉树遍历

三种遍历方式

1. 前序遍历（根左右）

void PreOrder(BitNode *root) {if (root == NULL) return;printf("%d ", root->data);PreOrder(root->lchild);PreOrder(root->rchild);
}

2. 中序遍历（左根右）

void MidOrder(BitNode *root) {if (root == NULL) return;MidOrder(root->lchild);printf("%d ", root->data);MidOrder(root->rchild);
}

3. 后序遍历（左右根）

void PostOrder(BitNode *root) {if (root == NULL) return;PostOrder(root->lchild);PostOrder(root->rchild);printf("%d ", root->data);
}

---

五、特殊二叉树类型

1. 满二叉树

• 定义：高度为h的二叉树有2^h - 1个节点。
• 特点：
  • 除最后一层外，所有层的节点数达到最大。
  • 无度为1的节点。
  • 节点编号按层序从1开始，父节点i的左右子节点分别为2i和2i+1。

2. 完全二叉树

• 定义：编号与满二叉树一致，即叶子节点仅出现在最后一层或倒数第二层。
• 性质：可高效用数组存储。

3. 二叉排序树（BST）

• 定义：左子树所有节点值 < 根节点值 < 右子树所有节点值。
• 应用：快速搜索、插入和删除操作（平均时间复杂度O(log n)）。

4. 平衡二叉树（AVL树）

• 定义：所有节点的左右子树高度差≤1。
• 作用：保证树的平衡性，避免退化为链表，确保操作效率。

---

六、总结与应用场景

核心总结

1. 存储选择：
   • 顺序存储：适合完全二叉树（如堆）。
   • 链式存储：通用，支持动态扩展。
2. 遍历用途：
   • 前序：复制二叉树。
   • 中序：对二叉排序树进行升序遍历。
   • 后序：释放内存、计算表达式。

典型应用场景

• 二叉排序树：数据库索引、快速查找。
• 平衡二叉树：需要高效插入/删除的场景（如动态数据集合）。
• 堆（完全二叉树）：优先队列实现。

---

希望这篇笔记能帮助读者掌握树与二叉树的核心概念及实现方法！