数据结构学习笔记--树与二叉树

Published on May 27, 2024 with 0 views and 0 comments

# 待分类

一、基本概念

1.1 定义

树时n(n>=0)个节点的有限集。n=0时称为空树。

非空树具有以下特性：

有且仅有一个称为根的节点；
当n>1时，其余节点可分为m(m>0)个互不相交的有限集T₁,T₂...T_n，其中每个集合本身又是一棵树，称为根的子树。

树作为一种逻辑结构，具有以下特点：

树的根节点没有前驱，除根节点以外的其他节点有且只有一个前驱；
树中所有节点可以有0或者多个后继；
n个节点的树中有n-1条边。

1.2 基本术语

从节点A->K的唯一路径上的任意节点，称为K的祖先，B为K的祖先，K为B的子孙，E是K的双亲，K为E的孩子。有相同双亲的节点称为兄弟，K和L是兄弟
树中一个节点的孩子个数称为该节点的度，树中节点最大的度数，称为树的度。如节点B度为2，节点D度为3
度大于0的节点称为分支节点，度为0的节点称为叶子节点
节点的深度、高度和层次
1. 节点的层次从根节点开始定义，逐级向下递增
2. 双亲在同一层的节点称为堂兄弟，如K、L、M互为堂兄弟
3. 节点的深度是从根节点开始自顶向下累加的
4. 节点的高度是从叶子节点开始自底向上累加的
5. 树的高度是树中节点的最大层数
路径和路径长度
1. 树中两个节点之间的路径是由这两个节点之间所经过的节点序列构成的
2. 路径的长度是路径上所经过的边的个数
森林
1. 森林是m(m>=0)棵互不相交的树的集合
2. 树的根节点删去就成了森林，m棵独立的树加上一个根节点，森林就变成了树

1.3 树的性质

树具有以下性质：

树中的节点数量等于所有节点的度数+1
度为m的树中第i层上至多有m^i-1个节点(i>=1)
高度为h的m叉树至多有(m^h-1)/(m-1)个节点
具有n个节点的m叉树的最小高度为log_m^(n(m-1)+1)

二、二叉树的概念

2.1 二叉树的定义及其特性

2.1.1 二叉树的定义

二叉树是每个节点至多有两棵子树，树中不存在度>2的节点，二叉树是n(n>=0)个节点的有限集合:

n=0称为空树
由一个根节点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树

二叉树与度为2的树的区别：

度为2的树至少有3个节点，二叉树可以为空
二叉树节点的左右次序是确定的，而度为2的有序树孩子的左右次序是相对于另一个孩子而言的

2.1.2 几个特殊的二叉树

满二叉树
- 一颗高度为h，且含有2^h-1个节点的二叉树称为满二叉树，树中每层都含有最多的节点，除叶子节点外每个节点度数均为2
- 对满二叉树按层序编号：约定从根节点起，自上而下，自左向右，这样每个节点有一个编号，对编号为i的节点，双亲为i/2,左孩子为2i，右孩子为2i+1
完全二叉树
- 高度为h，有n个节点的二叉树，且仅当每个节点都与高度为h的满二叉树中编号为i-n的节点一一对应，称为完全二叉树
- 若i<=[i/2]，则节点i为分支节点，否则为叶子节点
- 叶子节点只可能在层次最大的两层上出现，对于最大层次中的叶子节点，都依次排列在该层最左边的位置上
- 若有度为1的节点，有且只能有一个，且该节点无孩子节点
- 按层序编号后，一旦出现编号为i的节点是叶子节点或者只有左孩子，则编号大于i的节点均为叶子节点
- 若n为奇数，则每个分支节点都有左孩子和有孩子；若n为偶数，则编号最大的分支节点(编号为n/2)只有左孩子
二叉排序树
- 左子树所有节点的关键字都小于根节点关键字
- 右子树所有节点的关键字都大于根节点关键字
- 左子树和右子树又各是一颗二叉排序树
平衡二叉树
- 树上任意节点的左子树和右子树深度只差不超过1

2.1.3 二叉树的性质

非空二叉树上的叶子节点数等于度为2的节点树加1，n⁰=n²+1，其实就是二叉树中节点数=边数+1
非空二叉树上第k层，至多有2^k-1个节点
高度为h的二叉树至多有2^h-1个节点
对完全二叉树按从上到下，从左到右的顺序依次编号1,2...,n，具有以下关系
- 当i>1，i为偶数，双亲为i/2，i为奇数，双亲为(i-1)/2且他是双亲的右孩子
- 当2i<=n时，节点i的左孩子编号为2i，否则无左孩子
- 当2i+1<=n时，节点的右孩子编号为2i+1，否则无右孩子
- 节点i所在层次为log₂ⁱ+1
具有n个节点的完全二叉树的高度为log₂⁽ⁿ⁺¹⁾或log₂ⁿ+1

