luffy博客

六、树和二叉树

12/14/2023 data-structure_c

# 六、树和二叉树

# 树

# 树的定义

有n(n≥0)个结点的有限集合。当n=0时，称为空树；任意一颗非空树应满足以下条件：

​ 1)、有且只有 一个根结点

​ 2)、当n>1时，除根结点外的其余结点被分成m(m>0)个互不相交的有线集合T1，T2,...,Tm,其中每个集合又是一棵树，并称为这个根结点的子树

# 树的相关术语

*(下列此相关术语解释以下图做参考)

image_20231209153427761

  • 结点的度：结点所拥有的子树的个数。例：D有三个子树，即D结点的度为3；

  • 树的度：树中所有结点的度的最大值。上图树的度为3.因为所有结点中最大的度为3；

  • 祖先结点：往上知道根结点，做经过的所有结点都称为祖先结点。例：E的祖先结点有B、A；

  • 子孙结点：一个结点的所有分支。例：B的子孙结点有K、L、E、F；

  • 双亲结点/父结点：往上一级结点。例：E的双亲结点为B；

  • 孩子结点：往下一级结点。例：B的孩子结点有E、F；(*孩子结点只包括往下一级，而子孙结点包括往下的所有)

  • 兄弟结点：同一个前驱结点。例：E、F都是由B分出来的，即E、F为兄弟结点；

  • 堂兄弟结点：处于同一级且不是同一个前驱结点。例：E、G的前驱结点不是同一个，即E、G为堂兄弟结点；

  • 路径：从根结点A开始到结点E，路径为A->B->E,其路径长度就是有几条边，A到E的路径长度为2；

  • 有序树&无序树：从逻辑上看，有序树中结点的各子树从左至右是有次序的，不可互换；而无序树中结点的各子树从左至右是无次序的，可以互换；

# 树的基本性质

​ 1)、树中的结点数等于所有结点的度数之和加一；(*加一是因为每个结点有且仅有一个前驱结点，才构成度，但是根结点是没有前驱结点的，加一即加上跟结点)

​ 2)、度为m的树中第i层上最多有m^(i-1)个结点（i≥1）

​ 3)、高度为h的m叉树最多有m^(h)-1/m-1个结点

​ 4)、具有n个结点的m叉树的最小高度是：log( n(m-1) + 1)以m为底；

# 树的基本运算

# 先根遍历(根左右)

①先访问根节点。②按照从左到右的顺序先遍历根结点的每一颗子树。按照上图的先根遍历结果为：ABEKLFCGDHMIJ

# 后根遍历(左右根)

①按照从左到右的顺序先遍历根结点的每一颗子树。②访问根结点。按照上图的后根遍历结果：KLEFBGCMHIJDA

# 层次遍历

即头结点开始依次从上往下从左往右的顺序访问每一个结点。按照上图层次遍历的结果：ABCDEFGHIJKLM

# 树的存储结构

# 双亲表示法

​ 是一种顺序存储结构，用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器parent指示其双亲结点在表中的位置。

typedef struct
{
	Elemtype data; //存放节点数据
	int parent;//存放双亲的位置
}PTree[MaxSize];
1
2
3
4
5
image_20231209200722288

# 孩子表示法

​ 用一组连续的空间来存储树中的结点，把每个结点的孩子在表中的位置（并非孩子本身）排列起来构成一个单链表，称为孩子链表。n个结点共有n个孩子链表。

typedef struct node{
	ElemType data;//结点的值
	struct node * sons[MaxSons];//指向孩子结点
}TSonNode;
1
2
3
4
image_20231209201422592

# 二叉树

# 定义

​ 有限的结点的集合，由根结点和不相交的二叉子树组成；

​ 二叉树的五种基本形态：

image_20231209185330775

# 树和二叉树的联系与区别

​ 满足以下两个条件的树形结构叫做二叉树：

  • 每个结点至多只有两棵子树
  • 二叉树的子树有左右之分，其次序不能颠倒，是有序树。而树可以有序可以无序

【孩子与双亲：结点若有直接后继，则可称它为它直接后继结点的父亲或双亲，直接后继结点为它的孩子，位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子】

# 二叉树的基本术语

  • 结点的度：结点直接后继的个数
  • 树的度：树的所有结点的度的最大值
  • 叶子结点：也称终端结点，即度为0的结点
  • 分支结点：也称非终端结点，即度不为0的结点
  • 孩子结点：结点的直接后继
  • 双亲结点：结点的直接前驱
  • 兄弟结点：同一双亲结点的孩子结点互称兄弟结点

