深圳龙华的学校网站建设,甘肃最新消息今天,崇信县门户网站官网,没网站域名可以做备案吗文章目录树二叉树二叉树的性质完全二叉树二叉树的存储遍历二叉树和线索二叉树6.4 树和森林哈夫曼树应用树 树的定义#xff1a;树是以分支关系定义的层次结构。 D; 树(Tree)是n(n≥0)个结点的有限集。 R 数据关系 有且仅有一个特定的称为根(Root) 的结点 当n1时树是以分支关系定义的层次结构。 D; 树(Tree)是n(n≥0)个结点的有限集。 R 数据关系 有且仅有一个特定的称为根(Root) 的结点 当n1时除根以外的其余结点 可分为m(m0)个互不相交的有限 集T1, T2 ,… ,Tm 其中每一个集 合本身又是一棵树并且称为根 的子树(SubTree)。 只有一个结点——只有一个根结点的树 有0个结点的树——空树 分支结点 非终端结点 结点层次指的是结点在树中所处的层次 堂兄弟指的是具有相同父亲的兄弟结点 树的深度指的是树中所有结点中最大层数 有序树指的是树中每个结点的子节点之间具有顺序关系无序树则相反子节点之间没有顺序关系 森林则指由若干棵互不相交的树组成。 孩子指的是一个结点的直接后代 双亲指的是一个结点的直接前驱 兄弟指的是具有相同双亲的结点 祖先指的是从根到某一结点路径上所有结点 子孙则指某一结点为根的子树中所有结点。 叶子结点指的是度为0的结点 分支结点指的是度不为0的结点 内部结点指的是除根节点和叶子节点以外的所有节点 树的度指的是树中所有结点中最大度数。
二叉树 二叉树(Binary Tree) 是另一种树形结构 特点是每个结点最多只有两棵子树(即二 叉树中不存在度2的结点) 二叉树的子树有左右之分其次序不能 任意颠倒 二叉树的性质 性质1 在二叉树的第i层上至多有2i-1个结点(i≥1) 性质2 深度为k的二叉树至多有2k-1个结点(k≥1) 性质3 对任一棵二叉树T如果其终端结点数为n0度为2的 结点数为n2则n0n21
完全二叉树
满二叉树 一棵深度为k且有2k-1个结点的二叉树 深度为k有n个结点的二叉树当且仅当其每一个 结点都与深度为k的满二叉树中编号从1至n的结点 一一对应时 某一结点 有右子树 则其必有 左子树叶子结点只可能在层次最大的两层上出现对任一结点若其右分支的子孙最大层次为l则其 左下分支的子孙的最大层次必为l或l1 性质4 具有n个结点的完全二叉树的深度为 log2 n 1
二叉树的存储
顺序存储结构 链式存储结构 知识点 在含有n个结点的二叉链表中有n1个空链域 遍历二叉树和线索二叉树
对线性结构而言顺序遍历 二叉树是非线性结构每个结点有两个后继则存在如 何遍历即按什么样的搜索路径遍历的问题。 看ppt 有代码实现
二叉树遍历的时间效率和空间效率
基本操作访问结点Visit()
时间效率:O(n) //每个结点只访问一次空间效率:O(n) //栈占用的最大辅助空 间
6.4 树和森林 树的存储结构——双亲表示法 利用每个结点只有一个 双亲的性质 采用多重链表即每个结点设置多个指针域每个指针域指 向一棵子树的根结点 树林遍历顺序 和 树一样 ( 顺序即为第几棵树的Root结点) 树的存储结构——孩子兄弟表示法 / 二叉树表示法 / 二叉链 表表示法
哈夫曼树 应用
1二进制编码 : 通信中可以采用0、1的不同排列来表示不同的字符 称为二进制编码。 发送端需要将电文中的字符序列转换成二进制的0、1 序列即编码 接受端需要把接受的0、1序列转换成对应的字符序列 即译码。 (左0 右 1)
2} 前缀编码 : 若对某一字符集进行不等长编码则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫 做前缀编码
