绵阳梓潼网站制作公司

第五章树与二叉树-创新互联

免责声明：

主要从事网页设计、PC网站建设（电脑版网站建设）、wap网站建设（手机版网站建设）、响应式网站、程序开发、微网站、小程序定制开发等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了丰富的网站设计、成都网站设计、网络营销经验，集策划、开发、设计、营销、管理等多方位专业化运作于一体，具备承接不同规模与类型的建设项目的能力。
  • 笔记来源：本系列所有笔记均整理自 B站·王道考研·数据结构 视频教程。
  • 参考书籍：《2021年数据结构考研复习指导》，王道论坛所著，电子工业出版社出版，ISBN ：9787121379819。

目录

1 树 1.1 树的概念

树，由 n （n >= 0）个结点组成的有限集。

  • 树中除了根结点外，其他节点有且仅有一个前驱
  • 树值所有节点可以有0个或者多个后继
  • 树是一种递归的逻辑结构，同时也是一种分层结构
  • 空树：n 为0时
  • 非空数：n >0 时
    • 只有一个根结点
    • 其余子结点又可以作为一棵树（每棵子树的结点集不想交）
  • 树的高度：也叫深度，即树总的有多少层
  • 结点 的深度：从上往下数，结点在第几层（也叫结点 的层次）
  • 结点的高度： 从下往上数，结点在第几层
  • 结点的度：某个结点的子结点个数
    • 度大于0：分支结点、非终端结点
    • 度等于0：叶子结点、终端结点
  • 树的度：各结点中度的大值
  • 边：连接两个结点的路径
  • 路径长度：从起始结点到达目标结点需要经过几条边（只能从上到下）
    在这里插入图片描述
  • 有序树：逻辑上，树中结点的各子树，从左到右是有次序的，不能交换位置
  • 无序树：逻辑上，树中结点的各子树，从左到右是无次序的，可以交换位置
1.2 树的基本性质
  • 总结点数等于所有结点的度数加1
  • 度为 m 的树与m叉树的区别

在这里插入图片描述

  • 高度为h的m叉树，最多有（m^h - 1）/ (m - 1)个结点，最少有h个结点
  • 高度为 h 度 为m的树，至少有h + m - 1个结点
    在这里插入图片描述
2 二叉树 2.1 二叉树的概念

二叉树是一种每个结点最多只有两棵子树的树，子树分别叫做左子树和右子树，其顺序不能交换。即便树中只有一颗子树，也要区分是左子树还是右子树。因此，二叉树中不存在度大于2的结点。
在这里插入图片描述

2.2 特殊的二叉树 满二叉树与完全二叉树

在这里插入图片描述

二叉搜索树

在这里插入图片描述

平衡二叉树

在这里插入图片描述

2.3 二叉树的基本性质

性质1

在这里插入图片描述

性质2

在这里插入图片描述

性质3

在这里插入图片描述

完全二叉树的性质

在这里插入图片描述

3、二叉树的存储结构 3.1 顺序存储

对于一棵完全二叉树，采用顺序存储结构如下：
在这里插入图片描述
在这里插入图片描述
对于普通的二叉树，为了让数组下标能够反应出结点间的逻辑关系，只能添加一些并不存在的虚拟结点，让其与完全二叉树相对应起来，如下：

在这里插入图片描述
但是这种方式，使得存储空间利用率降低，而且不方便判断是某个结点是否有左或右孩子，也不方便判断这个结点是否属于叶子结点。因此对于二叉树，一般使用链式存储结构。

3.2 链式存储

二叉链表的结点，至少包含三个域：

  • 数据域
  • 左孩子指针域
  • 右孩子指针域
    在这里插入图片描述
    在这里插入图片描述

链式存储实现二叉树定义：

#includenamespace MYTREE{using std::cout;
	using std::endl;

	// 链式存储实现二叉树
	// 二叉树结点定义
	struct TreeNode {int data; // 数据域
		TreeNode* lc; // 指向左孩子节点的指针
		TreeNode* rc; // 指向右孩子节点的指针
	};
	// 二叉树
	typedef TreeNode* BinaryTree;

	// 给指定结点添加孩子结点
	// 约定flag：true 表示左孩子 false 表示右孩子
	bool InsertNode(TreeNode* node, bool flag, int value) {if (node == NULL) {	return false;
		}
		// 创建新的结点
		TreeNode* new_node = new TreeNode;
		new_node->data = value;
		new_node->lc = NULL;
		new_node->rc = NULL;
		
		if (flag) {	// 添加左子结点
			node->lc = new_node;
		}
		else {	// 添加右子结点
			node->rc = new_node;
		}
		return true;
	}
}

