导图社区 第四章树
第四章树的思维导图,树(Tree)是n(n≥0)个结点构成的有限集合。当n=0时,称为空树;对于任棵非空树(n>0)。
编辑于2023-06-02 20:26:57 山东省第四章树
树
定义:树(Tree)是n(n≥0)个结点构成的有限集合。当n=0时,称为空树;对于任棵非空树(n>0)
性质
(1)树中有一个称为“树根"(Root)的特殊结点,用r表示
(2)其余结点可以划分为m个不相交的子集T,,T,,…,Tm。任何子集T(ie[1,m])也是一个树,称为根结点r的“子树"(SubTree)。每个子树的根结点都与r有一条相连接的边,r是这些子树根结点的“父结点”(Parent)。
基本术语
1.结点的度(Degree):一个结点的度是其子树的个数
2.树的度:树的所有结点中最大的度数
3.叶结点(Leal ):是度为0的结点。叶结点也可称为端结点
4.父结点(Parent) :具有于树的结点是其子树的根结点的父结点
5.子结点(Child):与父结点相反,对于某一个结点来讲,其子树的根结点是它的子结点
6.兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点
7.祖先结点(Ancestor ):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点
8.子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙
9.结点的层次(Level)!规定根结点在1层,其他任一结点的层数是其父结点的层数加1
10.树的深度(Depth):树中所有结点中的最天层次是这棵树的深度。树的高度(Height)跟深度是一样的,只不过是自底向上计数。叶结点的高度规定为1,其他任一结点的高度层数是其所有子结点的最大高度层数加1。树的高度就是其根结点的高度。
11.分支:树中两个相邻结点的连边称为一个分支
12.路径和路径长度:从结点n,到n,的路径被定义为一个结点序列n,,n ,…, n ,对于1≤i<k,n,是n,,的父结点。一条路径的长度为这条路径所包含的边(分支)的个数
二叉树
二叉树的概念和性质
定义
二叉树是一个有限的结点集合,这个集合或者为空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
度为2的树中至少有—个结点的度为2,而二叉树没有这种要求度为2的树不区分左、右子树,而二叉树是严格区分左右子树的
集中在二叉树的最下—层,这样的二叉树称为满二叉树
满二叉树
在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶子结点都集中在二叉树的最下一层
非空满二叉树
叶子结点都在最下—层,只有度为0和度为2的结点
完全二叉树
若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶子结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树
非空完全二叉树
叶子结点只可能在最下面两层中出现对于最大层次中的叶子结点,都依次排列在该层最左边的位置上,如果有度为1的结点,只可能有一个,且该结点只有左孩子而无右孩子;按层序编号时,一旦出现编号为i的结点是叶子结点或只有左孩子,则编号大于i的结点均为叶子结点,当结点总数n为奇数时,n1=0,当结点总数为偶数时,n1=1
二叉树的表示方法
树形表示法
文氏图表示法
凹入表示法
条形表示法
二叉树的性质
非空二叉树上的叶子结点数等于双分支结点数加1
非空二叉树的第i层上最多有2的i-1次方个结点(i>=1)
高度为h的二叉树最多有2的h次方-1个结点(h>=1)
二叉树与树、森林之间的转换
森林、树转换为二叉树
若某结点是其双亲的左孩子,则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来
删除原二叉树中所有双亲结点与右孩子结点之问的连线
整理由前两步得到的树,以根结点为轴心,逆时针转动45°,使之结构层次分明
实际上,二叉树的还原就是将二叉树中的左分支保持不变,将二叉树中的右分支还原成兄弟关系
二叉树还原为树/森林
抹掉二叉树根结点右链上的所有结点之间的“双亲--右孩子”关系,将其分成若干个以右链上的结点为根结点的二叉树,设这些二叉树为bt1、bt2、......btm.
分别将bt1、bt2、.......btm各自还原成—棵树
存储结构
顺序存储结构
二叉树的顺序存储结构是用—组地址连续的存储单元来存放二叉树的数据元素,因此必须确定好树中各数据元素的存放次序,使得各数据元素在这个存放次序中的相互位置能反映出数据元素之间的逻辑关系
链式存储结构
二叉树的链式存储结构是指用一个链表来存储一棵二叉树,二叉树中的每一个结点用链表中的一个结点来存储
data表示值域,用于存储对应的数据元素,Ichild和rchild分别表示左指针域和右指针域,分别用于存储左孩子结点和右孩子结点的存储地址。这种链式存储结构通常简称为二叉链
基本运算及其实现
创建二叉树CreateBTree(b,str)销毁二叉树DestroyBTree(&b)
查找结点FindNode(b,x)
找孩子结点LchildNode(p)和RchildNode(p)
求高度BTHeight(b)输出二叉树DispBTree(b)
遍历
先序遍历
中序遍历
后序遍历
层次遍历
层次遍历不同于前三种,它是非递归的,用于一层一层的访问二叉树中的所有结点
构造
任何n(n>0)个不同节点的二叉树,都可由它的中序序列和后序序列唯一地确定
线索二叉树
规定是当某结点的做指针为空时,令该指针指向这个线性序列中该结点的前驱结点;当某结点的右指针为空时,令该指针指向这个线性序列中该结点的后继结点,这样的指向该线性序列中的“前驱结点”和“后继结点”的指针称为线索。
创建线索的过程称为线索化。线索化的二叉树称为线索二叉树
—般分类有先序线索二叉树、中序线索二叉树、后序线索二叉树
创建线索二叉树的目的是提高该遍历过程的效率
哈夫曼树
概述
带权路径长度
将树中的结点赋予一个某种意义的数值,称此数值为该结点的权。从根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(Weighted PathLength,WPL)。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度
哈夫曼树(最优二叉树)
在n0个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树称为哈夫曼树(Huffman tree)或最优二叉树
哈弗曼编码
在数据通信中,将传送的文字转换成二进制字符0和1组成的二进制字符串,称这个过程为编码。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案
设需要编码的字符集合为{d1,d2,…,dn},各个字符在电文中出现的次数集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶子结点,以w1,w2,…,wn作为各根结点到每个叶子结点的权值构造一棵哈夫曼树,规定哈夫曼树中的左分支为0、右分支为1,则从根结点到每个叶子结点所经过的分支对应的0和1组成的序列便是该结点对应字符的编码。这样的编码称为哈夫曼编码。
哈夫曼编码的实质就是使用频率越高的字符采用越短的编码。