前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构【第五章知识小结】

数据结构【第五章知识小结】

作者头像
MIKE笔记
发布2023-03-22 16:23:18
2530
发布2023-03-22 16:23:18
举报

文章目录


前言

提示:第五章知识小结:

1、树和二叉树的定义

结点:即树的数据元素

结点的度:结点挂接的子树数

结点的层次:从根到该结点的层数(根结点算第一层)

终端结点:即度为0的结点,即叶子

分支结点:即度不为0的结点(也称为内部结点)

树的度:所有结点度中的最大值

树的深度:指所有结点中最大的层数,也称树的高度

  1. 二叉树的性质

性质1: 在二叉树的第i层上至多有2i-1个结点

性质2: 深度为k的二叉树至多有2k-1个结点

性质3: 对于任何一棵二叉树,若度为2的结点数有n2个,则叶子数n0必定为n2+1 (即n0=n2+1)

性质4: 具有n个结点的完全二叉树的深度必为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IJ8nLdSK-1652529375276)(media/68d218db515ea1827d77a6925ef343ae.png)]

性质5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DgBBzBJq-1652529375277)(media/8458845ab29ecbe0fc8eae3dd487618d.png)]。

3、特殊形态的二叉树

满二叉树:一棵深度为k 且有2k -1个结点的二叉树。(特点:每层都“充满”了结点)

完全二叉树:深度为k 的,有n(n< 2k -1 )个结点的二叉树,当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。

只有最后一层叶子不满,且最后一层叶子全部集中在左边

  1. 二叉树的顺序存储

存储方法:按满二叉树的结点层次编号,依次存放二叉树中的数据元素。

优点:结点间关系蕴含在其存储位置中

缺点:浪费空间,仅适于存满二叉树和完全二叉树

  1. 遍历二叉树

先序遍历:DLR,即先根再左再右

中序遍历:LDR,即先左再根再右

后序遍历:LRD,即先左再右再根

结论:

1.若二叉树中各结点的值均不相同,则:

(1)由二叉树的前序序列和中序序列,或由其后序序列和中序序列均能唯一地确定一棵二叉树,

(2)但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

2.时间效率:O(n) //每个结点只访问一次

3.空间效率:O(n) //栈占用的最大辅助空间

5、线索二叉树

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

1)若结点有左子树,则lchild指向其左孩子;

否则, lchild指向其直接前驱(即线索);

2)若结点有右子树,则rchild指向其右孩子;

否则, rchild指向其直接后继(即线索)。

为了避免混淆,增加两个标志域

lchild

LTag

data

RTag

rchild

若LTag=0, lchild指向左孩子;若 LTag=1, lchild指向其前驱。

若RTag=0, rchild指向右孩子;若 RTag=1, rchild指向其后继。

6、树的存储结构

1.双亲表示法

用一组连续的存储单元存储树的结点。

每个结点包含一个数据域和一个指向双亲结点位置的指针域。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HO4VHCs0-1652529375278)(media/6590dca4b287088e3460455cfe089e58.png)]

2.孩子表示法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-biFs74Bp-1652529375279)(media/ae0e0b68a74b31b727adc9ff3a2ac5f6.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SnkEDxqr-1652529375279)(media/3ff93464a32fc86029ca75816df4e6a1.png)]

3.孩子双亲表示法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GTFkKJts-1652529375280)(media/ae0e0b68a74b31b727adc9ff3a2ac5f6.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Fo5zJJe0-1652529375280)(media/ee5f7cb4d59642516b1fcc8dd6c2b95b.jpeg)]

4.孩子兄弟表示法

firstchild

Data

nextsibling

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KMtzUZrG-1652529375280)(media/ae0e0b68a74b31b727adc9ff3a2ac5f6.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kRu8tEwc-1652529375281)(media/b5f1e9ea882aedd31f0cb261980de717.png)]

此处举个栗子

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DvzuXT43-1652529375281)(media/4b095d12eb8fec400ac7660bc2f9dfe9.png)]

7、哈夫曼树及其应用

路径:由一结点到另一结点间的分支所构成。

路径长度:路径上的分支数目,a→e的路径长度=2

带权路径长度:结点到根的路径长度与结点上权的乘积。

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

哈夫曼树:带权路径长度最小的树

哈夫曼编码的译码过程:

分解接收字符串:遇“0”向左,遇“1”向右;一旦到达叶子结点,则译出一个字符,反复由根出发,直到译码完成。

特点:每一码都不是另一码的前缀,绝不会错译! 称为前缀码

哈夫曼编码的总结:

1.哈夫曼编码是不等长编码。

2.哈夫曼编码是前缀编码,即任一字符的编码都不是另一字符编码的前缀。

3.哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n,则哈夫曼编码树的结点总数为 2n-1。

4.发送过程:根据由哈夫曼树得到的编码表送出字符数据。

5.接收过程:按左0、右1的规定,从根结点走到一个叶结点,完成一个字符的译码。反复此过程,直到接收数据结束。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 前言
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档