Daisy's Blog
ZJU 数据结构课程笔记 | 树
Daisy Author
  2023-07-17 11:17:58   2024-10-19 23:23:34    2.7k Words  10 Mins

这是我在学习浙江大学 MOOC『数据结构』的第三章：树 的过程中做的笔记。

ZJU 数据结构 MOOC 课程链接

问题引入

梳理层次关系

分层次组织管理具有高效性

如何实现有效率的查找？

def 查找：根据某个给定关键字K，从集合R中找出与K相同的记录

  1. 静态查找：记录固定
    • 没有插入和删除操作，只有查找
  2. 动态查找：记录动态变化
    • 除了查找，还可能发生插入和删除

p1

操作对象 在数组内==有序连续==存放的数据元素 o()

p2

5. left = 4, right = mid - 1 = 3, left > right? 查找失败，结束

1
2
3
4
5
6
7
8
9
10
11
12
13
int BinarySearch(List Tbl, ElementType K)
{
	int left, right, mid, NoFound = -1;
	left = 1;
	right = Tgl -> Length;
	while (left <= right) {
		mid = (left + right) / 2;
		if (K < Tbl -> Element[mid]) right = mid - 1;
		else if (K > Tbl -> Element[mid]) left = mid + 1;
		else return mid;
	}
	return NotFound;
}

p3

查找树为解决动态查找问题提供思路

树(Tree)

定义

def 树：n个节点构成的有限集合

n = 0时，称为空树

任意非空树（n > 0），具备如下性质

  • 一个根（root）节点，用r表示
  • 其余节点分为m（m > 0）个互不相交的有限集合， … ，其中每个集合本身又是一棵树，称为原来树的子树（subtree）
  1. 子树是不相交的
  2. 除了根结点，每个结点有且仅有一个父结点
  3. 一棵N个基点的树有N - 1条边

p4

基本术语

  1. 结点的度（Degree）：子树个数
  2. 树的度：所有结点中最大的度数
  3. 叶节点（Leaf）：度为0的结点
  4. 父节点（Parent）：有子树的结点是其子树的根节点的父结点
  5. 子节点（Child）：若A是B的父结点，则称B是A的子结点
  6. 兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点
  7. 路径和路径长度：结点到的路径为一个结点序列，是的父节点，路径所包含的边数为路径长度
  8. 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先节点
  9. 子孙结点（Ancestor）：某一结点的子树中的所有结点时这个结点的子孙
  10. 结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父节点的层数加1
  11. 树的深度（Depth）：树中所有结点的最大层次是这棵树的深度

树的表示

由于树的空间结构比较复杂，使用顺序结构难以判断结点间的相互关系，故顺序存储方式难以实现！

树的链式结构实现

child-sibling表示法

p5

将结果树旋转45°得到一棵每个结点有至多两个分支的树状结构,称二叉树

树的同构

def 同构: 给定两棵树T1, T2, 若T1可以通过若干次左右孩子互换变化为T2,则称两棵树是同构的

二叉树(Binary Tree)

def 二叉树T: 一个有穷结点集合

  • 集合可以为空
  • 若不为空,则其由根节点和称为其左子树 和右子树 的两个不相交的二叉树构成

p6

特殊二叉树

p7

重要性质

  1. 一个二叉树第i层最大结点数为: (i 1)
  2. 深度为k的二叉树有最大结点总数为: (k 1)
  3. 对于任何非空二叉树T,若表示叶结点的个数,是度为2的非叶结点个数,则

二叉树的顺序结构实现

完全二叉树:

按从上到下,从左到右顺序存储n个结点的完全二叉树的结点父子关系

  • 非根结点(i > 1)的父节点的序号为[i/2]
  • 结点(i)的左子结点的序号为2i (2i n, 否则没有左子节点)
  • 结点(i + 1)的右子结点的序号是2i + 1 (2i + 1 n, 否则没有右子结点)

一般二叉树也可通过结点补齐的方式转化为完全二叉树, 从而能够采用顺序结构实现 空间浪费

二叉树的链式结构实现

p8

1
2
3
4
5
6
7
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

二叉树的递归遍历

1. 先序遍历

① 访问根结点
② 先序遍历其左子树
③ 先序遍历其右子树

递归解法

1
2
3
4
5
6
7
8
void PreOrderTraversal(BinTree* BT)
{
	if (BT) {
		printf("%d", BT -> Data);
		PreOrderTraversal(BT -> Left);
		PreOrcerTraversal(BT -> Right);
	} 
}

非递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> PreOrderTraversal(TreeNode* Root) {
	vector<int> ans;
	if (Root == nullptr) return ans;
	stack<TreeNode*> travis;
	TreeNode* p = Root;
	do {
		if (p) {
			ans.push_back(p -> val);
			travis.push(p);
			p = p -> left;
		} else {
			p = travis.top();
			travis.pop();
			p = p -> right;
		}
	} while (!travis.empty() || p)
}

2. 中序遍历