int main() {using namespace MYTREE;

	// 创建一棵空树
	BinaryTree tree = NULL;
	// 插入根结点 1
	tree = new TreeNode;
	tree->data = 1;
	tree->lc = NULL;
	tree->rc = NULL;

	// 插入根结点的左子结点 2
	InsertNode(tree, true, 2);
	// 插入根结点的右子结点 3
	InsertNode(tree, false, 3);
	// 给跟结点的左孩子结点插入右子结点 4
	InsertNode(tree->lc, false, 4);
	// 给跟结点的右孩子结点插入左子结点 6
	InsertNode(tree->rc, true, 6);
	// 给跟结点的右孩子结点插入右子结点 7
	InsertNode(tree->rc, false, 7);
	// 给跟结点的左孩子结点的右孩子结点插入右子结点 11
	InsertNode(tree->lc->rc, false, 11);
	// 给跟结点的右孩子结点的左孩子结点插入左子结点 12
	InsertNode(tree->rc->lc, true, 12);
}

使用两个指针表示左右孩子结点，可以很方便的访问到左右孩子结点，但是要访问其父结点就只能从头遍历，可以根据实际情况，在结点中增设一个父结点指针，指向其父结点，这样的链表称为三叉链表。

4、二叉树的遍历 4.1 先序、中序、后续遍历

遍历一棵二叉树，需要确定对根结点N，左子树L 和右子树R 的访问顺序，一般按照先左后右的原则，遍历顺序中的序是指访问根结点的顺序，常见的分为三种：

  • 先序遍历：先访问跟结点，再按先序遍历左子树，最后按先序遍历右子树
  • 中序遍历：先按中序遍历左子树，再访问根结点，最后按中序遍历右子树
  • 后序遍历：先按后序遍历左子树，再按后序遍历右子树，最后访问根结点

对于有n个结点的一棵二叉树，使用三种遍历方式的递归算法，若不考虑访问结点的方式带来的影响，那么：

  • 时间复杂度：都是O(n)，因为每个结点都只访问一次
  • 空间复杂度：递归工作栈的深度就是树的深度，假如二叉树是一颗n个结点，深度为n的单支树，此时空间复杂度达到大O(n)
先序遍历
// 先序遍历：根→左孩子→右孩子
void PreOrder(const BinaryTree& tree) {// 如果是空树，则什么也不做
	if (tree != NULL) {// 最先访问根结点
		cout<< tree->data<< " ";
		// 然后访问左子树
		PreOrder(tree->lc);
		// 最后访问右子树
		PreOrder(tree->rc);
	}
}
中序遍历
// 中序遍历
void InOrder(const BinaryTree& tree) {// 如果是空树，则什么也不做
	if (tree != NULL) {// 最先访问左子树
		InOrder(tree->lc);
		// 然后访问根结点
		cout<< tree->data<< " ";
		// 最后访问右子树
		InOrder(tree->rc);
	}
}
后续遍历
// 后序遍历
void PostOrder(const BinaryTree& tree) {// 如果是空树，则什么也不做
	if (tree != NULL) {// 最先访问左子树
		PostOrder(tree->lc);
		// 然后访问右子树
		PostOrder(tree->rc);
		// 最后访问根结点
		cout<< tree->data<< " ";
	}
}
4.2 递归求二叉树的深度
// 求二叉树的深度
int GetDepth(const BinaryTree& tree) {if (tree == NULL) {return 0;
	}
	else {int l = GetDepth(tree->lc); // 求出左子树的深度
		int r = GetDepth(tree->rc); // 求出由子树的深度
		// 树的深度 = Max(左子树深度，右子树深度) + 1
		return l >r ? l + 1 : r + 1;
	}
}
4.3 层次遍历

二叉树的层序遍历是指，从上到下，从左到右一次遍历每个结点，需要借助队列完成。

  • 根结点入队，然后出队
  • 针对出队结点，若存在左子树，则左子树根结点入队；若存在右子树，则右子树根结点入队，然后出队
  • 再访问出队结点，循环第二步，直到队列为空

使用一个链式队列来存储二叉树的结点指针：

