网站首页 > 技术文章正文

数据结构——第5章-树和二叉树数据结构树和二叉树思维导图

btikc 2024-10-19 03:10:56 技术文章 6 ℃ 0 评论

5.1 树和二叉树的定义

5.1.1 树的定义

树(Tree)是 n(n≥0) 个结点的有限集

若 n = 0，称为空树
若 n = 0，则它满足如下两个条件

有且仅有一个特定的称为根（Root）的结点
其余结点可分为m（m≥0）个互不相交的有限集 T1，T2，T3，... ，Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）

5.1.2 树的基本术语

根结点：非空树中无前驱结点的结点
结点的度：结点拥有的子树数
树的度：树内各结点的度的最大值
树的深度：树中结点的最大层次
终端结点：当度为0时的结点度≠0，非终端结点
内部结点：根节点以外的非终端结点
孩子、双亲：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
结点的祖先：从根到该节点所经分支上的所有结点
结点的子孙：以某结点为根的子树中的任一结点

有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）

无序树：树中结点的各子树无次序

森林：

是 m(m≥0)棵互不相交的树的集合
把根结点删除树就变成了森林
一棵树可以看成是一个特殊的森林
给森林中的各子树加上一个双亲结点，森林就变成了树

树一定是森林，森林不一定是树

5.1.3 二叉树的定义

二叉树的结构最简单，规律性最强；所有树都能转为唯一对应的二叉树，不失一般性；普通树（多叉树）若不转化为二叉树，则运算很难实现

二叉树是 n(≥0) 个结点的有限集，它或者是空集 (n = 0)，或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成

特点：

每个结点最多有两孩子（二叉树中不存在度大于2的结点）
子树有左右之分，其次序不能颠倒
二叉树可以是空集合，根可以有空的左子树或空的右子树

注：二叉树不是树的特殊情况，它们是两个概念

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树
树当结点只有一个孩子时，就无须区分它是左还是右的次序，因此二者是不同的。这是二叉树与树的最主要的区别

具有两个结点的二叉树有两种状态

具有两个结点的树只有一种状态

即二叉树的每个结点的位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说，没有别的结点时，它就无所谓左右了

5.2 案例引入

5.2.1 数据压缩问题

将数据文件转换成由 0、1组成的二进制串，称之为编码

5.2.2 利用二叉树求解表达式的值

以二叉树表示表达式的递归定义如下：

若表达式为数或简答变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息
若表达式为“第一操作数运算符第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作树，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身又为表达式

然后对二叉树进行后序遍历

5.3 树和二叉树的抽象数据类型定义

基本操作：

CreateBinaryTree(&T, definition)

初始条件：definition给出二叉树T的定义
操作结果：按definition构造二叉树T

PreOrderTraverse(T)

初始条件：二叉树T存在
操作结果：先序遍历T，对每个结点访问一次

InorderTraverse(T)

初始条件：二叉树T存在
操作结果：中序遍历T，对每个结点访问一次

PostOrderTraverse(T)

初始条件：二叉树T存在
操作结果：后序遍历T，对每个结点访问一次

5.4 二叉树的性质和存储结构

5.4.1 二叉树的性质

性质1：在二叉树的第 i 层上至多有 2^(i-1) 个结点 ( i ≥ 1) 第 i 层至少有 1 个结点

性质2：深度为k的二叉树至多有 2^k - 1 个结点( k≥1 )；最少有 k 个结点

性质3：对任何一棵二叉树 T ，如果其叶子数为 n0，度为 2 的结点数为 n2，则 n0 = n2 +1

满二叉树

定义：一棵深度为 k 且有 2^k - 1 个结点的二叉树称为满二叉树

特点：

每一层上的结点数都是最大结点数（即每层都满）
叶子结点全部在最底层

完全二叉树

定义：深度为 k 的具有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号为 1~n 的结点一一对应时，称之为完全二叉树

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