① 中序遍历其左子树
② 访问根结点
③ 中序遍历其右子树

1
2
3
4
5
6
7
8
void InOrderTraversal(BinTree* BT)
{
	if (BT) {
		InOrderTraversal(BT -> Left);
		printf("%d", BT -> Data);
		InOrderTraveersal(BT -> Right);
	}
}

3. 后序遍历

① 后续遍历其左子树
② 后序遍历其右子树
③ 访问根结点

递归解法

1
2
3
4
5
6
7
8
void PostOrderTraversal(BinTree* BT)
{
	if (BT) {
		PostOrderTraversal(BT -> Left);
		PostOrderTraversal(BT -> Right);
		printf("%d", BT -> Data);
	}
}

非递归解法

根据二叉树前序或后续遍历的任一结果与中序遍历结果,可以唯一确定该二叉树

二叉树的非递归遍历

思路: 使用堆栈

1. 前序遍历

① 遇到一个结点, 压入栈中,并进行访问
② 前序遍历其左子树
③ 继续按其右指针进行右子树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrderTraversal(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreateStack(MaxSize); //创建堆栈并初始化
	while (T || !IsEmpty(S)) {
		while (T) { //向左子树遍历,将沿途结点压入堆栈
			Push(S, T);
			printf("%5d", T -> Data); //访问结点(打印)
			T = T -> left;
		}
		if (! IsEmpty(S)) {
			T = Pop(S); //结点弹出堆栈
			T = T -> Right; //转向右子树
		}
	}
}

2. 中序遍历

① 遇到一个结点, 压入栈中, 并遍历其左子树
② 左子树遍历完成后, 从栈顶弹出该结点进行访问
③ 访问完成后,继续按其右指针进行右子树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrderTraversal(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreateStack(MaxSize); //创建堆栈并初始化
	while (T || !IsEmpty(S)) {
		while (T) { //向左子树遍历,将沿途结点压入堆栈
			Push(S, T);
			T = T -> left;
		}
		if (! IsEmpty(S)) {
			T = Pop(S); //结点弹出堆栈
			printf("%5d", T -> Data); //访问结点(打印)
			T = T -> Right; //转向右子树
		}
	}
}

3. 后序遍历

① 沿着根的左孩子, 依次入栈, 直到左孩子为空
② 读栈顶元素进行判定, 若右孩子不空且未被访问, 将右孩子执行第一步
③ 栈顶元素出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 vector<int> PostOrderTraversal(TreeNode* Root) {
	TreeNode* p = Root;
	vector<int> ans;
	if (p == nullptr) return ans;
	stack<TreeNode*> travis;
	travis.push(p);
	while (!travis.empty()) {
		p = travis.top();
		travis.pop();
		if (p) {
			travis.push(p);
			travis.push(nullptr);
			if (p -> right) travis.push(p -> right);
			if (p -> left) travis.push(p -> left);
		} else {
			p = travis.top();
			travis.pop();
			ans.push_back(p -> val);
		}
	} 
	return ans;
}

二叉树的层序遍历

核心问题: 二维结构的线性化

  • 从结点访问其左, 右儿子结点
  • 访问左儿子后, 右儿子怎么办?
    • 需要一个存储结构保存暂时不访问的结点
    • 存储结构: 堆栈, 队列

队列实现

  1. 遍历从根结点开始, 首先将根结点入队, 然后开始执行循环
  2. 从队列中取出一个元素, 访问该元素所指向的结点
  3. 若该元素所指结点的左右孩子结点非空, 则将其左右孩子结点顺序入队
1
2
3
4
5
6
7
8
9
10
11
12
13
void LevelOrderTraversal(BinTree BT)
{
	Queue Q; BinTree T;
	if (! BT) return ;
	Q = CreatQueue(MaxSize);
	AddQ(Q, BT);
	while (! IsEmptyQ(Q)) {
		T = DeleteQ(Q);
		visit(T);
		if (T -> Left) AddQ(Q, T -> Left);
		if (T -> Right) AddQ(Q, T -> Right);
	}
}

二叉搜索树(BST)

def BST: 一棵二叉树,可以为空; 若不为空, 则满足以下性质:

  1. 非空左子树的所有键值小于其根结点的键值
  2. 非空右子树的所有键值大于其根结点的键值
  3. 左右子树均为二叉搜索树

p9

funtion Find

  • 查找从根结点开始, 若树为空, 返回NULL
  • 若搜索树非空, 则根结点关键字与X进行比较, 进行不同处理:
    1. 若X＜根结点键值, 只需在左子树中进行搜索
    2. 若X＞根结点键值, 只需在右子树中进行搜索
    3. 若两者比较结果是相等, 搜索完成, 返回指向此节点的指针
1
2
3
4
5
6
7
8
9
10
Position Find(ElementType Z, BinTree BST)
{
	if (!BST) return NULL;
	if (X > BST -> Data)
		return Find(X, BST -> Right);
	else if (X < BST -> Data)
		return Find(X, BST -> Left); //尾递归
	else
		return BST; 
}