2.2 二叉树的存储结构

2.2.1 顺序存储

把二叉树的所有节点，按照一定的次序自上而下，自左至右依次存储到一片连续的存储单元中，就是将编号为i的节点存储在一维数组中，为了与节点编号对应，数组第一个位置不存储数据，如果二叉树只有左孩子或右孩子，则跳过的孩子在数组中用NULL或其他标识符表示

2.2.2 链式存储

链式存储结构描述如下，每个节点又数据域和两个指针域，分别指向他的左孩子和右孩子

typedef int dataType;
typedef struct Node {
	dataType data;
	struct Node* lChild, * rChild;
}BitTree;

含有n个节点的二叉链表中，有n+1个空链域

三、二叉树的遍历和线索二叉树

3.1 二叉树的遍历

沿某条路径访问二叉树的每个节点，使得每个节点均被访问一次，设根节点为N，左子树为L，右子树为R，常见的遍历顺序有先序(NLR)、中序(LNR)、后序(LRN)

现有一颗二叉树如下

3.1.1 递归遍历

3.1.1.1 先序遍历

先序遍历操作过程如下：

访问根节点
遍历左子树
遍历右子树

void PreOrder(BitTree* node) {
	if (node != NULL) {
		printf("%c", node->data);
		PreOrder(node->lChild);
		PreOrder(node->rChild);
	}
}

在这里插入图片描述

3.1.1.2 中序遍历

中序遍历操作过程如下：

遍历左子树
访问根节点
遍历右子树

// 中序遍历
void InOrder(BitTree* node) {
	if (node != NULL) {
		InOrder(node->lChild);
		printf("%c", node->data);
		InOrder(node->rChild);
	}
}

在这里插入图片描述

3.1.1.3 后序遍历

后序遍历操作过程如下：

遍历左子树
遍历右子树
访问根节点

void PostOrder(BitTree* node) {
	if (node != NULL) {
		PostOrder(node->lChild);
		PostOrder(node->rChild);
		printf("%c", node->data);
	}
}

在这里插入图片描述

3.1.1.4 递归遍历代码

#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct Node {
	dataType data;
	struct Node* lChild, * rChild;
}BitTree,BitNode;

// 前序遍历
void PreOrder(BitTree* node) {
	if (node != NULL) {
		printf("%c", node->data);
		PreOrder(node->lChild);
		PreOrder(node->rChild);
	}
}
// 中序遍历
void InOrder(BitTree* node) {
	if (node != NULL) {
		InOrder(node->lChild);
		printf("%c", node->data);
		InOrder(node->rChild);
	}
}
// 后序遍历
void PostOrder(BitTree* node) {
	if (node != NULL) {
		PostOrder(node->lChild);
		PostOrder(node->rChild);
		printf("%c", node->data);
	}
}

BitNode *initNode(dataType data) {
	BitNode *node = (BitNode*)malloc(sizeof(BitNode));
	if (node == NULL) {
		printf("内存申请失败");
		return NULL;
	}
	node->data = data;
	node->lChild = NULL;
	node->rChild = NULL;
	return node;
}

int main() {
	BitNode *A = initNode('A');
	BitNode *B = initNode('B');
	BitNode *C = initNode('C');
	BitNode *D = initNode('D');
	BitNode *E = initNode('E');
	BitNode *F = initNode('F');
	BitNode *G = initNode('G');
	BitNode *H = initNode('H');
	BitNode* I = initNode('I');

	A->lChild = B;
	A->rChild = C;
	B->lChild = D;
	C->lChild = E;
	C->rChild = F;
	D->lChild = G;
	D->rChild = H;
	E->rChild = I;

	printf("前序遍历-->");
	PreOrder(A);
	printf("\n中序遍历-->");
	InOrder(A);
	printf("\n后序遍历-->");
	PostOrder(A);
}

3.1.2 非递归遍历

使用栈来实现非递归遍历

3.1.2.1 先序遍历

先序遍历先遍历根节点在遍历左右子树，因此直接使用一个栈，先将根节点入栈，然后根节点出栈，获取他的左右节点，在先将右节点入栈，然后将左节点入栈，依次出栈即可

