《数据结构导论第四章》由会员分享，可在线阅读，更多相关《数据结构导论第四章（149页珍藏版）》请在金锄头文库上搜索。
1、复复习前前节1 1、数据、数据结构的基本概念构的基本概念2 2、顺序表、序表、链表表3 3、顺序序栈、链栈4 4、顺序序队、链队5 5、顺序串、序串、链串串6 6、数、数组和广和广义表表线性表性表线性表的推广性表的推广树的推广的推广1 1第第4 4章章 树4.1 4.1 树的基本概念的基本概念4.2 4.2 二叉二叉树4.3 4.3 二叉二叉树的存的存储结构构4.4 4.4 二叉二叉树的遍的遍历4.5 4.5 递归消除消除4.6 4.6 树和林和林4.7 4.7 判定判定树和哈夫曼和哈夫曼树2 2本章本章本章本章项项目：目：目：目： 电电文文文文编码编码3 3文字文字文字文字电电文文文文编码编
2、码电电波波波波译码译码摩摩摩摩尔尔斯斯斯斯电码电码（又（又（又（又译为译为摩斯摩斯摩斯摩斯电码电码）是一种）是一种）是一种）是一种时时通通通通时时断的信号代断的信号代断的信号代断的信号代码码，这这种信号代种信号代种信号代种信号代码码通通通通过过不同的排列不同的排列不同的排列不同的排列顺顺序来表达不同的英文字母、数字和序来表达不同的英文字母、数字和序来表达不同的英文字母、数字和序来表达不同的英文字母、数字和标标点符号等。它由点符号等。它由点符号等。它由点符号等。它由美国人艾美国人艾美国人艾美国人艾尔尔菲德菲德菲德菲德维尔发维尔发明（明（明（明（1835183518351835年）。年）。年）。年
3、）。4 4网网网网络络信息信息信息信息传输传输：文字文字文字文字数字数字数字数字编码编码电电信信信信号号号号电电文文文文编码编码发发送者送者送者送者数字数字数字数字编码编码文字文字文字文字电电文文文文编码编码接收者接收者接收者接收者你好你好你好你好0101010101010101010101010101010101010101你好你好你好你好核心核心核心核心问题问题：电电文如何文如何文如何文如何编码编码称称称称为为01010101串？串？串？串？5 5本章本章本章本章项项目：目：目：目：电电文文文文编码问题编码问题涉及知涉及知涉及知涉及知识识点：点：点：点：1 1 1 1、树树的概念的概念的概
4、念的概念2 2 2 2、树树的的的的专业术语专业术语3 3 3 3、二叉、二叉、二叉、二叉树树的概念的概念的概念的概念4 4 4 4、哈夫曼、哈夫曼、哈夫曼、哈夫曼树树和哈夫曼和哈夫曼和哈夫曼和哈夫曼编码编码核心核心核心核心问题问题：如何将：如何将：如何将：如何将电报电报文字文字文字文字转换转换成可成可成可成可传传送送送送编码编码6 6自自然然中中的的树抽抽象象的的树知知识点点1 1：树的概念的概念7 7旋旋转后后8 8适当适当进行行调整整ABCDEFGHI9 9数据数据结构中构中树的形的形态，具有分，具有分层特点特点ABCDEFGHI1010某姓氏族某姓氏族谱1111ABCDEFGHIJKL
5、MNOPQRSTUV WXY Z.对树中的中的结点点给定一个符号名称，具有一定一个符号名称，具有一对多的特点多的特点1212树描述的是一种描述的是一种层次次结构，构， 是一种一是一种一对多的多的逻辑关系关系FGIJABCEDH1313树树(Tree)(Tree)(Tree)(Tree)是是是是n(n=0)n(n=0)n(n=0)n(n=0)个个个个结结点点点点的的的的有有有有限限限限集。集。集。集。n=0n=0n=0n=0时时称称称称为为空空空空树树。n1n1n1n1时时，有且有且有且有且仅仅有一个称有一个称有一个称有一个称为为根的根的根的根的结结点；点；点；点；其其其其余余余余结结点点点点可
6、可可可分分分分为为m(m0)m(m0)m(m0)m(m0)个个个个互互互互不不不不相相相相交交交交的的的的有有有有限限限限集集集集T1,T2,Tm,T1,T2,Tm,T1,T2,Tm,T1,T2,Tm,其其其其中中中中每每每每个个个个集集集集合又是一棵合又是一棵合又是一棵合又是一棵树树，称，称，称，称为为子子子子树树知知识点点1 1：树的概念的概念FGIJABCEDH根根根根1414树树的的的的其其其其他他他他表表表表示示示示形形形形式式式式ABCDEFHGM1515n n结结点：点：点：点：数据元素的内容及其指向其子数据元素的内容及其指向其子数据元素的内容及其指向其子数据元素的内容及其指向其
7、子树树根的分支根的分支根的分支根的分支n n结结点的度点的度点的度点的度：结结点点点点拥拥有的子有的子有的子有的子树树的数目。的数目。的数目。的数目。n n树树的度：的度：的度：的度：树树内各内各内各内各结结点的度的最大点的度的最大点的度的最大点的度的最大值值；知知识点点2 2：树的的专业术语ABCDEFHGMA A A A、B B B B、C C C C、D D D D、E E E E、F F F F、G G G G、H H H H、M M M M均称均称均称均称为结为结点点点点A A A A 结结点的度点的度点的度点的度为为 2 2 2 2C C C C 结结点的度点的度点的度点的度为为
8、3 3 3 3M M M M 结结点的度点的度点的度点的度为为 0 0 0 0树树的度的度的度的度为为3 3 3 31616n n叶子（叶子（叶子（叶子（终终端端端端结结点），非点），非点），非点），非终终端端端端结结点：点：点：点：度度度度为为0 0 0 0的的的的结结点称点称点称点称为为叶子叶子叶子叶子结结点；度不点；度不点；度不点；度不为为0 0 0 0的的的的结结点称点称点称点称为为非非非非终终端端端端结结点。点。点。点。ABCDEFHGM1717n n结结点点点点的的的的层层数数数数：树树中中中中根根根根结结点点点点的的的的层层次次次次为为1 1 1 1，根根根根结结点点点点子子子子
9、树树的的的的根根根根为为第第第第2 2 2 2层层，以此，以此，以此，以此类类推。推。推。推。n n树树的高度（深度）：的高度（深度）：的高度（深度）：的高度（深度）：树树中所有中所有中所有中所有结结点点点点层层次的最大次的最大次的最大次的最大值值ABCDEFHGM1818n n孩孩孩孩子子子子，双双双双亲亲，兄兄兄兄弟弟弟弟，堂堂堂堂兄兄兄兄：结结点点点点的的的的子子子子树树的的的的根根根根称称称称为为该该结结点点点点的的的的孩孩孩孩子子子子；该该结结点点点点称称称称为为孩孩孩孩子子子子的的的的双双双双亲亲；同同同同一一一一个个个个双双双双亲亲的的的的孩孩孩孩子子子子之之之之间间互互互互称称
10、称称兄兄兄兄弟弟弟弟；双双双双亲亲在在在在同同同同一一一一层层的的的的结结点点点点互互互互为为堂堂堂堂兄弟。兄弟。兄弟。兄弟。ABCDEFHGMA A A A是是是是B B B B、C C C C的双的双的双的双亲亲B B B B、C C C C是是是是A A A A的孩子的孩子的孩子的孩子B B B B、C C C C是兄弟关系是兄弟关系是兄弟关系是兄弟关系E E E E、F F F F是堂兄弟关系是堂兄弟关系是堂兄弟关系是堂兄弟关系1919n n路路路路径径径径：若若若若树树中中中中存存存存在在在在一一一一个个个个序序序序列列列列k k k k1 1 1 1，k k k k2 2 2 2k
11、kkkn n n n，使使使使得得得得k k k ki i i i是是是是k k k ki+1i+1i+1i+1的的的的双双双双亲亲，则则称称称称该结该结点序列点序列点序列点序列为为k k k k1 1 1 1到到到到k k k kn n n n的一条的一条的一条的一条路径路径路径路径。n n路径路径路径路径长长度：度：度：度：这这些些些些节节点点点点经过经过的的的的边边的条数的条数的条数的条数ABCDEFHGM序列：序列：序列：序列：A B D M EA B D M EA B D M EA B D M E序列：序列：序列：序列：A B D MA B D MA B D MA B D M序列：序
12、列：序列：序列：A C FA C FA C FA C F是路径是路径是路径是路径非路径非路径非路径非路径是路径是路径是路径是路径2020n n子子子子孙孙，祖祖祖祖先先先先：以以以以某某某某结结点点点点为为根根根根的的的的子子子子树树中中中中的的的的所所所所有有有有结结点点点点都都都都被被被被称称称称为为是是是是该该结结点点点点的的的的子子子子孙孙。从从从从根根根根结结点点点点到到到到该该结结点点点点路路路路径径径径上上上上的所有的所有的所有的所有结结点称点称点称点称为该结为该结点的祖先。点的祖先。点的祖先。点的祖先。ABCDEFHGM2121n n森林：森林：森林：森林：多棵互不相交的多棵互
13、不相交的多棵互不相交的多棵互不相交的树树的集合构成森林的集合构成森林的集合构成森林的集合构成森林ABCDEFHGM三棵三棵三棵三棵树树构成的森林构成的森林构成的森林构成的森林2222n n结结点点点点n n结结点的度点的度点的度点的度(Degree)(Degree)(Degree)(Degree)n n叶子（叶子（叶子（叶子（Leaf)Leaf)Leaf)Leaf)或或或或终终端端端端结结点点点点n n分支分支分支分支结结点或非点或非点或非点或非终终端端端端结结点点点点n n树树的度的度的度的度n n层层次次次次(Level)(Level)(Level)(Level)n n树树的深度的深度的深
14、度的深度(Depth)(Depth)(Depth)(Depth)n n孩子（孩子（孩子（孩子（child)child)child)child)n n双双双双亲亲（Parent)Parent)Parent)Parent)n n兄弟兄弟兄弟兄弟(Sibling)(Sibling)(Sibling)(Sibling)n n祖先祖先祖先祖先n n子子子子孙孙n n路径路径路径路径ABCDEFHGM2323知知识点点3 3： 二叉二叉树的概念的概念n n二叉二叉二叉二叉树树(Binary Tree)(Binary Tree)(Binary Tree)(Binary Tree)：n n或者是一棵空或者是一
15、棵空或者是一棵空或者是一棵空树树，n n或者是一棵由一个根或者是一棵由一个根或者是一棵由一个根或者是一棵由一个根结结点和两棵互不相交的左子点和两棵互不相交的左子点和两棵互不相交的左子点和两棵互不相交的左子树树和右子和右子和右子和右子树树所所所所组组成的非空成的非空成的非空成的非空树树，n n左子左子左子左子树树和右子和右子和右子和右子树树同同同同样样也都是二叉也都是二叉也都是二叉也都是二叉树树 ABCDEFHM2424n n特征：特征：特征：特征： 每个每个每个每个结结点最多只有两棵子点最多只有两棵子点最多只有两棵子点最多只有两棵子树树 子子子子树树有左右之分，次序不能任意有左右之分，次序不能
16、任意有左右之分，次序不能任意有左右之分，次序不能任意颠颠倒，只有一倒，只有一倒，只有一倒，只有一棵子棵子棵子棵子树时树时也也也也必必必必须须分清是左子分清是左子分清是左子分清是左子树还树还是右子是右子是右子是右子树树ABCACB2525网网网网络络信息信息信息信息传输传输：文字文字文字文字数字数字数字数字编码编码电电信信信信号号号号电电文文文文编码编码发发送者送者送者送者数字数字数字数字编码编码文字文字文字文字电电文文文文编码编码接收者接收者接收者接收者你好你好你好你好0101010101010101010101010101010101010101你好你好你好你好核心核心核心核心问题问题：电电文如何文如何文如何文如何编码编码称称称称为为01010101串？串？串？串？2626项目目实现的的进一步分析：一步分析：项目核心目核心问题： 如何将如何将电报文字文字转换成成0101编码 扩展展问题： 电文文传送送时的高效性的高效性2727扩展展问题： 电文文传送送时的高效性的高效性在在计算机及通信中，算机及通信中，常用二常用二进制制编码来表示字符，来表示字符，假假设某某电文通信中只使用文通信中只