def 尾递归: 递归调用发生在函数的最后一个语句后

由于非递归函数执行效率高, 故而尾递归函数可以利用循环进行优化, 改为迭代函数

1
2
3
4
5
6
7
8
9
10
11
12
Position IterFind(ElementType X, BinTree BST)
{
	while (BST) {
		if (X > BST -> Data)
			BST = BST -> Right;
		else if (X < BST -> Data)
			BST = BST -> Left;
		else
			return BST;
	}
	return NULL; //查找失败
}

查找效率决定树的高度 -> 为维持结构均衡性, 引入平衡二叉树

function Find Min / Max

最小值查找

1
2
3
4
5
6
7
8
9
Position FindMin(BinTree BST)
{
	//一直沿着左分支查找, 直到左孩子为空
	if (!BST) return NULL;
	else if (!BST -> Left)
		returtn BST;
	else 
		return FindMin(BST -> Left);
}

最大值查找

1
2
3
4
5
6
7
Positon FindMax(BinTree BST)
{
	//一直沿着右分支查找, 直到右孩子为空
	if (BST)
		while(BST -> Right) BST = BST -> Right;
	return BST; 
}

funtion Insert

关键是找到元素插入位置, 可采用与Find相似的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BinTree Insert(ElementType X, BinTree BST)
{
	if (!BST) {
		BST = (BinTree)malloc(sizeof(struct TReeNode))
		BST -> Data = X:
		BST -> Left = NULL;
		BST -> Right = NULL;
	} else { 
		if (X < BST -> Data)
			BST -> Left = Insert(X, BST -> Left);
		else if (X > BST -> Data)
			BST -> Right = Insert(X, BST -> Right);
	}
	return BST;
}

funtion Delete

三种情况

  1. 删除叶结点: 直接删除, 再修改其父节点相应指针为NULL
  2. 删除结点仅一孩子: 将其父结点相应指针指向要删除结点的孩子结点
  3. 删除结点有左右两棵子树: 用另一结点代替被删除的结点(右子树的最小元素或左子树的最大元素)

p15

平衡二叉树(AVL)

def 平衡因子(Balance Factor): BF(T) = -

def 平衡二叉树(Balance Binary Tree):

  1. 空树
  2. 任一结点左, 右子树高度差的绝对值不超过1, 即abs(BF) 1

给定结点数为n的AVL树的最大高度为O(n)

平衡二叉树的调整

对AVL树的插入与删除操作可能破坏其平衡性

  • RR插入

p10

  • LL插入

p11

  • LR插入

p12

  • RL插入

p13

计算完全二叉树左右子树规模

已知总结点树, 以左子树为例:

p14

忽略X, 结果向下取整求出H, 再利用H反推出X.

ZJU 数据结构课程笔记 | 树
2023/07/17/Data-Structures-note-3/
Author
Daisy
Published
2023-07-17 11:17
License
  1. 问题引入
    1. 二分查找(Binary Search)
  2. 树(Tree)
    1. 定义
  3. 基本术语
  4. 树的表示
    1. 树的链式结构实现
    2. 树的同构
  5. 二叉树(Binary Tree)
    1. 特殊二叉树
    2. 重要性质
  6. 二叉树的顺序结构实现
  7. 二叉树的链式结构实现
    1. 二叉树的递归遍历
      1. 1. 先序遍历
      2. 2. 中序遍历
      3. 3. 后序遍历
    2. 二叉树的非递归遍历
      1. 1. 前序遍历
      2. 2. 中序遍历
      3. 3. 后序遍历
    3. 二叉树的层序遍历
      1. 队列实现
  8. 二叉搜索树(BST)
    1. funtion Find
    2. function Find Min / Max
    3. funtion Insert
    4. funtion Delete
  9. 平衡二叉树(AVL)
    1. 平衡二叉树的调整
  10. 计算完全二叉树左右子树规模
  1. 问题引入
    1. 二分查找(Binary Search)
  2. 树(Tree)
    1. 定义
  3. 基本术语
  4. 树的表示
    1. 树的链式结构实现
    2. 树的同构
  5. 二叉树(Binary Tree)
    1. 特殊二叉树
    2. 重要性质
  6. 二叉树的顺序结构实现
  7. 二叉树的链式结构实现
    1. 二叉树的递归遍历
      1. 1. 先序遍历
      2. 2. 中序遍历
      3. 3. 后序遍历
    2. 二叉树的非递归遍历
      1. 1. 前序遍历
      2. 2. 中序遍历
      3. 3. 后序遍历
    3. 二叉树的层序遍历
      1. 队列实现
  8. 二叉搜索树(BST)
    1. funtion Find
    2. function Find Min / Max
    3. funtion Insert
    4. funtion Delete
  9. 平衡二叉树(AVL)
    1. 平衡二叉树的调整
  10. 计算完全二叉树左右子树规模