# 二叉树的分类

# 满二叉树

一颗高度为h，且含有2^h-1结点的二叉树。(人话：除了根结点外，其余分支结点都有两个度，不存在只有一个度的结点)如下图：

image_20231209212640017

**特点：**①不存在度为1的结点

​ ②只有最后一层有叶子节点

​ ③按层序从1开始编号，结点为i的左孩子为2i，右孩子为2i+1，结点i的父结点为i/2(如果有的话)

# 完全二叉树

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

image_20231209213237804

**特点：**①只有最后两层可能有叶子结点 ②最多只有一个度为1的结点 ③按层序从1开始编号，结点为i的左孩子为2i，右孩子为2i+1，结点i的父结点为i/2(如果有的话) ④i≤n/2为分支结点，i>n/2为叶子结点

​ (补充：1.对于完全二叉树，如果只有一个子结点时，那么一定是左结点

​ 2.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树)

# 二叉排序树

一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:

  • ​ 左子树上所有结点的关键字均小于根结点的关键字;
  • ​ 右子树上所有结点的关键字均大于根结点的关键字。
  • ​ 且左子树和右子树又各是一颗二叉排序树 。
image_20231209214200577

# 平衡二叉树

树上任意结点的左子树与右子树的深度之差不超过1

image_20231209214445656

# 二叉树的存储结构

# 顺序存储

顺序结构存储就是使用数组来存储，按编号顺序存储。

所以对于完全二叉树，直接从根起按层序存储即可，依次自上向下自左向右存储结点元素，将完全二叉树中编号为i的结点存储在数组中下标为i-1的分量中。而对于一般的二叉树，由于也是按照编号存储，二叉树的顺序存储中可能会出现大量未用分量，十分浪费空间所以对于一般二叉树，不适合用顺序存储，

由此可见二叉树的顺序存储只适合完全二叉树的存储。对于一般二叉树，更适合二叉树的链式存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

image_20231216150812897

# 链式存储

二叉树由根节点和左右子树构成（如a图）。所以二叉树的结点由数据域，左右指针域，三个部分构成（如图b）。为了便于寻找结点的双亲，我们可以增加一个指向双亲结点的指针域。（如图c）

image_20231216150908142

利用这两种结点，所得到的二叉树的存储结构分别称为二叉链表和三叉链表：

image_20231216151016579 
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
}

// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 二叉树的遍历

按照一定的次序访问二叉树中的所有结点，并且每个 结点仅被访问一次的过程。分别用LDR表示二叉树的根节点，左子树，右子树。我们就有3！种遍历顺序，若规定先左后右，就只有三种：DLR、LDR、LRD，分别对应先序遍历、中序遍历、后续遍历。

# 先、中、后序遍历（递归）

//先序——访问根结点的操作发生在遍历其左右子树之前。
void PreOrder(BTNode *b)
{  if (b!=NULL)  
   {  printf("%c "，b->data); 	//访问根结点
      PreOrder(b->lchild);
      PreOrder(b->rchild);
   }
}

//中序——访问左结点的操作发生在遍历其根结点和右子树之前。
void InOrder(BTNode *b)
{  if (b!=NULL)  
   {  InOrder(b->lchild);
      printf("%c "，b->data); 	//访问根结点
      InOrder(b->rchild);
   }
}