即在满二叉树中，从最后一个结点开始，连续去掉任意结点，即是一棵完全二叉树；必须连续去掉

特点：

叶子结点只可能分布在层次最大的两层上
对任意结点，如果其右子树的最大层次为 i ，其左子树的最大层次必为 i 或 i+1

性质4：具有 n 个结点的完全二叉树的深度为 log(2, n)（取整） +1

性质5：如果对一棵具有 n 个结点的完全二叉【树深度为 log(2, n)（取整） +1】的结点按层序编号（从第1层到第 log(2, n)（取整） +1 层，每层从左到右），则对任一结点 i （1≤ i ≤ n），有：

5.4.2 二叉树的存储结构

顺序存储结构

按满二叉树的结点层次编号，依次存放二叉树中的数据元素

类C语言

// 二叉树的顺序存储表示
#define MAXSQTREESIZE 100

typedef TelEmeType sequenBinaryTree[MAXSQTREESIZE];
sequenBinaryTree bt;

如果既不是满二叉树也不是完全二叉树

二叉树顺序存储的缺点：

特点：结点间关系蕴含在其存储位置中，浪费空间，适于存满二叉树和完全二叉树

链式存储

二叉链表

typedef struct BinaryNode {
	char data;							// 数据域
	struct BinaryNode* leftChild;		// 左孩子
	struct BinaryNode* rightChild;		// 右孩子
}binaryNode, * linkBinaryTree;

如图：

在n个结点的二叉链表中，有 n + 1 个空指针域

分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以会有 n-1 个结点的链域存放指针，指向非空子女结点。即空指针数目 = 2n -(n - 1) = n + 1

三叉链表

仅多了一个指针域指向双亲结点

5.5 遍历二叉树和线索二叉树

5.5.1 遍历二叉树

遍历定义：顺着某一条搜索路径巡访二叉树中的结点，使得某一个结点均被访问一次，而且仅被访问一次（又称周游）

访问的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构

遍历目的：得到树中所有结点的一个线性排列

遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心

先序遍历

若二叉树为空，则空操作；否则：

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

/*******************************************************************************************************************************
 * @description：先序遍历
 * @param：tree	链式树
 */
void preOrderTraverse(linkBinaryTree tree) 
{
	if (tree == NULL) {
		return;
	}
	printf("%c", tree->data);			// 根
	preOrderTraverse(tree->leftChild);	// 左
	preOrderTraverse(tree->rightChild);	// 右
}

中序遍历

若二叉树为空，则空操作；否则

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

/*******************************************************************************************************************************
 * @description：中序遍历
 * @param：tree	链式树
 */
void inOrderTraverse(linkBinaryTree tree)
{
	if (tree == NULL) {
		return;
	}
	inOrderTraverse(tree->leftChild);	// 左
	printf("%c", tree->data);			// 根
	inOrderTraverse(tree->rightChild);	// 右
}

后序遍历

若二叉树为空，则空操作；否则：

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

/*******************************************************************************************************************************
 * @description：后序遍历
 * @param：tree	链式树
 */
void postOrderTraverse(linkBinaryTree tree)
{
	if (tree == NULL) {
		return;
	}
	postOrderTraverse(tree->leftChild);		// 左
	postOrderTraverse(tree->rightChild);	// 右
	printf("%c", tree->data);				// 根
}

遍历算法的分析：

三种算法时间复杂度：O(n)，空间复杂度：O(n)

中序遍历非递归算法

二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

基本思想：

建立一个栈
根结点进栈，遍历左子树
根节点出栈，输出根节点，遍历右子树

status inOrderTraverse(Bitree T)
{
    BiTree p;
    initStack(S);
    p = T;
    while(p || !StackEmpty(S)){
        if(p){
            Push(S, p);
            p = p->leftChild;
        }
        else{
            Pop(S, p);
            printf("&c", q->data);
            p = q->rightCild;
        }
    }
    return OK;
}

层次遍历