// 链式队列的一个节点
struct LQNode {// 数据域存储的是二叉树的一个结点的指针
	TreeNode* data;
	LQNode* next;
};
// 链式队列
struct LinkQueue {LQNode* front; // 队头指针，指向第一个节点或者指向头结点
	LQNode* rare; // 队尾指针，指向最后一个节点
};

// 带头结点的链式队列 初始化
void InitLinkQueue(LinkQueue& queue) {// 初始时，队头指针、队尾指针都指向头结点
	queue.front = queue.rare = new LQNode;
	// 头结点的next指针域指向空
	queue.front->next = NULL;
}

// 带头结点的链式队列 判断是否为空
bool LinkQueueIsEmpty(LinkQueue queue) {// 通过头指针与尾指针是否指向同一个位置判断
	return queue.front == queue.rare;
}

// 带头结点的链式队列 入队
// 将 一个指向二叉树结点的指针 TreeNode* 存入队列尾部
bool LinkQueueIn(LinkQueue& queue, TreeNode* node_pointer) {// 创建一个新的节点
	LQNode* s = new LQNode;
	if (s == NULL) {// 分配内存失败
		return false;
	}
	// 将数据存入新的节点
	s->data = node_pointer;
	// 新节点应该是最后一个节点，它的指针域应该指向NULL
	s->next = NULL;
	// 将新的节点插入到队尾（只能从队尾插入）
	queue.rare->next = s;
	// 队尾指针后移,指向新插入的节点
	queue.rare = s;
	return true;
}

// 带头结点的链式队列 出队
// 使用引用变量的方式，将一个指向二叉树结点的指针 TreeNode* 返回 
bool LinkQueueOut(LinkQueue& queue, TreeNode*& node_pointer) {if (queue.front == queue.rare) {return false; // 空队列
	}
	// 指向要出队的节点
	// 队首结点是头结点的后继节点
	LQNode* p = queue.front->next;
	// 先使用引用变量将要出队的元素返回
	node_pointer = p->data;
	// 修改头结点的后继节点
	queue.front->next = p->next;
	// 如果此时是最后一个元素出队
	if (queue.rare == p) {// 队尾指针也指向头结点
		queue.rare = queue.front;
	}
	// 释放内存空间
	delete p;
	return true;
}

层序遍历二叉树：

// 层序遍历
void LevelOrder(const BinaryTree& tree) {// 辅助队列
	LinkQueue queue;
	// 初始化空队列
	InitLinkQueue(queue);
	// 当前访问的结点
	TreeNode* p = NULL;
	// 根结点入队
	LinkQueueIn(queue, tree);
	// 如果队列不为空，开始循环
	while (!LinkQueueIsEmpty(queue)) {// 队头节点出队
		LinkQueueOut(queue, p);
		// 访问出队结点数据域
		cout<< p->data<< " ";
		// 如果左子树不为空，左子树根结点入队
		if (p->lc != NULL) {	LinkQueueIn(queue, p->lc);
		}
		// 如果右子树不为空，右子树根结点入队
		if (p->rc != NULL) {	LinkQueueIn(queue, p->rc);
		}

	}
}
4.4 由遍历序列构造二叉树

若只给出一棵二叉树的前序遍历序列或中序遍历序列或后序遍历序列或层序遍历序列，无法确定唯一的一棵二叉树。由中序遍历序列和其他三个中的任意一个遍历序列组合，就能确定唯一的二叉树：
在这里插入图片描述

5 线索二叉树 5.1 线索二叉树的概念

传统的二叉链表，仅仅能体现父子关系，无法表达出结点在遍历序列中的前驱或后继。

以普通二叉树的中序遍历为例：

  • 每次都必须从根结点出发
  • 无法找到某个结点在遍历序列中的前驱（基于遍历序列定义的前驱）

包含n个节点的二叉树中，存在 n+1 个空指针域。可以利用这些空指针域，来存放结点在遍历序列中的前驱指针和后继指针。

在这里插入图片描述
因此，根据如下规定，若某个结点：

  • 没有左子树，让左孩子指针 lc 指向其遍历序列中的前驱结点
  • 没有右子树，让右孩子指针 rc 指向其遍历序列中的前驱结点
  • 增加两个标识域，存放标识左右指针所指向的是左/右孩子还是前驱/后继

在这里插入图片描述
中序线索二叉树，以中序序列为依据进行线索化。先序线索二叉树与后续线索二叉树同理。

5.2 二叉树线索化
#include// 线索二叉树
namespace CLUE_BINARY_TREE {using std::cout;
	using std::endl;

	typedef int E;

