树的定义及概念:

  • 树是具有相同特性的数据元素的集合,若树为空集,则称为空树。在树中存在唯一的称为根的数据元素root;当n>1时,其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树。(递归定义)
  • 有且仅有一个结点没有前驱结点,这个结点称作树的根结点。
  • 除根结点外,树中的每个结点有且仅有一个前驱结点,但可以有多个后继结点。树中可以有多个终端结点。

树的表示法:

树形表示法:这是树的最基本的表示,使用一棵倒置的树表示树结构,

文氏图表示法:使用集合以及集合的包含关系描述树结构。

凹入表示法:使用线段的伸缩关系描述树结构。

广义表表示法:将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号分隔。

树的结点:包含一个数据元素及若干指向其子树的分支。

结点的度:树中每个结点具有的子树数或者后继结点数称为该结点的度。

树的度:树中所有结点的度的最大值称之为树的度。

分支结点:度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点,度为2的结点称为双分支结点。

叶子结点:度为零的结点称为叶子结点或终端结点。

孩子结点:一个结点的后继称之为该结点的孩子结点。

双亲结点:一个结点称为其后继结点的双亲结点(或父亲结点)。

子孙结点:一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。

祖先结点:从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点(不含该结点自身)。

兄弟结点:具有同一双亲的结点互相称之为兄弟结点。

结点层次:树具有一种层次结构,根结点为第一层,其孩子结点为第二层,如此类推得到每个结点的层次。

树的高度:树中结点的最大层次称为树的高度或深度。

森林:零棵或多棵互不相交的树的集合称为森林。

有序树:子树之间存在确定的次序关系。

无序树:子树之间不存在确定的次序关系。

二叉树

二叉树的递归定义:

  • 二叉树或者是一棵空树。
  • 或者是一棵由一个根结点和两棵互不相交的分别称做根结点的左子树和右子树所组成的非空树。
  • 左子树和右子树又同样都是一棵二叉树。
  • 二叉树与度为2的树是不同的,度为2的树至少有3个结点,而二叉树的结点数可以为0。度为2的树不区分子树的次序,而二叉树中的每个结点最多有两个孩子结点,且必须要区分左右子树,即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
  • 二叉树的5种形态

满二叉树:深度为k 且有2k-1个结点的二叉树。在满二叉树中,每层结点都是满的,即每层结点都具有最大结点数。满二叉树的顺序表示,即从二叉树的根开始,层间从上到下,层内从左到右,逐层进行编号(1,2, …, n)。

完全二叉树:深度为k,结点数为n的二叉树,如果其结点1~n 的位置序号分别与满二叉树的结点1~n 的位置序号一一对应,除第k 层外,其它各层(1~k-1) 的结点数都达到最大个数,第k 层从右向左连续缺若干结点,这就是完全二叉树。满二叉树必为完全二叉树, 而完全二叉树不一定是满二叉树。

二叉树的性质:

  1. 若二叉树的层次从1开始, 则在二叉树的第i 层最多有2i-1个结点。( i≥1)
  2. 高度为k的二叉树最多有2k-1个结点。(h≥1)
  3. 对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0=n2+1。
  4. 具有n(n≥0)个结点的完全二叉树的高度为⌈ log2(n+1) ⌉,或 ⌊ log2n ⌋ +1(当n=0不适用)。若设完全二叉树中叶结点有n0个, 则该二叉树总的结点数为n = 2n0, 或n = 2n0 –1。若完全二叉树的结点数为奇数,没有度为1的结点,偶数有一个度为1的结点。
  5. 如将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号: 1, 2, …, n,则有以下关系:若i = 1, 则i 为树的根结点,无双亲;若i > 1, 则i 的双亲为 ⌊ i/2 ⌋ 。若2i <= n, 则i 的左孩子为2i,否则没有左孩子。若2i+1 <= n, 则i 的右孩子为2i+1;否则没有右孩子。

二叉树的顺序存储:就是用一组连续的存储单元存放二叉树中的结点。