对于一棵二叉树，从根节点开始，按从上到下、从左到右的顺序访问每一个结点，每个结点仅仅访问一次

层次遍历结果：abfcdgeh

算法思路：使用一个队列

将根结点进队
队不为空时循环：从队列中出列一个结点*p，访问它

若它有左孩子结点，将左孩子结点进队
若它有右孩子结点，将右孩子结点进队

void levelOrder(BTNode* b)
{
    BTNode* p;
    SqQueue* qu;
    initQueue(qu);						// 初始化队列
    enQueue(qu, b);						// 根节点指针进入队列
    while(!QueueEmpty(qu)){				// 队不为空则循环
        deQueue(qu, p);					// 出队结点p
        printf("%c", p->data);			// 访问结点p
        if(p->leftData!=NULL){
            enQueue(qu, p->leftCild);	// 有左孩子时将其进队
        }
        if(p->rightChild!=NULL){
            enQueue(qu, p->rightChild);	// 有右孩子时将其进队
        }
    }
}

先序遍历建立二叉树

算法思路：

从键盘输入二叉树的结点信息，建立二叉树的存储结构
在建立二叉树的过程中按照二叉树先序方式建立

/*******************************************************************************************************************************
 * @description：先序遍历创建二叉树
 * @return：
 */
status preCreateBinaryTree(linkBinaryTree* tree)
{
	char ch;
	printf("输入先序序列，以#表示空结点：");
	scanf("%c", &ch);
	if (ch == '#') {
		*tree = NULL;
	}
	else {
		*tree = (linkBinaryTree)malloc(sizeof(binaryNode));
		if (*tree == NULL) {
			exit(OVERFLOW);
		}
		(*tree)->data = ch;		// 生成根结点
		preCreateBinaryTree(&(*tree)->leftChild);	// 构造左子树
		preCreateBinaryTree(&(*tree)->rightChild);	// 构造右子树
	}
	return OK;
}

复制二叉树

算法思路：

如果是空树，递归结束
否则。申请新结点空间，复制根结点

递归复制左子树
递归复制右子树

/*******************************************************************************************************************************
 * @description： 复制二叉树
 * @param：tree
 * @param：copyTree
 * @return：
 */
status copyBinaryTree(linkBinaryTree tree, linkBinaryTree* copyTree)
{
	if (copyTree == NULL) {
		tree = NULL;
	}
	else {
		*copyTree = (linkBinaryTree)malloc(sizeof(binaryNode));
		if (*copyTree == NULL) {
			exit(OVERFLOW);
		}
		(*copyTree)->data = tree->data;
		copyBinaryTree(tree->leftChild, &((*copyTree)->leftChild));
		copyBinaryTree(tree->rightChild, &((*copyTree)->rightChild));
	}
	return OK;
}

计算二叉树深度

算法思路：

如果是空树，则深度为0；
否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1

/*******************************************************************************************************************************
 * @description：计算二叉树深度
 * @param：tree
 * @return：
 */
int depthBinaryTree(linkBinaryTree tree)
{
	int depth = 0;
	if (tree != NULL) {
		int leftDepth = depthBinaryTree(tree->leftChild);
		int rightDepth = depthBinaryTree(tree->rightChild);
		depth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
	}
	return depth;
}

计算结点总数

算法思路：

如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数 + 右子树的结点个数再 + 1

/*******************************************************************************************************************************
 * @description：求结点总数
 * @param：tree
 * @return：
 */
int countBinaryTree(linkBinaryTree tree)
{
	int count = 0;
	if (tree != NULL) {
		count = 1 + countBinaryTree(tree->leftChild) + countBinaryTree(tree->rightChild);
	}
	return count;
}

计算叶子结点总数

/*******************************************************************************************************************************
 * @description：求叶子结点的总数
 * @param：tree
 * @return：
 */