void PreOrder(BitTree* root) {
	if (root == NULL) {
		return;
	}
	BitTree* stack[100];
	int top = -1;
	stack[++top] = root;

	while (top != -1) {
		BitNode* currentNode = stack[top--];
		printf("%c", currentNode->data);

		// 先把又节点入栈，在入栈左节点，出的时候，就会先出左节点了
		if (currentNode->rChild != NULL) {
			stack[++top] = currentNode->rChild;
		}
		if (currentNode->lChild != NULL) {
			stack[++top] = currentNode->lChild;
		}

	}
}

3.1.2.2 中序遍历

我们可以先一直遍历左子树，将遍历过的节点都压入栈中，然后再依次出栈并访问，同时遍历它们的右子树。这样，我们就能得到正确的中序遍历顺序

void InOrder(BitTree* root) {
	if (root == NULL) {
		return;
	}
	BitNode* stack[100];
	int top = -1;
	BitNode* curr = root;
	while (curr != NULL || top != -1) {
		// 先一直遍历左子树并压入栈中
		while (curr != NULL) {
			stack[++top] = curr;
			curr = curr->lChild;
		}
		// 弹出栈顶元素并访问
		curr = stack[top--];
		printf("%c",curr->data);

		// 遍历右子树
		curr = curr->rChild;
	}
}

3.1.2.3 后续遍历

后续遍历使用两个栈实现，一个栈用来遍历树，第二个栈用来存储后续结果，然后再出栈，这里需要注意，因为我们最重出栈的结果是先出左孩子，右孩子，最后才算是根节点，所以再第二个栈中入栈顺序就要先入根节点，后入右孩子，再入左孩子，为了实现这个效果再栈一中就要先入根节点，然后入左孩子，右孩子

void PostOrder(BitTree* root) {
	if (root == NULL) {
		return;
	}
	BitTree* stack1[100], * stack2[100];
	int top1 = -1, top2 = -1;
	stack1[++top1] = root;
	while (top1 != -1) {
		BitNode* currentNode = stack1[top1--];
		stack2[++top2] = currentNode;
		if (currentNode->lChild != NULL) {
			stack1[++top1] = currentNode->lChild;
		}
		if (currentNode->rChild != NULL) {
			stack1[++top1] = currentNode->rChild;
		}
	}
	while (top2 != -1) {
		printf("%c", stack2[top2--]->data);
	}
}

3.1.2.3 非递归遍历代码

#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct Node {
	dataType data;
	struct Node* lChild, * rChild;
}BitTree, BitNode;

// 前序遍历
void PreOrder(BitTree* root) {
	if (root == NULL) {
		return;
	}
	BitTree* stack[100];
	int top = -1;
	stack[++top] = root;

	while (top != -1) {
		BitNode* currentNode = stack[top--];
		printf("%c", currentNode->data);

		// 先把又节点入栈，在入栈左节点，出的时候，就会先出左节点了
		if (currentNode->rChild != NULL) {
			stack[++top] = currentNode->rChild;
		}
		if (currentNode->lChild != NULL) {
			stack[++top] = currentNode->lChild;
		}

	}
}
// 中序遍历
void InOrder(BitTree* root) {
	if (root == NULL) {
		return;
	}
	BitNode* stack[100];
	int top = -1;
	BitNode* curr = root;
	while (curr != NULL || top != -1) {
		// 先一直遍历左子树并压入栈中
		while (curr != NULL) {
			stack[++top] = curr;
			curr = curr->lChild;
		}
		// 弹出栈顶元素并访问
		curr = stack[top--];
		printf("%c",curr->data);

		// 遍历右子树
		curr = curr->rChild;
	}
}
// 后序遍历
void PostOrder(BitTree* root) {
	if (root == NULL) {
		return;
	}
	BitTree* stack1[100], * stack2[100];
	int top1 = -1, top2 = -1;
	stack1[++top1] = root;
	while (top1 != -1) {
		BitNode* currentNode = stack1[top1--];
		stack2[++top2] = currentNode;
		if (currentNode->lChild != NULL) {
			stack1[++top1] = currentNode->lChild;
		}
		if (currentNode->rChild != NULL) {
			stack1[++top1] = currentNode->rChild;
		}
	}
	while (top2 != -1) {
		printf("%c", stack2[top2--]->data);
	}
}

