建站网站模板下载,企业名录怎么导出,先做公众号在做网站,沈阳男科医院哪家好点儿一、树的定义
树#xff08;Tree#xff09;是n#xff08;n0#xff09;个结点的有限集。 n0又称为空树。在任意一课非空的树中#xff1a;#xff08;1#xff09;有且仅有一个特定的称为跟#xff08;Root#xff09;的结点#xff1b;#xff08;2#xf…一、树的定义
树Tree是nn0个结点的有限集。 n0又称为空树。在任意一课非空的树中1有且仅有一个特定的称为跟Root的结点2当n1时其余结点可分为mm0个互不相交的有限集其中每一个集合本身又是一棵树并且称为根的子树SubTree。 树是一种一对多的数据结构。 需要注意的是 1当n0时根结点是惟一的不可能存在多个根结点。 2m0时子树的个数没有限制但它们一定是互不相交的。如果相交就不符合树的定义。 结点分类 结点拥有的子树称为结点的度。度为0的结点称为叶结点或终端结点度不为0的结点称为非终端结点或分支结点。除根结点外分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图所示树的最大结点是D的度为3则树的度也为3. 树中结点最大的层次称为树的深度或高度。 如果将树中结点的各子树看成从左到右是有次序的不能互换的则称该树为有序树否则称为无序树。 森林是mm0棵互不相交的树的集合。
二、树的存储结构
简单的顺序存储结构和链式存储结构表示不了树一对多的关系。试想数据元素挨个的存储谁是谁的双亲谁是誰的孩子呢 树有自己的三种不同表示法双亲表示法、孩子表示法、孩子兄弟表示法。 1. 双亲表示法 在每个结点中附设一个指示器指示双亲结点在数组中的位置。结点结构表如下。
dataparent
其中data是数据域存储结点的数据信息。而parent是指针域存储该结点的双亲在数组的下标。 标出双亲左右结点则构成树。 2. 孩子表示法 先介绍一种多种链表表示法每个结点有多个指针域其中每个指针指向一棵子树的根结点。 方案一 指针域的个数就等于树的度。
datachild1child2child3……childd
其中data是数据域child1到childd是指针域用来指向该结点的孩子结点。对于图6-4-1的树来说树的度是3所以指针域的个数是3。如下图。 这种方法对于树中各结点的度相差很大是显然是浪费空间的因为有很多的结点它的指针域都是空的。不过如果树的各结点度相差很小时那就意味着开辟的空间被充分利用了这时存储结构的缺点反而变成了优点。 为了按需分配空间我们考虑方案二。 方案二 每个结点指针域的个数等于该结点的度。
datadegreechild2child2……childd
其中data是数据域degree为度域也就是存储该结点的孩子结点的个数child1到childd为指针域指向该结点的各孩子结点。如下图。 这种方案也有缺点就是会给结点的维护带来麻烦。所以我们提出孩子表示法。 孩子表示法 把每个结点的孩子结点排列起来以单链表作存储结构则n个结点有n个孩子链表如果是叶子结点则次单链表为空。然后n个头指针又组成一个线性表采用顺序存储结构存放进一个一维数组中。如下图。 为此设计两种结点结构一个是孩子链表的孩子结点如下图。
childnext
其中child是数据域用来存储某个结点在表头数组的下标。next是指针域用来存储指向某结点的下一个孩子结点的指针。 另一个是表头数组的表头结点如下表。
datafirstchild
其中data是数据域存储某结点的数据信息。firstchild是头指针域存储该结点的孩子链表头指针。 但是这种方法也找不到某个结点的双亲。于是有了双亲孩子表示法。如下图。 3. 孩子兄弟表示法 任意一棵树它的结点的第一个孩子如果存在就是唯一的它的右兄弟如果存在也是唯一的。因此我们设置两个指针分别指向该结点的第一个孩子和词结点的右兄弟。
datafirstchildrightsib
其中data是数据域firstchild为指针域存储该结点的第一个孩子结点的存储地址rightsib是指针域存储该结点的右兄弟结点的存储地址。如下图。
三、二叉树的定义
二叉树Binary Tree是nn0个结点的有限集合该集合或者为空集称为空二叉树或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 二叉树的特点
每个结点最多有两棵子树所以二叉树中不存在大于2的结点。注意不是只有两棵子树而是最多有。没有子树或者有一棵子树都是可以的。左子树和右子树是有顺序的次序不能颠倒。就像人的左右手。即使树中某结点只有一棵子树也要区分它是左子树还是右子树。 二叉树有5种基本形态 空二叉树。只有一个根结点。根结点只有左子树。根结点只有右子树。根结点既有左子树又有右子树。 斜树只有左子树或者只有右子树。是一种特殊的线性表。 满二叉树所有分支结点都存在左子树和右子树并且所有叶子都在同一层上。 满二叉树的特点有 叶子只能在最下一层。出现在其他层就不可能达到平衡。非叶子结点的度一定是2。否则就是“缺胳膊少腿了”。在同样深度的二叉树中满二叉树的结点个数越多叶子树越多。 完全二叉树 叶子结点只能在最下两层。最下层的叶子一定集中在左部连续的位置。倒数第二层若有叶子结点一定都在右部连续位置。如果结点度为1则该结点只有左孩子即不存在右子树的情况。同样结点数从二叉树完全二叉树的深度最小。 判断一棵树是否是完全二叉树心中默默给每个结点按照满二叉树的结构逐层顺序编号如果编号出现空档就不是完全二叉树否则就是。 满二叉树是特殊的完全二叉树。 完全二叉树必须先满足左后满足右缺的元素只能是满二叉树最下一层的高度差小于或等于1。
四、二叉树的存储结构
一顺序存储结构 一般只有完全二叉树才考虑顺序存储结构因为完全二叉树的严格性可以充分利用顺序存储空间。其他二叉树都会造成空间的浪费特别是右斜树。 二二叉链表 二叉树每个结点最多有两个孩子所以为它设计一个数据域和两个指针域称为二叉链表。
lchilddatarchild
其中data是数据域lchild和rchild都是指针域分别存放指向左孩子和右孩子的指针。
五、遍历二叉树
二叉树的遍历traversing binary tree是指从根结点出发按照某种次序一次访问树中所有结点使得每个结点被访问一次且仅被访问一次。
前序遍历 根–左子树–右子树 中序遍历 左子树–根–右子树 后序遍历 左子树–右子树–根 层序遍历 根–第一层从左到右–第一层从左到右……
已知前序遍历序列和中序遍历序列可以唯一确定一棵二叉树。 已知后序遍历序列和中序遍历序列可以唯一确定一棵二叉树。 已知前序遍历序列和后序遍历序列不可以唯一确定一棵二叉树。
六、线索二叉树
为了充分利用二叉链表的空指针把空指针指向前驱和后继这种指向前驱和后继的指针称为线索加上线索的二叉链表称为线索链表相应的二叉树就称为线索二叉树。 对二叉树一某种次序比那里时期变为线索二叉树的过程称作是线索化。线索化的过程就是在遍历的过程中修改空指针的过程。 为了判别某一结点的lchild是指向左孩子还是前驱rchild是指向右孩子还是后继引入ltag和rtag两个标志域。
lchildltagdatartagrchild
其中ltag为0时指向该结点的左孩子为1时指向该结点的前驱rtag为0时指向该结点的右孩子为1时指向该结点的后继因为对6-10-1的图的二叉链表图可以修改如下图。 如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继那么采用线索二叉链表的存储结构就是不错的选择。
七、二叉树的性质
在一棵高度为k的二叉树中,结点总数为至多为2kk次方-1
八、树、森林与二叉树的转换
一树转化为二叉树 1. 加线。在所有兄弟结点之间加一条连线。 2. 去线。对树中每个结点只保留它与第一个孩子结点的连线删除它与其他孩子结点之间的连线。 3. 层次调整。以树的根结点为轴心将整棵树瞬时间旋转一定的角度。使之结构层次分明。之一第一个孩子是二叉树结点的左孩子兄弟转换过来的孩子是结点的右孩子。 二森林转换为二叉树 森林是由若干棵树组成的所以完全可以理解为森林中的每一棵树都是兄弟可以按照兄弟的处理办法来操作如下 1. 把每个树转换为二叉树 2. 第一棵树不动从第二棵二叉树开始依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子用连线连接起来。当多有的二叉树连接起来后就得到森林转化的二叉树。 三二叉树转换为树 二叉树转换为树是树转换为二叉树的逆过程。 1. 加线。若某结点的左孩子结点存在则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子的结点……哈反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。 2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。 3. 层次调整。使之结构层次分明。 四二叉树转换为森林 判断一棵树是否能转换为一棵树还是森林就看它是否有右结点若有就可以转为森林否则就是一棵树。 1. 从根结点开始若右孩子存在则把与右孩子结点的连线删除再查看分离后的二叉树若右孩子存在则连线删除……直到所有右孩子连线都删除为止得到分离的二叉树。 2. 再将每棵分离后的二叉树转换为树即可。 五树与森林的遍历 树的遍历分为两种方式 1. 一种是先根遍历树即先访问树的根结点然后依次先根遍历根的每棵子树。 2. 另一种是后根遍历即先依次后根遍历每棵子树然后再访问根结点。 森里的遍历方式也分为两种方式 1. 前序遍历先访问森林中第一棵树的根结点然后再依次先跟遍历根的每棵子树再依次用同样方式遍历除去每一棵树的剩余树构成的森林。 2. 后序遍历先访问森林中第一棵树后根遍历的方式遍历每棵子树然后再访问根结点再依次同样方式遍历除去第一棵树的剩余树构成的森林。 树和森林的遍历可参看三四图中的笔记。 神奇的是森林的前序遍历和二叉树的前序遍历结果相同森林的后序遍历和二叉树的中序遍历结果相同。这也就告诉我们当以二叉链表作树的存储结构时树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。
九、赫夫曼树
赫夫曼树带全路径长度WPL最小的二叉树。 先取最小权值的结点作为叶子结点逐级递增就能构造出哈夫曼树。把左结点标为0右结点标为1就能构造出赫夫曼编码。
十、题目
某棵完全二叉树上有699个节点则该二叉树的叶子节点数为350。 解析n0n21; nn0n1n2n0n1n0-1699 由于完全二叉树中度为1的节点只有0个或1个两种情况所以将0或1带入上面公式整理后得 n0n1/2或者n0n/2; 看看n是否能被2整除能则用n0n/2。否则用n0n1/2 既叶子节点为n0n1/2350。一棵有124个叶节点的完全二叉树最多有248 个节点。 解析n0 n2 1于是度为2的结点个数123个 完全二叉树中度为1结点个数最多1个 因此该完全二叉树中结点最多有123 1 124 248个