//后序——访问左右结点的操作发生在遍历其根结点之前。
void PostOrder(BTNode *b) 
{  if (b!=NULL)  
   {  PostOrder(b->lchild);
      PostOrder(b->rchild);
      printf("%c "，b->data); 	//访问根结点
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这里算法中的访问是直接输出结点值。实际上，访问结点可以对该结点进行各种操作，如计数、删除结点等。3种递归算法的执行过程是递归的。以先序遍历图解：

image_20231216151120504

# *先、中、后序遍历（非递归）

递归在系统中本质就是系统栈的使用，所以递归能遍历二叉树，那么就能使用栈堆二叉树进行非递归遍历。

算法思路：

  1. 初始化空战，指针p指向根节点H

  2. 申请一个结点空间用来存放栈顶弹出去的元素

  3. 当p非空或栈非空，循环执行以下操作：

    如果p非空，则p进栈，p指向该节点的左孩子

    如果p为空，则弹出栈顶元素并访问根节点，将p指向该节点的有孩子

  4. 先序非递归遍历：

    指针指向根节点，建立栈。循环遍历：

    ​ p非空则入栈，同时p指向左子树

    ​ p空则出栈顶元素，p指向栈顶的右子树

    ​ 先序遍历就是在入栈的时候输出

    //前序非递归遍历
void PreOrderTraverse(BTNode* root){
    
	if (root == NULL)
		return;
	BTNode* p = root;
	stack<BTNode*> s;
	while (!s.empty() || p)
	{
		if (p)
		{
			cout << setw(4) << p->data;
			s.push(p);
			p = p->lchild;
		}
		else
		{
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25

  5. 中序非递归遍历：

    ​ p非空则入栈，同时p指向左子树

    ​ p空则出栈顶元素，p指向栈顶的右子树

    ​ 中序遍历就是在栈顶出元素的时候输出

    //中序非递归遍历
void InOrderTraverse(BTreeNode* root){
    
    if (root == NULL)
		return;
	stack<BTreeNode*> s;
	BTreeNode* temp;
	BTreeNode* p = root;
	while (p || !s.empty()){
		if (p) {
			s.push(p);
			p = p->left;
		}
		else {
			temp = s.top();
			s.pop();
			cout << temp->data << "->";
			p = temp->right;
		}
	}
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21

  6. 后序非递归遍历：

    ​ 后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。这里用到一个指针pLastVisit记录上次访问过的结点,节点能被访问的前提就是:无右子树或右子树已被访问过

//后续非递归遍历
void PostOrderTraverse(BTNode* root)
{
	if (root == NULL)
		return;

	BTNode* pcur = root;
	BTNode* pLastVisit = NULL;
	//pCur:当前访问节点，pLastVisit:上次访问节点
	stack<BTNode*>s;

	//先把pCur移动到左子树最下边
	while (pcur) {
		s.push(pcur);
		pcur = pcur->left;
	}

	while (!s.empty()) {

		//走到这里，pCur都是空，并已经遍历到左子树底端
		BTNode* pcur = s.top();
		s.pop();

		//一个根节点被访问的前提是：无右子树或右子树已被访问过
		if (pcur->right == NULL || pLastVisit == pcur->right) {
			cout << pcur->data << "->";
			pLastVisit = pcur;
		}
		else {
			//走到这根结点不配出栈，重新入栈
			s.push(pcur);

			//进入右子树，且可肯定右子树一定不为空
			pcur = pcur->right;

			//访问一个新结点，就遍历到左子树左下底
			while(pcur) {
				s.push(pcur);
				pcur=pcur->left;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# 层次遍历

所谓层序遍历，就是自上而下，自左向右逐层访问的过程：

image_20231216151218976

层序遍历核心思路就是上一层带下一层，调用队列预先写好的函数辅助实现层序遍历。具体来说就是将结点自上到下逐层放入队列中，每次队列出一个节点，直到最后队列为空，遍历完成。代码如下：

void LevelOrder(BinaryTreeNode* root)
{
	Queue BTree;//层序遍历的队列
	QueueInit(&BTree);//队列初始化
	if (root)QueuePush(&BTree,root);//入队
	while (!QueueEmpty(&BTree))//队列空，循环终止
	{
		BinaryTreeNode* temp = QueueFront(&BTree);
		QueuePop(&BTree);
		cout << temp->data << " -> ";
		if (temp->left)QueuePush(&BTree, temp->left);//上一层带下一层
		if (temp->right)QueuePush(&BTree, temp->right);//上一层带下一层
	}
	cout << endl;
	QueueDestory(&BTree);//销毁队列
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 二叉树的构造

# 先序序列构造二叉数

//根据先序遍历序列创建二叉树
//根据数值和传入指针构建结点
void newNode(BinaryTreeNode*& newp,char data) {
	newp = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	newp->data = data;
	newp->left = NULL;
	newp->right = NULL;
}

//构建二叉树，传进来的字符串：AB^DF^^^CEG^^H^^^，index初始值为0
void createTree(BinaryTreeNode*& root,string prevStr,int& index) {
	if (prevStr[index] != '^'){
		newNode(root, prevStr[index]);
		index++;
		createTree(root->left, prevStr, index);
		createTree(root->right, prevStr, index);
	}
	else {
		index++;
		return;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 后续序列构建二叉树

思想将后序序列倒过来，就是根-右节点-左结点，先构建右子树，再构建左子树，string下标也是倒着来

//根据数值和传入指针构建结点
void newNode(BinaryTreeNode*& newp,char data) {
	newp = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	newp->data = data;
	newp->left = NULL;
	newp->right = NULL;
}
//构建二叉树，传进来的字符串：AB^DF^^^CEG^^H^^^,index初始值为postStr最大下标
void createTree2(BinaryTreeNode*& root, string postStr, int& index) {
	if (postStr[index] != '^') {
		newNode(root, postStr[index]);
		index--;
		createTree2(root->right, postStr, index);//先构建右子树
		createTree2(root->left, postStr, index);
	}
	else {
		index--;
		return;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 线性二叉树

# 基本定义

所谓线索二叉树就是将二叉链表中的空指针改为指向前趋和后继的线索。

对于n个结点的指针，就相应的有n+1的空指针域，线索二叉树就是将这些空指针域利用起来！

我们知道二叉树遍历次序有先序遍历，中序遍历，后序遍历，这三种遍历次序对应的输出结果分别对应先序序列，中序序列，后序序列。而线索二叉树中的前趋和后继就是指的序列中位置的前趋和后继！举例：对于如下二叉树

image_20231216151301386

其中序输出序列为：CBEGDFA，所以对于E结点其前趋为B，后继为G。

理解的前趋后继，下面谈谈如何将二叉树修改成线索二叉树！

如果结点左指针为空，就将该指针指向结点在序列中的前驱。如果结点右指针为空，就将该指针指向结点在序列中的后继。

为了弄清指针指向的时左右子树还是前驱后继，我们在结点中增加两个标志域LTag和RLag image_20231216151332135

  • 这种结点结构的构成的二叉树叫线索二叉树
  • 对应的存储结构叫做线索链表
  • 结点中指向前驱后继的指针叫做线索。

了解完线索二叉树的基本概念，来看个例子，看看其指针指向：如图（a）所示为中序线索二叉树，与其对应的中序线索链表如图（b）所示。

其中实线为指针(指向左、右子树)，虚线为线索(指向前驱和后继)。

image_20231216151406629

可以看出：线索二叉树仿照线性表的存储结构

在二叉树的线索链表上也添加一个头节点，并令其lchild域的指针指向二叉树的根节点，令其rchild域的指针指向中序遍历时访问的最后一个节点；

同时,令二叉树中序序列中第一个节点的lchild域指针和最后一个节点的rchild域指针均指向头节点。(中序序列第一个结点就是二叉树最左边的结点和最右边的结点)

这好比为二叉树建立了一个双向线索链表,既可从第一个节点起顺后继进行遍历，也可从最后一个节点起顺前驱进行遍历。

# 构造线性二叉树

构造线索二叉树的过程就是将二叉链表中的空指针改为指向前趋和后继的线索的过程。也就是说二叉树线索化就是修改空指针的过程。

由于前趋和后继只有在遍历的时候才能获得，所以按照不同的遍历次序对二叉树线索化，可以得到分别得到先序线索二叉树，中序线索二叉树，后续线索二叉树。

在讲解构造线索二叉树前，相信二叉树的遍历大家都很清楚了，访问结点的先后顺序时不变的（框架不变）。所谓先中后遍历二叉树就是将输出语句放在不同的位置，如下：

void prevOrder(BinaryTreeNode* root)
{
	if (root == NULL)
	{
		cout << "NULL->";
		return;
	}
	//cout << root->data << "->";//放在此处就是先序遍历
	prevOrder(root->left);
	//cout << root->data << "->";//放在此处就是中序遍历
	prevOrder(root->right);
	//cout << root->data << "->";//放在此处就是后序遍历
}
1
2
3
4
5
6
7
8
9
10
11
12
13

将修改空指针的操作和记录前趋节点的操作放在放在二叉树遍历的不同位置，就衍生出先序线索二叉树，中序线索二叉树，后续线索二叉树。

为了记下遍历过程中访问结点的先后关系，便于当前节点的线索化，左指针指向前前趋，右指针指向后继。设置一个指针pre始终指向刚刚访问过的结点，而p指针指向当前结点

我们每次修改空指针，都改变当前节点的左指针，改变前趋（也就是prev）的右指针。这样再遍历过后除了，除了序列的最后一个节点的后继没有修改外，其余节点均被完全线索化了。来看看个图就明白了： image_20221109161606056

记住：当前节点的左指针，改变前趋（也就是prev）的右指针

对于当前节点C而言，修改左指针，遍历一次后C成为前趋，修改前趋的右指针（C的后继），这样C的左右指针都做了修改。

# 中序线索二叉树的构建

在修改空指针前我们需要记下当前结点的前驱后继！所以设置一个指针prev始终指向刚刚访问过的结点，而p指针指向当前结点，在构造中序线索二叉树前，我们先理解pre指针和p指针时如何记录当前结点和前趋的，这样能更有利于我们理解中序二叉树的构建：

//将以p为根的二叉树线索化的部分代码
void InThreading(BTNode* p,BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {
		InThreading(p->left,prev);
		prev = p;
		InThreading(p->right,prev);
	}
}
1
2
3
4
5
6
7
8
9
10
11

可以看到，和遍历输出二叉链表的代码实现很像！p非空？那就递归左子树线索化，记录根结点prev = p;，再右子树线索化！

prev的初始值指向线索二叉树的头节点Thrt，对于中序第一个结点，它的前趋就是二叉搜索树的头节点

上面代码，每一层递归都记录下的当前结点和上一个结点：每一层递归中当前结点为p，当前结点的前趋为prev。下一步接着加入修改空指针的操作：

//将以p为根的二叉树线索化
void InThreading(BTNode* p, BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {

		InThreading(p->left, prev);

		if (!p->left) {
			p->LTag = 1;//标记p->left为左线索
			p->left = prev;//指向前趋
		}
		else p->LTag = 0;//标记p->left指向左子树

		if (!prev->right) {
			prev->RTag = 1;//标记p->right为右线索
			prev->right = p;//指向后继
		}
		else prev->RTag = 0;//标记p->right指向右子树

		prev = p;

		InThreading(p->right, prev);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

上面说过，我们每次修改空指针，都改变当前节点的左指针，改变前趋（也就是prev）的右指针。这样再遍历过后除了，除了序列的最后一个节点的后继没有修改外，其余节点均被完全线索化了。所以真正的代码实现我们还需要对序列最后一个节点的后继线索化！，下面是完整的线索化二叉树实现：

//将以p为根的二叉树线索化
void InThreading(BTNode* p, BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {

		InThreading(p->left, prev);

		if (!p->left) {
			p->LTag = 1;//标记p->left为左线索
			p->left = prev;//指向前趋
		}
		else p->LTag = 0;//标记p->left指向左子树

		if (!prev->right) {
			prev->RTag = 1;//标记p->right为右线索
			prev->right = p;//指向后继
		}
		else prev->RTag = 0;//标记p->right指向右子树

		prev = p;

		InThreading(p->right, prev);
	}
}

//中序遍历二叉树T，并将线索化，Thrt指向头节点（线索二叉树的头节点）
void InOrderThreading(BTNode*& Thrt, BTNode* root) {

	Thrt = new BTNode;//建立头节点
	Thrt->LTag = 0;//头节点有左孩子，若树非空，左孩子为树根。若树空，左孩子指向其自己。
	Thrt->RTag = 1;//头节点右孩子指向序列最后一个节点
	Thrt->right = Thrt;//右孩子初始化指向自己

	if (!root)Thrt->left = Thrt;
	else {
		Thrt->left = root;
		BTNode* prev = Thrt;//前趋节点，初始化指向头节点
		InThreading(root, prev);

		prev->right = Thrt;//递归出来prev指向序列最后一个节点,对最后一个节点序列化
		prev->RTag = 1;

		Thrt->right = prev;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# 先序线索二叉树的构建

还是一样，在修改空指针前我们需要记下当前结点的前驱后继！所以设置一个指针prev始终指向刚刚访问过的结点，而p指针指向当前结点，在构造先序线索二叉树前，我们先理解pre指针和p指针时如何记录当前结点和前趋的，这样能更有利于我们理解先二叉树的构建：

//将以p为根的二叉树线索化
void InThreading(BTNode* p, BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {
		prev = p;

		InThreading(pleft, prev);
		InThreading(p->right, prev);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

可以发现和中序相比就是将prev=p移动的了位置

下面就是修改空指针了，此处有点小修改，因为先序线索二叉树可能需要再访问左右子树前，修改左右指针，这直接影响我们原本遍历二叉树所以我们，先将左指针存储起来，再修改左指针：

//将以p为根的二叉树线索化
void InThreading(BTNode* p, BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {
		BTNode* pleft = p->left;//先存储左指针，防止下面修改左指针映像二叉树遍历！

		if (!p->left) {
			p->LTag = 1;//标记p->left为左线索
			p->left = prev;//指向前趋
		}
		else p->LTag = 0;//标记p->left指向左子树

		if (!prev->right) {
			prev->RTag = 1;//标记p->right为右线索
			prev->right = p;//指向后继
		}
		else prev->RTag = 0;//标记p->right指向右子树

		prev = p;

		InThreading(pleft, prev);
		InThreading(p->right, prev);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

和中序一样需要对序列最后一个节点序列化，完整实现如下：

//将以p为根的二叉树线索化
void InThreading(BTNode* p, BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {
		BTNode* pleft = p->left;//用于临时存储当前节点的left，以放NULL修改后死循环！

		if (!p->left) {
			p->LTag = 1;//标记p->left为左线索
			p->left = prev;//指向前趋
		}
		else p->LTag = 0;//标记p->left指向左子树

		if (!prev->right) {
			prev->RTag = 1;//标记p->right为右线索
			prev->right = p;//指向后继
		}
		else prev->RTag = 0;//标记p->right指向右子树

		prev = p;

		InThreading(pleft, prev);
		InThreading(p->right, prev);
	}
}

//中序遍历二叉树T，并将线索化，Thrt指向头节点（线索二叉树的头节点）
void InOrderThreading(BTNode*& Thrt, BTNode* root) {

	Thrt = new BTNode;//建立头节点
	Thrt->LTag = 0;//头节点有左孩子，若树非空，左孩子为树根。若树空，左孩子指向其自己。
	Thrt->RTag = 1;//头节点右孩子指向序列最后一个节点
	Thrt->right = Thrt;//右孩子初始化指向自己

	if (!root)Thrt->left = Thrt;
	else {
		Thrt->left = root;
		BTNode* prev = Thrt;//前趋节点，初始化指向头节点
		InThreading(root, prev);

		prev->right = Thrt;//递归出来prev指向序列最后一个节点,对最后一个节点序列化
		prev->RTag = 1;

		Thrt->right = prev;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

# 后续线索二叉树的构建

经过上面两个例子，后续线索二叉树就是将修改空指针和记录位置下移，但不同的是后续序列最后一个节点是不一定要序列化的因此还要判断，再序列化，代码实现

//将以p为根的二叉树线索化
void InThreading(BTNode* p, BTNode*& prev) {
	//if (!root)return;//可以写但很多余

	//prev是全局定义好的变量，用于指向刚刚访问过的结点
	if (p) {

		InThreading(p->left, prev);

		InThreading(p->right, prev);

		if (!p->left) {
			p->LTag = 1;//标记p->left为左线索
			p->left = prev;//指向前趋
		}
		else p->LTag = 0;//标记p->left指向左子树

		if (!prev->right) {
			prev->RTag = 1;//标记p->right为右线索
			prev->right = p;//指向后继
		}
		else prev->RTag = 0;//标记p->right指向右子树

		prev = p;
	}
}

//中序遍历二叉树T，并将线索化，Thrt指向头节点（线索二叉树的头节点）
void InOrderThreading(BTNode*& Thrt, BTNode* root) {

	Thrt = new BTNode;//建立头节点
	Thrt->LTag = 0;//头节点有左孩子，若树非空，左孩子为树根。若树空，左孩子指向其自己。
	Thrt->RTag = 1;//头节点右孩子指向序列最后一个节点
	Thrt->right = Thrt;//右孩子初始化指向自己

	if (!root)Thrt->left = Thrt;
	else {
		Thrt->left = root;
		BTNode* prev = Thrt;//前趋节点，初始化指向头节点
		InThreading(root, prev);

		if (!prev->right) {
			prev->right = Thrt;//递归出来prev指向序列最后一个节点,对最后一个节点序列化
			prev->RTag = 1;
		}
        else {
			prev->RTag = 0;
		}

		Thrt->right = prev;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 遍历线索二叉树

我们可以直接递归遍历，根据标记判断当前节点是否有左右子树。但我们知道递归遍历二叉树时间复杂度和空间复杂度都是O(N)。但这样丝毫没有发挥线索二叉树的优势，线索二叉树的非递归遍历才是一大亮点！

这里以中序线索二叉树为例，在理解中序线索二叉树非递归遍历前，先要清楚线索二叉树是如何非递归遍历的算法思路：

  1. 开始p指针指向A
  2. 然后循环找到当前子树最左下角的节点M，并输出！
  3. M通过右索引访问输出N（此时循环结束，N没有右索引）
  4. 循环结束就将指针指向该节点的右孩子（也就是新的根节点了）

下图红线是中序线索二叉树遍历输出过程，每一个红线下方的节点都是当前子树的最左下节点。把握住子树的最左下节是中序遍历的头，右线索是直接后继。

image_20221109193911617

代码实现：

void InOrderTraverse(BTNode* T)
{
	BTNode* p = T->left;//线索二叉树头节点的左指针指向实际二叉树的头
	while (p != T)
	{
        //1. 循环找到当前子树的左下角，开始以四字节单元访问！
		while (p->LTag == 0)
			p = p->left;
		cout << p->data;
        
        //2. 通过右索引访问直接后继
		while (p->RTag == 1 && p->right != T)
		{
			p = p->right;
			cout << p->data;
		}
        
        //3. 四字节单元访问完，指向右孩子，寻找下一个四字节！
		p = p->right;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 哈夫曼树

# 基本概念

  • 结点间路径：从一个结点到另一个结点所经历的结点和分支序列。
  • 结点的路径长度：从根节点到该结点的路径上分支的数目。
  • 结点的权：在实际应用中，人们往往会给树中的每一个结点赋予一个具有某种实际意义的数值，这个数值被称为该结点的权值。
  • 结点的带权路径长度：该结点的路径长度与该结点的权值的乘积。
  • 树的带权路径长度：树中所有叶结点的带权路径长度之和。
image_20231210201214724

# 构造哈夫曼树

给定n个权值分别为w1, w2…wn的结点，构造哈夫曼树的算法描述如下：

  1. 首先将这n个结点分别视作n棵仅含一个结点的二叉树，构成森林F。

  2. 在森林中选取两棵==根结点权值最小的树==作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。

  3. 重复选树的过程，知道森林只剩下一棵树

    下面是构建哈夫曼树的过程：

    image_20231210201512060

# 哈夫曼编码

  • 可变长度编码，对不同字符采用不等长的二进制位表示。
  • 前缀编码：没有一个编码时另一个编码的前缀

用哈夫曼树得到的编码方案叫哈夫曼编码，并且哈夫曼编码时前缀编码

具体：对不同的字符赋予权值，就得到了带权的结点，相应构建哈夫曼树。每一个字符对应哈夫曼树的叶子结点，规定查找路径向左为编码1，向右为编码0。该叶子的查找路径就对应了字符的唯一编码。

下面时哈夫曼编码的案例：可以看到同一权值的结点能构造的哈夫曼树不唯一，对应的哈夫曼编码也是不唯一的！

img

对使用频率高的字符赋予较高权值，对应哈夫曼树种权值高的结点查找路径更短，相应的编码也更短，从而实现文件压缩！

  • n个权值，组成哈夫曼树节点个数：2n-1

  • 哈夫曼结点类

    #include <iostream>

class HuffmanNode {
public:
    int weight; // 权值
    bool flag; // 节点是否加入哈夫曼树的标志
    HuffmanNode* parent, * lchild, * rchild; // 父节点及左右孩子节点

    // 构造一个空节点
    HuffmanNode() : weight(0), flag(false), parent(nullptr), lchild(nullptr), rchild(nullptr) {}

    // 构造一个具有权值的节点
    HuffmanNode(int weight) : weight(weight), flag(false), parent(nullptr), lchild(nullptr), rchild(nullptr) {}
};
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

  • 哈夫曼编码类

#include <iostream>
#include <vector>

class HuffmanNode {
public:
    int weight; // 权值
    bool flag; // 节点是否加入哈夫曼树的标志
    HuffmanNode* parent, * lchild, * rchild; // 父节点及左右孩子节点

    // 构造一个空节点
    HuffmanNode() : weight(0), flag(false), parent(nullptr), lchild(nullptr), rchild(nullptr) {}

    // 构造一个具有权值的节点
    HuffmanNode(int weight) : weight(weight), flag(false), parent(nullptr), lchild(nullptr), rchild(nullptr) {}
};

class HuffmanTree {
public:
    // 求哈夫曼编码的算法，w存放n个字符的权值(均>0)
    std::vector<std::vector<int>> huffmanCoding(const std::vector<int>& W) {
        int n = W.size();  // 字符个数
        int m = 2*n -1;   //哈夫曼树的节点数
        // 构造n个具有权值的节点
        HuffmanNode* HN = new HuffmanNode[m];
        int i = 0;
        for (; i<n ; i++) {
            HN[i] = HuffmanNode(W[i]);
        }
        // 创建哈夫曼树
        for (i = n;  i<m ; i++) {
            // 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2
            HuffmanNode* min1 = selectMin(HN,i-1);
            min1->flag = true;
            HuffmanNode* min2 = selectMin(HN,i-1);
            min2->flag = true;
            // 构造 min1和min2的父节点，并修改父节点的权值
            HN[i] = new HuffmanNode();
            min1->parent=HN[i];
            min2->parent=HN[i];
            HN[i]->lchild = min1;
            HN[i]->rchild = min2;
            HN[i]->weight = min1->weight+min2->weight;
        }
        //  从叶子到根 逆向求每个字符的哈夫曼编码
        std::vector<std::vector<int>> HuffCode(n, std::vector<int>(n)); // 分配n个字符编码存储空间
        for (int j =0;j<n;j++){
            // 编码的开始位置，初始化为数组的结尾
            int start = n-1;
            // 从叶子节点到根，逆向求编码
            for(HuffmanNode* c = &HN[j], p=c->parent;p!=nullptr;c=p,p=p->parent){
                if(p->lchild == c){
                    HuffCode[j][start--]=0;
                }else{
                    HuffCode[j][start--]=1;
                }
            }
            // 编码的开始标志为-1，编码是-1之后的01序列
            HuffCode[j][start] = -1;

        }

        return HuffCode;
    }

private:
    // 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2
    HuffmanNode* selectMin(HuffmanNode* HN, int end) {
        // 求 不在哈夫曼树中， weight最小值的那个节点
        HuffmanNode* min = &HN[end];
        for (int i = 0; i < end; i++) {
            HuffmanNode* h = &HN[i];
            // 不在哈夫曼树中， weight最小值
            if(!h->flag && h->weight<min->weight){
                min = h;
            }
        }
        return min;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
  • 哈夫曼编码会用类似如下格式进行存储

​ img

  • 测试类

    #include <iostream>
#include <vector>

class HuffmanTree {
public:
    std::vector<std::vector<int>> huffmanCoding(const std::vector<int>& W) {
        // 实现哈夫曼编码的代码...
    }
};

int main() {
    // 一组权值
    std::vector<int> W = {6,30,8,9,15,24,4,12};
    // 创建哈夫曼树
    HuffmanTree tree;
    // 求哈夫曼编码
    std::vector<std::vector<int>> HN = tree.huffmanCoding(W);
    // 打印编码
    std::cout << "哈夫曼编码是：\n";
    for (size_t i = 0; i < HN.size(); i++) {
        std::cout << W[i] << " ";
        for (size_t j = 0; j < HN[i].size(); j++) {
            if (HN[i][j] == -1) {
                for (size_t k = j + 1; k < HN[i].size(); k++) {
                    std::cout << HN[i][k];
                }
                break;
            }
        }
        std::cout << "\n";
    }

    return 0;
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34

# 并查集

# 定义

并查集是一种用来管理元素分组情况的数据结构。

可以高效进行如下操作

  • 查询元素a和元素b 是否属于同一组。

  • 合并元素a和元素b 所在的组

    分组和对应的例子

# 并查集的结构

并查集是树形结构。不过，不是二叉树。

每个元素对应一个节点，每个组对应一颗树。

在并查集中，哪个节点是哪个节点的父亲以及树的形状等信息不用关注，整体是树形结构才最重要

# 1. 初始化

初始化

# 2. 合并

和下面图一样，从一个组的根向另一个组的跟连边，将两棵树变成 一颗树，也就是两个组变成一个组

image_20231210203640735

# 3. 查询

为了查询两个节点是否同一组，只要沿着树向上走，查询根节点是否相同，根节点相同时同一组，否则不同组。如上图中 （2）（5）的根是 （1），而（7）的根是（6） 所以（2）和（5）是同一组，但是（2）和（7）不是同一组。

代码实现

#include <vector>

class UnionFind {
public:
    // 构造函数
    UnionFind(std::vector<int>& nums) {
        par.resize(nums.size());
        rank.resize(nums.size());
        
        for (size_t i = 0; i < nums.size(); i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    // 查询树的根
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return find(par[x]);
        }
    }

    // 查询x和y是否为同一集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并x和y所属集合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return;
        }

        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }

private:
    std::vector<int> par;  // 父节点数组
    std::vector<int> rank; // 节点的秩
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
Last Updated: 12/18/2023, 11:23:06 PM

七、图