BitNode* initNode(dataType data) {
	BitNode* node = (BitNode*)malloc(sizeof(BitNode));
	if (node == NULL) {
		printf("内存申请失败");
		return NULL;
	}
	node->data = data;
	node->lChild = NULL;
	node->rChild = NULL;
	return node;
}

int main() {
	BitNode* A = initNode('A');
	BitNode* B = initNode('B');
	BitNode* C = initNode('C');
	BitNode* D = initNode('D');
	BitNode* E = initNode('E');
	BitNode* F = initNode('F');
	BitNode* G = initNode('G');
	BitNode* H = initNode('H');
	BitNode* I = initNode('I');

	A->lChild = B;
	A->rChild = C;
	B->lChild = D;
	C->lChild = E;
	C->rChild = F;
	D->lChild = G;
	D->rChild = H;
	E->rChild = I;

	printf("前序遍历-->");
	PreOrder(A);
	printf("\n中序遍历-->");
	InOrder(A);
	printf("\n后序遍历-->");
	PostOrder(A);
}

3.1.3 层次遍历

层次遍历就是按照从上至下，从左至右依次访问节点，可以使用队列实现

#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct Node {
	dataType data;
	struct Node* lChild, * rChild;
}BitTree, BitNode;

// 队列节点
typedef struct QueueNode {
	BitNode* data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue {
	QueueNode* front;
	QueueNode* rear;
}Queue;

void initQueue(Queue* q) {
	q->front = q->rear = NULL;
}

// 从尾部入队
void push(Queue* q, BitNode* data) {
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL) {
		printf("内存申请失败\n");
		return;
	}
	newNode->data = data;
	newNode->next = NULL;

	if (q->front == NULL) {
		q->front = q->rear = newNode;
	}
	else {
		q->rear->next = newNode;
		q->rear = newNode;
	}
}

BitNode* pop(Queue* q) {
	if (q->front == NULL) {
		return NULL;
	}
	QueueNode* temp = q->front;
	BitNode* data = temp->data;
	q->front = q->front->next;
	if (q->front == NULL) {
		q->rear = NULL;
	}
	free(temp);
	return data;
}
printBitTree(BitNode* root) {
	if (root == NULL) {
		return;
	}
	Queue q;
	initQueue(&q);

	push(&q, root);
	while (q.front != NULL) {
		BitNode* curr = pop(&q);
		printf("%c ", curr->data);
		// 左子节点入队
		if (curr->lChild != NULL) {
			push(&q, curr->lChild);
		}

		// 右子节点入队
		if (curr->rChild!= NULL) {
			push(&q, curr->rChild);
		}
	}
}

BitNode* initNode(dataType data) {
	BitNode* node = (BitNode*)malloc(sizeof(BitNode));
	if (node == NULL) {
		printf("内存申请失败");
		return NULL;
	}
	node->data = data;
	node->lChild = NULL;
	node->rChild = NULL;
	return node;
}

int main() {
	BitNode* A = initNode('A');
	BitNode* B = initNode('B');
	BitNode* C = initNode('C');
	BitNode* D = initNode('D');
	BitNode* E = initNode('E');
	BitNode* F = initNode('F');
	BitNode* G = initNode('G');
	BitNode* H = initNode('H');
	BitNode* I = initNode('I');

	A->lChild = B;
	A->rChild = C;
	B->lChild = D;
	C->lChild = E;
	C->rChild = F;
	D->lChild = G;
	D->rChild = H;
	E->rChild = I;
	printf("层次遍历-->");
	printBitTree(A);
}

3.2 线索二叉树

二叉树中的节点指针域只存储了自己的两个孩子节点，从任意节点出发只能找到该节点的左右孩子节点，一般情况下无法直接找到该节点再某种遍历序列中的前驱和后继结点。而n个节点的二叉树中，共有n+1个空链域，我们可以使用这两个空链域来存储该节点的前驱和后继，为了区分左右孩子，还需要再加上两个标识符ltag和rtag

ltag和rtag的作用：标明指针是否用作线索标志，这里的前驱后继可以通过指定的遍历序列得到(前中后序遍历)

此时数据结构为

typedef char dataType;
typedef struct ThreadNode {
	dataType data;
	struct TBTNode* lChild, * rChild;
	int lTag, rTag;
}ThreadTree, ThreadNode;

这就是一个线索链表，指向结点前驱、后继的指针称为线索，加上线索的二叉树称为线索二叉树

3.2.1 二叉树线索化

将二叉树变为线索二叉树的过程称为线索化，按照某种次序将二叉树线索化，只要按照该次序遍历二叉树，再遍历过程中用线索取代空指针