int countLeafBinaryTree(linkBinaryTree tree)
{
	if (tree != NULL) {
		if (tree->leftChild == NULL && tree->rightChild == NULL) {
			return  1;
		}
		else {
			return  countLeafBinaryTree(tree->leftChild) + countLeafBinaryTree(tree->rightChild);
		}
	}
    return 0;
}

测试代码

构建如图二叉树

void BinaryTreeMain()
{
	linkBinaryTree tree = NULL;

	/**
	* 先序遍历顺序为：ABCDEGF
	* 输入：ABC##DE#G##F###
	*/
	printf("\n输入先序序列，以#表示空结点：");
	preCreateBinaryTree(&tree);
	printf("\n二叉树中的元素为：");
	printBinaryTree(tree);

	printf("\n\n先序遍历：");
	preOrderTraverse(tree);
	printf("\n\n中序遍历：");
	inOrderTraverse(tree);
	printf("\n\n后序遍历：");
	postOrderTraverse(tree);

	printf("\n\n二叉树的深度为：%d", depthBinaryTree(tree));
	printf("\n\n二叉树的结点总数为：%d", countBinaryTree(tree));
	printf("\n\n二叉树的叶子结点数为：%d\n", countLeafBinaryTree(tree));
}

运行截图：

5.5.2 线索二叉树

利用二叉链表中的空指针域：

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继

为了区分leftChild和rightChild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域 LeftTag和rightTag，并约定：

LeftTag = 0 leftChild指向该结点的左孩子
LeftTag = 1 leftChild指向该结点的前驱
rightTag= 0 rightChild指向该结点的右孩子
rightTag = 1 rightChild指向该结点的后继

typedef struct threadedBinaryTreeNode {
	char data;									// 数据域
	int leftTag;								// 左标志
	struct threadedBinaryTreeNode* leftChild;	// 左孩子
	int rightTag;								// 右标志
	struct threadedBinaryTreeNode* rightChild;	// 右孩子
}threadedBinaryTreeNode, * threadedBinaryTree;;

例：

5.6 树和森林

5.6.1 树的存储结构

双亲表示法

特点：找双亲容易，找孩子难

#define MAX_TREE_SIZE 100

typedef struct {
	char data;		// 数据域
	int parent;		// 双亲位置
}parentTreeNode;

typedef struct {
	parentTreeNode nodes[MAX_TREE_SIZE];// 双亲表示法的节点
	int r;								// 根的位置
	int num;							// 节点数
}parentTree;

孩子链表

特点：找孩子容易，找双亲难

typedef struct childTreeNode {
	char data;					// 数据域
	struct childTreeNode* next;	// 第一个孩子
}*childPtr;


typedef struct {
	char data;				// 数据域
	childPtr firstChild;	// 第一个孩子
}childLink;


typedef struct {
	childLink nodes[MAX_TREE_SIZE];	// 孩子表示法的节点
	int r;							// 根的位置
	int num;						// 节点数
}childTree;

也可以将双亲表示法和孩子链表结合

这种我们称为带双亲的孩子链表

孩子兄弟表示法

又称二叉树表示法，二叉链表表示法

实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

typedef struct childSiblingTreeNode {
	char data;									// 数据域
	struct childSiblingTreeNode* firstChild;	// 第一个孩子
	struct childSiblingTreeNode* nextSibling;	// 下一个兄弟
}childSiblingTreeNode, * childSiblingTree;

5.6.2 森林与二叉树的转换

将树转换为二叉树进行处理，利用二叉树的算法来实现对树的操作

由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系

树转换成二叉树

加线：在兄弟之间加上一根连线
抹线：对于每个结点，除了其左孩子，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转45°

树变二叉树：兄弟相连留长子

/*******************************************************************************************************************************
 * @description：将树转换为二叉树
 * @param：tree
 * @param：binaryTree
 * @return：
 */