	// 定义线索二叉树的结点
	struct CBTreeNode {E data;// 数据域
		CBTreeNode* lc; // 左孩子指针或者前驱结点指针
		CBTreeNode* rc; // 右孩子指针或者后继结点指针
		int l_tag; // 左指针标识，0表示指向的是左孩子，1表示指向的是前驱
		int r_tag; // 右指针标识，0表示指向的是右孩子，1表示指向的是后继
	};
	// 线索二叉树
	typedef CBTreeNode* CBTree;

	// 给指定结点添加孩子结点 约定flag：true 表示左 false 表示右
	bool AddNode(CBTreeNode* node, bool flag, E value) {if (node == NULL) {	return false; // 指定结点不能为空
		}
		CBTreeNode* new_node = new CBTreeNode; // 创建新的结点
		new_node->data = value;
		new_node->lc = NULL;
		new_node->rc = NULL;
		if (flag) {	node->lc = new_node; // 添加左子结点
		}
		else {	node->rc = new_node;// 添加右子结点
		}
		return true;
	}


	// 构建一棵二叉树
	void BuildTree(CBTree& tree) {// 创建 根结点
		tree = new CBTreeNode;
		tree->data = 1;
		tree->lc = NULL;
		tree->rc = NULL;

		AddNode(tree, true, 2); // 根结点添加左孩子
		AddNode(tree, false, 3); // 根结点添加右孩子

		AddNode(tree->lc, true, 4); // 根结点的左孩子添加左孩子
		AddNode(tree->lc, false, 5); // 根结点的左孩子添加右孩子

		AddNode(tree->rc, true, 6); // 根结点的右孩子添加左孩子
		AddNode(tree->rc, false, 7); // 根结点的右孩子添加右孩子

		AddNode(tree->rc->rc, true, 8); // 根结点的右孩子 的右孩子 添加左孩子
		AddNode(tree->rc->rc, false, 9); // 根结点的右孩子 的右孩子 添加右孩子
	}

	void Visit(const CBTree& tree) {cout<< tree->data<< " ";
	}

	// 普通二叉树的中序遍历
	void InOrder(const CBTree& tree) {if (tree != NULL) {	// 先访问左子树
			InOrder(tree->lc);
			// 访问根结点
			Visit(tree);
			// 后访问右子树
			InOrder(tree->rc);
		}
	}

	// 通过中序遍历对二叉树进行线索化递归算法
	// p 指向正在访问的结点；pre 指向刚刚访问过的结点
	void InClue(CBTree& p, CBTree& pre) {if (NULL != p) {	// 递归线索化左子树
			InClue(p->lc, pre);
			// 左子树为空，则建立前驱线索
			if (NULL == p->lc) {		p->lc = pre; // 指向前驱结点
				p->l_tag = 1; // 表示lc指向的是前驱结点
			}
			// 建立前驱结点的后继线索
			if (NULL != pre && NULL == pre->rc) {		pre->rc = p; // 指向后继结点
				pre->r_tag = 1; // 表示rc指向的是后继结点
			}
			// 标记当前结点为刚刚访问过的结点
			pre = p;
			// 递归线索化右子树
			InClue(p->rc, pre);
		}
	}

	// 建立中序线索二叉树
	void CreateInCBTree(CBTree& tree) {// 指向刚刚访问过的结点的指针
		CBTreeNode* pre = NULL;
		// 如果是非空二叉树，则进行线索化
		if (NULL != tree) {	// 线索化二叉树
			InClue(tree, pre);
			// 处理遍历序列中的最后一个节点
			pre->rc = NULL;
			pre->r_tag = 1;
		}
	}

	// 求中序线索二叉树 中序序列的第一个结点
	CBTreeNode* GetFirst(CBTreeNode* p) {while (p->l_tag == 0) {	p = p->lc;
		}
		return p;
	}
	// 求线索二叉树中，中序序列的最后结点
	CBTreeNode* GetLast(CBTreeNode* p) {while (p->r_tag == 0) {	p = p->rc;
		}
		return p;
	}

	// 求线索二叉树中，结点p在中序序列下的后继结点
	CBTreeNode* GetNext(CBTreeNode* p) {if (p->r_tag == 0) {	return GetFirst(p->rc);
		}
		else {	// 为 1 直接返回后继线索
			return p->rc;
		}
	}

	// 求线索二叉树中，结点p在中序序列下的前驱结点
	CBTreeNode* GetPre(CBTreeNode* p) {if (p->l_tag == 0) {	return GetLast(p->lc);
		}
		else {	// 为 1 直接返回前驱线索
			return p->lc;
		}
	}