3.2.1.1 前序线索二叉树

它首先找到最左边的节点（即前序遍历中的第一个节点），然后访问它。如果当前节点有后继节点（即右指针指向的是一个线程化的后继），则直接转到后继节点；否则，它返回到右子树的最左边节点并继续遍历

#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct ThreadNode {
	dataType data;
	struct ThreadNode* lChild, * rChild;
	int lTag, rTag;
}ThreadTree, ThreadNode;

ThreadNode* initNode(dataType data) {
	ThreadNode* node = (ThreadNode*)malloc(sizeof(ThreadNode));
	if (node == NULL) {
		printf("内存申请失败");
		return NULL;
	}
	node->data = data;
	node->lChild = NULL;
	node->rChild = NULL;
	node->lTag = 0;
	node->rTag = 0;
	return node;
}
void preOrderThreading(ThreadNode* root, ThreadNode** pre) {
	if (root == NULL) {
		return;
	}
	// 当前节点左孩子为空，则上一个遍历的节点是他的前驱
	if (root->lChild == NULL) {
		root->lTag = 1;
		root->lChild = *pre;
	}
	// 若上一个节点不为空，且上一个节点没有右孩子，则当前节点是上一个节点的后继
	if (*pre != NULL && (*pre)->rChild == NULL) {
		(*pre)->rTag = 1;
		(*pre)->rChild = root;
	}
	*pre = root;
	if (root->lTag == 0) {
		preOrderThreading(root->lChild, pre);
	}
	if (root->rTag == 0) {
		preOrderThreading(root->rChild, pre);
	}
}
void printPreorderThreaded(ThreadNode* root) {
	ThreadNode* p = root;
	while (p != NULL) {
		// 打印当前节点值
		printf("%c", p->data);

		// 如果右指针是线索，则直接移动到后继
		if (p->rTag == 1) {
			p = p->rChild;
		}
		else {
			// 否则，移动到左子树（即使左指针是线索，也是下一个要打印的节点）
			if (p->lTag == 0) {
				p = p->lChild;
			}
			else {
				p = p->rChild;
			}
		}
	}
}
int main() {
	ThreadNode* A = initNode('A');
	ThreadNode* B = initNode('B');
	ThreadNode* C = initNode('C');
	ThreadNode* D = initNode('D');
	ThreadNode* E = initNode('E');
	ThreadNode* F = initNode('F');
	ThreadNode* G = initNode('G');
	ThreadNode* H = initNode('H');
	ThreadNode* I = initNode('I');
	A->lChild = B;
	A->rChild = C;
	B->lChild = D;
	C->lChild = E;
	C->rChild = F;
	D->lChild = G;
	D->rChild = H;
	E->rChild = I;
	ThreadNode* pre = NULL;
	preOrderThreading(A, &pre);
	printPreorderThreaded(A);
}

3.2.1.2 中序线索二叉树

#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct ThreadNode {
	dataType data;
	struct ThreadNode* lChild, * rChild;
	int lTag, rTag;
}ThreadTree, ThreadNode;

ThreadNode* initNode(dataType data) {
	ThreadNode* node = (ThreadNode*)malloc(sizeof(ThreadNode));
	if (node == NULL) {
		printf("内存申请失败");
		return NULL;
	}
	node->data = data;
	node->lChild = NULL;
	node->rChild = NULL;
	node->lTag = 0;
	node->rTag = 0;
	return node;
}
// 全局变量，指向刚刚访问过的结点
ThreadNode* pre = NULL;
void inOrderThreading(ThreadNode* root) {
	if (root == NULL) {
		return;
	}
	// 递归左子树线索化
	inOrderThreading(root->lChild);
	// 节点无左孩子
	if (root->lChild == NULL) {
		root->lTag = 1;
		root->lChild = pre;
	}
	// 前驱没有右孩子
	if (pre != NULL && pre->rChild == NULL) {
		pre->rTag = 1;
		pre->rChild = root;
	}
	pre = root;
	inOrderThreading(root->rChild);

}
// 中序遍历二叉线索树
void printInOrderThreaded(ThreadNode* root) {
	ThreadNode* p = root;
	while (p) {
		while (p->lTag == 0) // 移动到最左边的结点
			p = p->lChild;
		printf("%c ", p->data); // 打印这个结点
		while (p->rTag == 1 && p->rChild) { // 访问后继
			p = p->rChild;
			printf("%c ", p->data); // 打印后继结点
		}
		p = p->rChild; // 移动到右孩子
	}
}
int main() {
	ThreadNode* A = initNode('A');
	ThreadNode* B = initNode('B');
	ThreadNode* C = initNode('C');
	ThreadNode* D = initNode('D');
	ThreadNode* E = initNode('E');
	ThreadNode* F = initNode('F');
	ThreadNode* G = initNode('G');
	ThreadNode* H = initNode('H');
	ThreadNode* I = initNode('I');
	A->lChild = B;
	A->rChild = C;
	B->lChild = D;
	C->lChild = E;
	C->rChild = F;
	D->lChild = G;
	D->rChild = H;
	E->rChild = I;
	ThreadNode* pre = NULL;
	inOrderThreading(A, &pre);
	printInOrderThreaded(A);
}