status convertTreeToBinaryTree(childSiblingTree tree, linkBinaryTree* binaryTree) {
	if (tree == NULL) {
		return ERROR;
	}
	// 申请根节点
	*binaryTree = (linkBinaryTree)malloc(sizeof(binaryNode));
	if (*binaryTree == NULL) {
		return OVERFLOW;
	}
	// 根节点赋值
	(*binaryTree)->data = tree->data;

	if (tree->firstChild != NULL) {
		convertTreeToBinaryTree(tree->firstChild, binaryTree);
	}
	else {
		(*binaryTree)->leftChild = NULL;
	}

	if (tree->nextSibling != NULL) {
		convertTreeToBinaryTree(tree->nextSibling, binaryTree);
	}
	else {
		(*binaryTree)->rightChild = NULL;
	}
	return OK;
}

二叉树转换成树

加线：若p结点是双亲结点的左孩子，则将p的右孩子，有孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列，形成树结构

二叉树变树：左孩右右连双亲，去掉原来右孩线

/*******************************************************************************************************************************
 * @description：将二叉树转换为树
 * @param：binaryTree
 * @param：tree
 * @return：
 */
status convertBinaryTreeToTree(linkBinaryTree binaryTree, childSiblingTree* tree) {
	if (binaryTree == NULL) {
		return ERROR;
	}
	// 申请根节点
	*tree = (childSiblingTree)malloc(sizeof(childSiblingTreeNode));
	if (*tree == NULL) {
		return OVERFLOW;
	}
	// 根节点赋值
	(*tree)->data = binaryTree->data;

	if (binaryTree->leftChild != NULL) {
		convertBinaryTreeToTree(binaryTree->leftChild, &((*tree)->firstChild));
	}
	else {
		(*tree)->firstChild = NULL;
	}

	if (binaryTree->rightChild != NULL) {
		convertBinaryTreeToTree(binaryTree->rightChild, &((*tree)->nextSibling));
	}
	else {
		(*tree)->nextSibling = NULL;
	}
	return OK;
}

森林转换为二叉树

将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

森林变二叉树：树变二叉根相连

二叉树转换成森林

抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树

二叉树变森林：去掉全部右孩线，孤立二叉再还原

5.6.3 树和森林的遍历

树的先根遍历

若树不为空，则先访问根结点，然后依次先根遍历各棵子树

和二叉树前序遍历一样

/*******************************************************************************************************************************
 * @description：树的先根遍历
 * @param：tree
 */
void preOrderTraverseTree(childSiblingTree tree) {
	if (tree == NULL) {
		return;
	}
	printf("%c", tree->data);
	preOrderTraverseTree(tree->firstChild);
	preOrderTraverseTree(tree->nextSibling);
}

树的后根遍历

若树不空，则先依次后根遍历各棵子树，然后访问根结点

/*******************************************************************************************************************************
 * @description：树的后根遍历
 * @param：tree
 */
void postOrderTraverseTree(childSiblingTree tree) {
	if (tree == NULL) {
		return;
	}
	postOrderTraverseTree(tree->firstChild);
	printf("%c", tree->data);
	postOrderTraverseTree(tree->nextSibling);
}

树的层次遍历

若树不空，则自上而下自左至右访问树中每个结点

和二叉树层次遍历一样使用队列

/*******************************************************************************************************************************
 * @description：树的层次遍历
 * @param：tree
 */
void levelOrderTraverseTree(childSiblingTree tree) {
	if (tree == NULL) {
		return;
	}
	// 申请队列
	suquenQueue queue;
	initSequenQueue(&queue);
	// 根节点入队
	enSequenQueue(&queue, tree);
	// 队列不为空
	while (queue.front != queue.base) {
		// 出队
		childSiblingTree node;
		deSequenQueue(&queue, &node);
		// 访问
		printf("%c", node->data);
		// 孩子节点入队
		if (node->firstChild != NULL) {
			enSequenQueue(&queue, node->firstChild);
		}
		// 兄弟节点入队
		if (node->nextSibling != NULL) {
			enSequenQueue(&queue, node->nextSibling);
		}
	}
}