	// 中序线索二叉树的遍历
	void InClueOrder1(CBTree tree) {for (CBTreeNode* p = GetFirst(tree); p != NULL; p = GetNext(p)) {	Visit(p); // 访问结点
		}
	}

	// 中序线索二叉树的逆向遍历
	void InClueOrder2(CBTree tree) {for (CBTreeNode* p = GetLast(tree); p != NULL; p = GetPre(p)) {	Visit(p); // 访问结点
		}
	}

}

int main() {using namespace CLUE_BINARY_TREE;

	CBTree tree;
	BuildTree(tree);
	// 普通中序遍历线索二叉树
	// InOrder(tree);
	cout<< endl;
	// 构建中序线索二叉树
	CreateInCBTree(tree);
	// 遍历中序线索二叉树
	InClueOrder1(tree);
	cout<< endl;
	InClueOrder2(tree);
}
6 树的存储结构

在这里插入图片描述

6.1 双亲表示法

在这里插入图片描述

#define MAX_SIZE 100

typedef int E;
// 树的结点定义
struct TreeNode {E data; // 数据域
	int parent; // 双亲的位置域
};

// 树的定义
struct MyTree {TreeNode nodes[MAX_SIZE]; // 结点数组
	int n; // 结点数
};
6.2 孩子表示法

在这里插入图片描述

6.3 孩子兄弟表示法

在这里插入图片描述

6.4 树的遍历 先根遍历

在这里插入图片描述

后根遍历

在这里插入图片描述

层次遍历

在这里插入图片描述

7 树与二叉树的应用 7.1 二叉排序树 BST

在这里插入图片描述

// 链式存储实现二叉树
// 二叉树结点定义
struct TreeNode {int data; // 数据域
	TreeNode* lc; // 指向左孩子节点的指针
	TreeNode* rc; // 指向右孩子节点的指针
};
// 二叉树
typedef TreeNode* BinaryTree;
查找操作

左子树结点值< 根结点值< 右子树结点值：

  • 若树非空，目标值与根结点值比较
  • 如果相等，则查找成功
  • 如果不相等，则继续查找
    • 小于根结点，在左子树上查找
    • 大于根结点，在右子树上查找
  • 查找成功返回结点指针，查找失败，返回NULL
// 查找，非递归实现，空间复杂度 O(1)
TreeNode* Search1(BinaryTree tree, int e) {while (tree != NULL && e != tree->data) {// 目标值在右子树上
		if (e >tree->data) {	tree = tree->rc;
		}
		// 目标值在左子树上
		else {	tree = tree->lc;
		}
	}
	return tree;
}
// 查找，递归实现，空间复杂度O(h)，h表示树的高度
TreeNode* Search2(BinaryTree tree, int e) {if (tree == NULL) {// 查找失败
		return NULL;
	}
	if (e == tree->data) {return tree; // 查找成功
	}
	else if (e< tree->data) {// 在左子树上查找
		return Search2(tree->lc,e);
	}
	else {// 在右子树上查找
		return Search2(tree->rc,e);
	}
}
插入操作

若原二叉排序树为空，则直接插入结点，否则，若关键字 k 小于根结点的值，将其插入到左子树上，若关键字 k 大于根结点的值，将其插入到右子树上。

// 插入，递归实现，空间复杂度O(h)，h 为二叉树的高度
bool Insert1(BinaryTree& tree, int e) {if (tree == NULL) {// 空树，直接插入到根结点
		tree = (BinaryTree)malloc(sizeof(TreeNode));
		tree->data = e;
		tree->lc = tree->rc = NULL;
		return true;
	}
	else if (e == tree->data) {// 存在相同关键字结点，插入失败
		return false;
	}
	else if (e< tree->data) {// 在左边插入
		Insert1(tree->lc, e);
	}
	else {// 在右边插入
		Insert1(tree->rc, e);
	}
}

可以使用插入函数，构造一棵二叉搜索树：

// 通过一个数组构造一棵二叉排序树
void BuildBST(BinaryTree& tree, int arr[], int n) {tree = NULL;
	int i = 0;
	while (i< n) {Insert1(tree, arr[i]);
		i++;
	}
}
删除操作