3.2.1.2 后续线索二叉树

这里只给除了构造后续线索二叉树的防范，没有给出按照线索遍历的方法，因为后续线索二叉树在有些结点上，其实是无法追踪到他的后续结点，无法输出，还是需要使用之前的两个栈或者递归的方式遍历输出

如下图中，按颜色标记出了各个节点的左右线索，观察结点D和C，可以看到这两个结点没有存储左右线索，所以无法按照线索遍历得到他的前驱后继

#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct ThreadNode {
	dataType data;
	struct ThreadNode* lChild, * rChild;
	int lTag, rTag;
}ThreadTree, ThreadNode;

ThreadNode* initNode(dataType data) {
	ThreadNode* node = (ThreadNode*)malloc(sizeof(ThreadNode));
	if (node == NULL) {
		printf("内存申请失败");
		return NULL;
	}
	node->data = data;
	node->lChild = NULL;
	node->rChild = NULL;
	node->lTag = 0;
	node->rTag = 0;
	return node;
}
// 全局变量，指向刚刚访问过的结点
ThreadNode* pre = NULL;
void postOrderThreading(ThreadNode* root) {
	if (root == NULL) {
		return;
	}
	// 递归左子树线索化
	postOrderThreading(root->lChild);
	postOrderThreading(root->rChild);
	// 节点无左孩子
	if (root->lChild == NULL) {
		root->lTag = 1;
		root->lChild = pre;
	}
	// 前驱没有右孩子
	if (pre != NULL && pre->rChild == NULL) {
		pre->rTag = 1;
		pre->rChild = root;
	}
	pre = root;

}

int main() {
	ThreadNode* A = initNode('A');
	ThreadNode* B = initNode('B');
	ThreadNode* C = initNode('C');
	ThreadNode* D = initNode('D');
	ThreadNode* E = initNode('E');
	ThreadNode* F = initNode('F');
	ThreadNode* G = initNode('G');
	ThreadNode* H = initNode('H');
	ThreadNode* I = initNode('I');
	A->lChild = B;
	A->rChild = C;
	B->lChild = D;
	C->lChild = E;
	C->rChild = F;
	D->lChild = G;
	D->rChild = H;
	E->rChild = I;
	postOrderThreading(A);
}

四、树和森林

4.1 树的存储结构

树可以使用顺序存储，也可以使用链式存储，只要能否反映出节点的逻辑关系即可，在二叉树中我们定义一个结点，并给他定义左右两个孩子结点，但是再树中，子节点数量不定，因此不是用这种定义方式，可以使用以下几种声明

4.1.1 双亲表示法

使用数组来存储结点，每个结点增加一个伪指针，指向他的父节点所在的数组位置

代码定义如下

typedef int ElemType;
typedef struct PTNode {
	ElemType data;
	int parent;// 节点的双亲是唯一的
}PTNode;
typedef struct {
	struct PTNode nodes[10];
	int n;//结点数量
}PTTree;

4.1.2 孩子表示法

每个结点的孩子结点都用链表存储，n个结点就有n个孩子链表

结构定义如下

typedef int ElemType;
//孩子结点
typedef struct cnode {
	int child;//孩子节点下标
	struct cnode* next; //兄弟结点
}link;

typedef struct {
	ElemType data;// 数据
	link* headPtr;// 该节点的子节点信息
} ctree;

4.1.3 孩子双亲表示法

双亲表示法无法只管看到结点有哪些孩子，孩子表示法又无法直接找到自己的双亲，把这二者结合以下，可以综合这两个优点

结构定义如下

// 双亲孩子表示法
typedef int ElemType;
//孩子结点
typedef struct cnode {
	int child;//孩子节点下标
	struct cnode* next; //兄弟结点
}link;