完全二叉树或满二叉树的顺序存储:由性质5可得,用一维数组按从上到下、从左到右的顺序存储树中所有结点值,通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。完全二叉树或满二叉树采用顺序存储结构比较合适,既能够最大可能地节省存储空间,又可以利用数组元素的下标确定结点在二叉树中的位置以及结点之间的关系。

一般二叉树的顺序存储:先增添空结点补齐为一棵完全二叉树,再对所有结点进行编号仅保留实际存在的结点值,其他为空。对于一般二叉树,如果它接近于完全二叉树形态,需要增加的空结点个数不多,也可适合采用顺序存储结构。

C语言描述如下:

#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
// 0号单元存储根结点
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
//TElemType为二叉树中结点的数据值类型
//MAX_TREE_SIZE为顺序表的最大长度
//将下标为0的单元存放根结点的下标,值为空的结点为空结点

二叉树的链式存储结构:二叉链表表示、三叉链表表示。

二叉链表表示
三叉链表表示

在二叉链表中:

  • n个结点有 2n个指针域
  • 分支数为n-1的非空指针域有n-1个
  • 空指针域个数= 2n-(n-1) = n+1

C语言描述如下:

// ----- 二叉树的二叉链表存储表示------
typedef struct BiTNode {
TElemType data;
BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;
//data表示数据域,用于存储放入结点值(默认情况下为单个字
母)。
//lchild和rchild分别表示左指针域和右指针域,分别存储左
孩子和右孩子结点(即左、右子树的根结点)的存储地址。
//当某结点不存在左或右孩子时,其lchild或rchild指针域取
特殊值NULL。

二叉树的遍历:按一定的次序访问树中的所有结点,使每个结点恰好被访问一次。其中遍历次序保证了二叉树上每个结点均被访问一次且仅有一次。二叉树常用的遍历有先序(根)遍历、中序(根)遍历、后序(根)遍历。区别在于访问根结点的顺序。(二叉树非空)

先序遍历(DLR):

//先序遍历序列的特点:其第一个元素值为二叉树中根结点值。
void PreOrder(BiTNode* bt)
{
	if (bt != NULL)
	{
		//访问根结点
		printf("%c ", bt->data);
		//先序遍历左子树
		PreOrder(bt->lchild);
		//先序遍历右子树
		PreOrder(bt->rchild);
	}
}

中序遍历(LDR):

//中序遍历序列的特点:若已知二叉树的根结点值,以该值为界,将中序遍历序列分为两部分,前半部分为左子树的中序遍历序列,后半部分为右子树的中序遍历序列。
void InOrder(BiTNode* bt)
{
	if (bt != NULL)
	{
		//中序遍历左子树
		InOrder(bt->lchild);
		//访问根结点
		printf("%c ", bt->data);
		//中序遍历右子树
		InOrder(bt->rchild);
	}
}

后序遍历(LRD):

//后序遍历序列的特点:最后一个元素值为二叉树中根结点值。
void PostOrder(BiTNode* bt)
{
	if (bt != NULL)
	{
		//后序遍历左子树
		PostOrder(bt->lchild);
		//后序遍历右子树
		PostOrder(bt->rchild);
		//访问根结点
		printf("%c ", bt->data);
	}
}

线索二叉树:对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域。利用这些空链域存放在某种遍历次序(线性序列)下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。线索二叉树分为先序、中序和后序线索二叉树。

先序线索二叉树

线索二叉树的存储:在原二叉链表中增加了ltag和rtag两个标志域。

enum PointerTag {Link, Thread}; // Link(0):指针,Thread(1):线索
struct BiThrNode {
	TElemType data;
	BiThrNode *lchild, *rchild; // 左右孩子指针
	PointerTag LTag, RTag; // 左右标志
};
typedef BiThrNode *BiThrTree;
//ltag= 0 表示lchild指向结点的左孩子
//	1 表示lchild指向结点的前驱结点即为线索
//rtag= 0 表示rchild指向结点的左孩子
//	1 表示rchild指向结点的后继结点即为线索

