树和二叉树数据结构.ppt

《树和二叉树数据结构.ppt》由会员分享，可在线阅读，更多相关《树和二叉树数据结构.ppt（185页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 树2023/5/202第6章 树w 6.1 树的概念及操作w 6.2 二叉树 n 6.2.1 二叉树的概念及操作 n 6.2.2 二叉树的性质n 6.2.3 二叉树的存储结构w 6.3 二叉树的遍历w 6.4 线索二叉树w 6.5 树和森林 n 6.5.1 树的存储结构 n 6.5.2 森林、树、二叉树的相互转换 n 6.5.3 树和森林的遍历w 6.6 哈夫曼树及其应用 n 6.6.1 最优二叉树(哈夫曼树)n 6.6.2 哈夫曼编码 w*6.7算法设计举例2023/5/203主要内容 w 知识点n 树和二叉树定义n 二叉树的性质，存储结构n 二叉树的遍历及遍历算法的应用n*线索二叉

2、树n 二叉树和树及森林的关系n Huffman树与Huffman编码w 重点难点n 二叉树的性质及应用n 二叉树的遍历算法及应用n*线索二叉树的算法n Huffman树的构造方法n 树的算法2023/5/204树例与特征n 社会的组织结构n 家族的族谱n 计算机中的目录组织描述层次结构，是一种一对多的逻辑关系2023/5/205树的定义 w 树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。w（注：有人定义树不能为空）n 有且仅有一个称为根的结点（Root）；n n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每个集合又是一棵树，称为子树(SubTree)F G IJAB CEDH2023/5/206树的定义 w 树的递归定义的各子树T1,T2,Tm的相对次序是重要的，即树是有序的。2023/5/207树定义(图示)T1T2T3