typedef struct {
	ElemType data;// 数据
	int parent;
	link* headPtr;// 该节点的子节点信息
} ctree;
ctree tree[10];

4.1.4 孩子兄弟表示法

孩子兄弟表示法也叫做二叉树表示法，每个结点包括三部分内容，数据，第一个孩子指针，下一个兄弟结点指针

在这里插入图片描述

数据结构定义

//孩子兄弟表示法
typedef int ElemType;
typedef struct CSNode {
	ElemType data;
	struct CSNode* firstChild;// 第一个孩子
	struct CSNode* firstBling;// 第一个兄弟
}CSNode，CSTree;

4.2 树、森林和二叉树的转化

4.2.1 树转化为二叉树

其实就是孩子兄弟表示法，根绝这个表示法，我们可以实现树和森林的转换

树转化为二叉树的规则：

每个节点的左指针指向它的第一个孩子
右指针指向他在树中相邻的右兄弟，由于根节点没有兄弟，所以对应的二叉树没有右子树

树转化为二叉树的画法：

兄弟之间加一条连线
对每个结点，只保留他与第一个孩子的连线，与其他孩子的连线全部抹掉
以树根为轴心，顺时针旋转45度

上图的树转化为二叉树如下，遵循左孩子右兄弟的规则即可

4.2.2 森林转化为二叉树

先把森林中的树转化为二叉树
由于任何一颗树都没有右子树，所以将这些树的根视作兄弟，将后一颗树作为前一棵树的右子树链接

二叉树转为森林反过来操作就行，任意结点右子树的根节点，都是当前节点的兄弟，在森林中就是单独一棵树

4.3 树和森林的遍历

4.4.1 树的遍历

先根遍历先访问根节点，再依次遍历根节点的子树，遍历子树任遵循先根后子树的规则
后根遍历依次遍历根节点的子树，再访问根节点，遍历子树任遵循先子树后根的规则

4.4.2 森林的遍历

先序遍历森林
- 访问森林中第一棵树的根节点
- 先序遍历第一个书中根节点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林
- 中序遍历森林中第一颗树的根节点的子树森林
- 访问第一棵树的根节点
- 中序遍历除去第一棵树之后剩余的树构成的森林

4.4.3 对应关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

4.4 并查集

4.4.1 基本概念

并查集是一个简单的集合表示，支持以下三种操作：

union(s,root1,root2) 把集合S中的子集root2，并入root1，要求root1和root2不相交，否则不执行合并
find(S,x) 再集合s中x元素所在的子集合，返回该子集合的名字
initial(s) 将集合S中的每个元素都初始化为只有一个单元素的子集合

通常用森林的双亲表示作为并查集的存储结构，每个子集都用一棵树表示，所有表示子集合的树，构成全集合的森林

若设有一个全集合为 S ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，初始化时每个元素自成一个单元素子集合，每个子集合的数组值为 -1，如图：

经过一段时间的计算，这些子集合合并为3个更大的子集合，并查集的树形表示和存储结构如图：

这里需要注意，0 1 2 分别为-4 -3 -3 表示他的集中有4个，3个，3个元素，只是用负数标识

两个自己合并，将一个子集的根节点的双亲指向另一个集合的根节点

S1US2就是

4.4.2 代码实现

查询的时间复杂度为O(n)，合并的时间复杂度为O(2)

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10



void initialUnionFind(int s[]) {
    for (int i = 0; i < SIZE; i++) {
        s[i] = -1;
    }
}

// 找到元素的根
int find(int s[],int x) {
    while (s[x] >= 0) {
        x = s[x]; 
    }
    printf("%d\n", s[x]);
    return x;
}
// root合并到root1
void Union(int s[], int root1, int root2) {
    // 把数量加起来
    s[root1] += s[root2];
    // root2作为root1的双亲
    s[root2] = root1;
}

int main() {
    int s[SIZE];
    initialUnionFind(s);
    find(s, 0);

    //0 6 7 8构成一个子集s1
    Union(s, 0, 6);
    Union(s, 0, 7);
    Union(s, 0, 8);
    //1 4 9构成一个子集s2
    Union(s, 1, 4);
    Union(s, 1, 9);

    //2 3 5构成一个子集s3
    Union(s, 2, 3);
    Union(s, 2, 5);


    for (int index = 0; index < SIZE; index++) {
        printf("%d ", s[index]);
    }
    printf("\n");
    // s1和s2合并
    Union(s, 0, 1);
    for (int index = 0; index < SIZE; index++) {
        printf("%d ", s[index]);
    }

}