二叉树线索化:在遍历过程中,检查当前结点的左、右指针域是否为空;如果为空,将它们改为指向前驱结点或后继结点的线索。

树与森林

树的度与结点关系:

  • 由二叉树可得m叉树的结点数等于分支数加1,B+1=n
  • 由二叉树的性质引申出,对于任何一颗树T,如果其终端结点树为n0度为i的结点数为ni,则n0=1+n2+2n3+···+(i-1)ni

树的双亲存储:是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个下标(伪指针)指示其双亲结点的位置。利用了每个结点(除根以外)只有惟一的双亲的性质。求结点的孩子时需要遍历整个结构。

C语言描述如下:

#define MAX_TREE_SIZE 100
struct PTNode {
	TElemType data;
	int parent; // 双亲位置域
};
struct PTree {
	PTNode nodes[MAX_TREE_SIZE];
	int r, n; // 根的位置、结点数
};

孩子表示法:由于树中每个结点可能有多棵子树,则可用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,此时链表中的结点可以有定长结点链表存储结构、孩子链表存储结构、孩子兄弟表示法。

  • 定长结点链表存储结构:孩子链表存储结构可按树的度(即树中所有结点度的最大值)设计结点的孩子结点指针域个数。空指针域:n(k-1)+1
  • 孩子链表存储结构:把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表作存储结构,則n个结点有n个孩子链表(叶子的孩子链表为空表),而n个头指针又组成一个线性表,为了便于査找,可采用顺序存储结构。
  • 孩子兄弟表示法:又称二叉树表示法,或二叉链表表示法。以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点,分别命名为firstchild域和nextsibling域。

树转换为二叉树:(左孩子右兄弟)

  • 树中所有相邻兄弟之间加一条连线
  • 对树中的每个结点,只保留它与第一个孩子结点之间的连线,删除它与其他孩子结点之间的连线;
  • 以树的根结点为轴心,将整棵树顺时针转动45度,使之结构层次分明。

森林转换为二叉树:

  • 将森林中的每棵树转换成相应的二叉树。
  • 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点,当所有二叉树连在一起后,此时所得到的二叉树就是由森林转换得到的二叉树。

树和森林的遍历:按某种方式访问树中的每一个结点且每一个结点只被访问一次。有两种遍历方法:先根遍历、后根遍历。先根和后根遍历算法都是递归的。

先根遍历:若树不空,则先访问根结点,然后依次先根遍历各棵子树。森林的前序遍历和二叉树的前序遍历相同。

后根遍历:若树不空,则先依次后根遍历各棵子树,然后访问根结点。森林的后根遍历和二叉树中序遍历相同。

哈夫曼树(最优二叉树):给定一组具有确定权值的叶子结点,可以构造出许多形状的二叉树。它们的带权路径长度可能不相同。把其中具有最小带权路径长度的二叉树称为哈夫曼树。

路径长度 :二叉树具有n个带权值的叶子结点,从根结点到每个叶子结点都有一个路径长度。

带权路径长度:从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和称为该二叉树的带权路径长度(WPL)。

构造哈夫曼树:根据哈夫曼树的定义,一棵二叉树要使其WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。n个叶子结点的可以构造2n – 1个结点的二叉树

哈夫曼算法过程:

  1. 由给定的n个权值{w1,w2,…,wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树的集合F={T1,T2,…,Tn}。
  2. 在F中选取根结点的权值最小和次小的两棵二叉树Ti、Tj进行合并,即增加一个根结点,将Ti、Tj分别作为它的左、右子树,该根结点的权值为其左、右子树根结点权值之和。
  3. 重复步骤2,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。

哈夫曼编码:利用哈夫曼树构造的用于通信的长度不等的,出现次数较多的字符采用尽可能短的二进制编码。

前缀编码:若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称做前缀编码。

构造哈夫曼编码:

  • 用给定的若干字符的频度为权值生成哈夫曼树,并在每个叶子上注明对应的字符。
  • 树中从根到每个叶子都有一条路径,对路径上的各分支约定指向左子树根的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码。
最后修改日期:2020年3月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据