先搜索找到目标结点：

  • 若即将被删除的结点是叶子结点，那么直接删除即可
  • 若即将被删除的结点只有左子树或者只有右子树，那么在删除该节点后，将其子树作为其父结点的子树即可
  • 若即将被删除的结点 z 既有左子树又有右子树
    • 让 z 结点在中序遍历序列中的直接前驱（左子树中大的结点）或直接后继（右子树中最小的结点）代替 z，然后再删除这个直接前驱（或直接后继）
查找效率分析

查找成功时的查找长度：
查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反应了查找操作的时间复杂度。
最坏的情况：每个结点只有一个分支，树的高度h等于结点数n，平均查找长度 O(n)
最好的情况：n 个节点的二叉树，达到最小高度，即 log2n 向下取整再加1，此时的平均查找长度为 O(log2n)

查找失败时的查找长度：
在这里插入图片描述

7.2 平衡二叉树

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）：树上任一结点的左子树和右子树的高度差不超过1。

结点的平衡因子= 左子树的高度 - 右子树的高度

因此，平衡二叉树的各结点的平衡因子只可能是 -1或0或1。

平衡二叉树的定义
// 平衡二叉树的结点定义
struct AVLNode {int key; // 数据域
	int balance; // 平衡因子
	AVLNode* lc; // 左孩子指针
	AVLNode* rc; // 右孩子指针
};
// 平衡二叉树定义
typedef AVLNode* AVLTree;
平衡二叉树的调整

二叉排序树在插入结点后，如何保持平衡，使得查找操作的时间复杂度达到最优的 O(log2n)？

从新插入结点往回找到第一个不平衡的结点（最小不平衡子树），调整以该结点为根的子树。
在这里插入图片描述
最小不平衡子树恢复平衡后，其他受影响的结点也将恢复平衡
在这里插入图片描述
如何让最小不平衡子树恢复平衡呢？需要分四种情况：

在这里插入图片描述

  • LL 在A结点的左孩子的左子树中插入新的结点导致不平衡

在这里插入图片描述

  • RR 在A结点的右孩子的右子树中插入新的结点导致不平衡
    在这里插入图片描述

  • LR 在A结点的左孩子的右子树中插入新的结点导致不平衡
    在这里插入图片描述
    在这里插入图片描述

  • RL 在A结点的右孩子的左子树中插入新的结点导致不平衡

在这里插入图片描述
在这里插入图片描述

平衡二叉树的查找效率

在这里插入图片描述

7.3 哈夫曼树 哈夫曼树的定义

  • 结点的权：给树中的结点赋予一个表示某种意义的数值，这个数值就是该结点的权。

  • 结点的带权路径长度：从根结点到任意结点的路径长度与该结点权值的乘积，称为结点的带权路径长度。

  • 树的带权路径长度：所有叶子结点的带权路径长度之和。

  • 哈夫曼树：在含有 n 个带权叶结点的二叉树中，其中带权路径长度最小的二叉树叫做最优二叉树，也叫做哈夫曼树。

如下三个二叉树都有 4个带权的叶子结点：

  • 第一个二叉树的带权路径长度：72 + 52 + 22 + 42 = 36
  • 第二个二叉树的带权路径长度：73 + 53 + 21 + 42 = 46
  • 第三个二叉树的带权路径长度：71 + 52 + 23 + 43 = 35

在这里插入图片描述
第三个二叉树的带权路径长度最小，第三个二叉树是哈夫曼树。

哈夫曼树构造

在这里插入图片描述
第二种构造结果：
在这里插入图片描述

哈夫曼编码

比如，要传递四个字符 A B C D

  • 固定长度编码
    • 每个字符使用相等长度的二进制位表示，比如 ASCII 编码，使用8个bit位二进制表示一个字符:
      • A : 0100 0001
      • B : 0100 0010
      • C : 0100 0011
      • D : 0100 0100
    • 要发送的字符只有4中形态，因此可以使用长度为 2 的二进制位表示一个字符：
      • A : 00
      • B : 01
      • C : 10
      • D : 11
  • 可变长度编码：对不同的字符使用不同长度的二进制位表示

在这里插入图片描述
前缀编码：如果不存在一个编码是另一个编码的前缀，则称这样的编码是前缀编码，非前缀编码在解码是有歧义。

由哈夫曼树得到哈夫曼编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，构造出哈夫曼树（可以将树的左指针看作二进制的0，右指针看作二进制的1）。

哈夫曼编码可以用于数据的压缩。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网站题目：第五章树与二叉树-创新互联
网页路径：http://myzitong.com/article/dpoedd.html

其他资讯