4.4.3 优化

4.4.3.1 find优化

问题：反复查找某个结点的根结点，每次都会花费大量时间
优化思路：只要查找一次，就将查找路径上的所有结点都挂到根结点下面，如图,查找L的根结点A，查找一次过后，就将E、B、L全部挂到根结点A之下

这里的优化是针对查询集合的优化，如果是还要根据路径来判断，那就不能这么做了,而且只有查询过后才会优化，初始化第一次查询还是原来的时间复杂度，优化后时间复杂度O(a(n)),a(n)是一个增长很慢的函数，通常a(n) < 4

4.4.3.2 合并优化

问题：若只有一个子集合，且这一个子集合是一条细长的链，若结点数是 n ,那么查找的最坏时间复杂度是O(n)
在每次Union操作构建树的时候，尽可能让树不长高，将矮的树合并到高的树，合并后在查询最坏时间复杂度为log₂ⁿ

4.4.3.3 代码实现

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10



void initialUnionFind(int s[]) {
    for (int i = 0; i < SIZE; i++) {
        s[i] = -1;
    }
}

// 找到元素的根
int find(int s[], int x) {
    //找到根节点
    int root = x;
    while (s[root] >= 0) root = s[root];
    //将路径上的结点双亲都设置为root
    while (x != root) {
        int currentParent = s[x];
        s[x] = root;
        x = currentParent;
    }
    printf("%d\n", root);
    return x;
}
// root合并到root1,当root1数量>=root2数量多，root2会合并到root1，否则会反过来
void Union(int s[], int root1, int root2) {
    // 因为存储的是，root1数量比root2多
    if (s[root2] >= s[root1]) {
        s[root1] += s[root2];
        s[root2] = root1; //小树合并到大树，即Root2指向Root1
    }
    else {
        s[root2] += s[root1];
        s[root1] = root2;

    }
}

int main() {
    int s[SIZE];
    initialUnionFind(s);
    find(s, 0);

    //0 6 7 8构成一个子集s1
    Union(s, 0, 6);
    Union(s, 0, 7);
    Union(s, 0, 8);
    //1 4 9构成一个子集s2
    Union(s, 1, 4);
    Union(s, 1, 9);

    //2 3 5构成一个子集s3
    Union(s, 2, 3);
    Union(s, 2, 5);


    for (int index = 0; index < SIZE; index++) {
        printf("%d ", s[index]);
    }
    printf("\n");
    // s1和s2合并
    Union(s, 0, 1);
    for (int index = 0; index < SIZE; index++) {
        printf("%d ", s[index]);
    }

}

标题：数据结构学习笔记--树与二叉树
作者：wenyl
地址：http://www.wenyoulong.com/articles/2024/05/27/1716816969709.html

一、基本概念
1.1 定义
1.2 基本术语
1.3 树的性质
二、二叉树的概念
2.1 二叉树的定义及其特性
2.1.1 二叉树的定义
2.1.2 几个特殊的二叉树
2.1.3 二叉树的性质
2.2 二叉树的存储结构
2.2.1 顺序存储
2.2.2 链式存储
三、二叉树的遍历和线索二叉树
3.1 二叉树的遍历
3.1.1 递归遍历
3.1.1.1 先序遍历
3.1.1.2 中序遍历
3.1.1.3 后序遍历
3.1.1.4 递归遍历代码
3.1.2 非递归遍历
3.1.2.1 先序遍历
3.1.2.2 中序遍历
3.1.2.3 后续遍历
3.1.2.3 非递归遍历代码
3.1.3 层次遍历
3.2 线索二叉树
3.2.1 二叉树线索化
3.2.1.1 前序线索二叉树
3.2.1.2 中序线索二叉树
3.2.1.2 后续线索二叉树
四、树和森林
4.1 树的存储结构
4.1.1 双亲表示法
4.1.2 孩子表示法
4.1.3 孩子双亲表示法
4.1.4 孩子兄弟表示法
4.2 树、森林和二叉树的转化
4.2.1 树转化为二叉树
4.2.2 森林转化为二叉树
4.3 树和森林的遍历
4.4.1 树的遍历
4.4.2 森林的遍历
4.4.3 对应关系
4.4 并查集
4.4.1 基本概念
4.4.2 代码实现
4.4.3 优化
4.4.3.1 find优化
4.4.3.2 合并优化
4.4.3.3 代码实现

Share WeiBo Twitter QZone WeChat ← → ↑ ↓