森林的遍历

将森林看作由三部分构成：

森林中第一棵树的根结点
森林中第一棵树的子树森林
森林中其它树构成的森林

先根遍历

若森林不空，则：

访问森林中第一颗树的根结点
先序遍历森林中第一棵树的子树森林
先序遍历森林中（除第一棵树之外）其余树构成的森林

中序遍历

若森林不空，则：

中序遍历森林中第一棵树的子树森林
访问森林中第一颗树的根结点
中序遍历森林中（除第一棵树之外）其余树构成的森林

即：依次从左至右对森林中的每一棵树进行后根遍历

5.7 哈夫曼树及其应用

5.7.1 哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

结点的路径长度：两结点间路径上的分支数

树的路径长度：从树根到每一个结点的路径长度之和。记作：TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

权(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权

结点的带权路径长度：从根节点到该节点之间的路径长度与该结点的权的乘积

树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为WPL

哈夫曼树：最优树，带权路径长度（WPL）最短的树

注：“带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等

因此哈夫曼树又称最优二叉树

5.7.2 哈夫曼树的构造算法

构造算法：

构造森林全是根
选用两小造新树
删除两小添新人
重复2、3剩单根

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点

包含n个叶子结点的哈夫曼树中共有2n-1个结点

总结：

在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树
经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点

可见：哈夫曼树中共有n+n-1 = 2n-1个结点，且其所有的分支结点的度均不为1

算法的实现

采用顺序存储结构——一维结构数组

typedef struct {
	int weight;		// 权值
	int parent;		// 父结点
	int leftchild;	// 左孩子
	int rightchild; // 右孩子
}HTNode, * HuffmanTree;

初始化HT[1……2n-1]：leftchild=rightchild=parent=0；
输入初始n个结点：置HT[1……n]的weight的值
进行以下n-1次合并，依次产生n-1个结点HT[i]，i=n+1……2n-1

在HT[1……i-1]中选两个未被选过（从parent == 0的结点中选）的weight最小的两个结点HT[s1]和HT[s2]，s1、s2为两个最小结点下标
修改HT[s1]和HT[s2]的parent值：HT[s1].parent=i; HT[s2].parent=i;
修改新产生的HT[i]：

HT[i].weight = HT[s1].weight + HT[s2].weight
HT[i].leftchild = s1; HT[i].rightchild = s2;

/*******************************************************************************************************************************
 * @description：选择HT[1...n]中parent为0且weight最小的两个结点，其序号分别为s1和s2
 * @param：HT
 * @param：n
 * @param：s1
 * @param：s2
 */
static void select(HuffmanTree HT, int n, int* s1, int* s2)
{
	int min1 = 0, min2 = 0;
	for (int i = 1; i <= n; i++) {
		if (HT[i].parent == 0) {
			if (min1 == 0) {
				min1 = i;
			}
			else if (min2 == 0) {
				min2 = i;
			}
			else {
				if (HT[i].weight < HT[min1].weight) {
					min2 = min1;
					min1 = i;
				}
				else if (HT[i].weight < HT[min2].weight) {
					min2 = i;
				}
			}
		}
	}
	*s1 = min1;
	*s2 = min2;
}






/*******************************************************************************************************************************
 * @description：构造Huffman树
 * @param：HT
 * @param：w
 * @param：n
 */
void createHuffmanTree(HuffmanTree HT, int* w, int n)
{
	if (n <= 1) {
		return;
	}
	int m = 2 * n - 1;	// 结点总数
	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));

	// 初始化
	for (int i = 1; i <= m; i++) {
		HT[i].parent = 0;
		HT[i].leftchild = 0;
		HT[i].rightchild = 0;
	}

	// 给前n个结点赋权值
	for (int i = 1; i <= n; i++) {
		HT[i].weight = w[i - 1];
	}

	// 合并产生n-1个结点——构造Huffman树
	for (int i = n + 1; i <= m; i++) {
		// 在HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
		int s1, s2;
		select(HT, i - 1, &s1, &s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].leftchild = s1;
		HT[i].rightchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;

	}
}

5.7.3 哈夫曼编码

统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）
利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点路径越短
在哈夫曼树的每个分支上标上0或1：

结点的左分支标0，右分支标1
把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码

两个问题：

1.为什么哈夫曼编码能够保证是前缀编码？

因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀

2.为什么哈夫曼编码能够保证字符编码总长最短？

因为哈夫曼树的带权路径长度最短，故字符编码的总长最短

编码的实现

/*******************************************************************************************************************************
 * @description：从叶子到根逆向求每个字符的哈夫曼编码
 * @param：HT
 * @param：HC
 * @param：n
 */
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n)
{
	*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
	char* cd = (char*)malloc(n * sizeof(char));
	cd[n - 1] = '\0';
	for (int i = 1; i <= n; i++) {
		int start = n - 1;
		int c = i;
		int p = HT[i].parent;
		while (p != 0) {
			--start;
			if (HT[p].leftchild == c) {
				cd[start] = '0';
			}
			else {
				cd[start] = '1';
			}
			c = p;
			p = HT[p].parent;	// 继续向上回溯
		}
		(*HC)[i] = (char*)malloc((n - start) * sizeof(char));
		strcpy((*HC)[i], &cd[start]);
	}
	free(cd);
}

5.8 案例分析与实现

5.8.1 文件的编码与解码

明文

编码

输入各字符及其权值
构造哈夫曼树——HT[i]
进行哈夫曼编码——HC[i]
查HC[i]，得到各字符的哈夫曼编码

解码

构造哈夫曼树
依次读入二进制码
读入0，则走向左孩子；读入1，则走向右孩子
一旦到达某叶子时，即可译出字符
然后再从根出发继续译码，直到结束

上一篇：「更新完毕」学习数据结构——第七章:排序
下一篇：数据结构-树论数据结构树的基本概念

网站首页 > 技术文章 正文

数据结构——第5章-树和二叉树 数据结构树和二叉树思维导图

5.1 树和二叉树的定义

5.1.1 树的定义

5.1.2 树的基本术语

5.1.3 二叉树的定义

5.2 案例引入

5.2.1 数据压缩问题

5.2.2 利用二叉树求解表达式的值

5.3 树和二叉树的抽象数据类型定义

5.4 二叉树的性质和存储结构

5.4.1 二叉树的性质

满二叉树

完全二叉树

5.4.2 二叉树的存储结构

顺序存储结构

链式存储

5.5 遍历二叉树和线索二叉树

5.5.1 遍历二叉树

先序遍历

中序遍历

后序遍历

中序遍历非递归算法

层次遍历

先序遍历建立二叉树

复制二叉树

计算二叉树深度

计算结点总数

计算叶子结点总数

测试代码

5.5.2 线索二叉树

5.6 树和森林

5.6.1 树的存储结构

双亲表示法

孩子链表

孩子兄弟表示法

5.6.2 森林与二叉树的转换

树转换成二叉树

二叉树转换成树

森林转换为二叉树

二叉树转换成森林

5.6.3 树和森林的遍历

树的先根遍历

树的后根遍历

树的层次遍历

森林的遍历

5.7 哈夫曼树及其应用

5.7.1 哈夫曼树的基本概念

5.7.2 哈夫曼树的构造算法

算法的实现

5.7.3 哈夫曼编码

编码的实现

5.8 案例分析与实现

5.8.1 文件的编码与解码

编码

解码

猜你喜欢

本文暂时没有评论，来添加一个吧(●'◡'●)

取消回复欢迎 你 发表评论:

网站首页 > 技术文章正文

数据结构——第5章-树和二叉树数据结构树和二叉树思维导图

取消回复欢迎你发表评论: