孩子结点.ppt

哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下： 设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。 哈夫曼编码 7.7.3 哈夫曼编码的软件设计 哈夫曼编码的数据结构设计 设计哈夫曼树的结点存储结构为双亲孩子存储结构。 weight flag parent leftChild rightChild 存放哈夫曼编码的存储结构为 start Bit[0] Bit[1] … Bit[maxBit-1] 7.8 树与二叉树的转换 1 树转换为二叉树 树转换为二叉树的方法是： （1）树中所有相同双亲结点的兄弟结点之间加一条连线。 （2）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线。 （3）整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。 树转换为二叉树的过程 2 二叉树还原为树 二叉树还原为树的方法是： （1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。 （2）删除原二叉树中所有双亲结点与右孩子结点的连线。 （3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。 二叉树还原为树的过程 7.9 树的遍历 1 先根遍历 树的先根遍历递归算法为： （1）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。 2 后根遍历 树的后根遍历递归算法为： （1）按照从左到右的次序后根遍历根结点的每一棵子树； （2）访问根结点。 先根遍历得到的结点序列为：A B E J F C G K L D H I 后根遍历得到的结点序列为：J E F B K L G C H I D A 二叉链存储结构的二叉树 （a）不带头结点的二叉树 （b）带头结点的二叉树 二叉树的二叉链式存储结构是一种常用的二叉树存储结构。其优点是结构简单，可以方便的构造任意需要的二叉树，key方便的实现二叉树的大多数操作。其缺点是查找当前节点的双亲结点操作实现起来比较麻烦。 另一种形式是三叉链。三叉链是在二叉链的基础之上再增加一个双亲结点域parent。三叉链对于查找当前结点的双亲结点操作实现起来比较容易。 3 二叉树的仿真指针存储结构 二叉树的仿真指针存储结构是用数组存储二叉树中的结点 。 二叉树的仿真二叉链存储结构 7.3 以结点类为基础的二叉树设计 7.3.1 二叉树结点类 7.3.2 二叉树的遍历 1 二叉树遍历的基本方法 一棵二叉树由三部分组成：根结点、左子树和右子树 。 根据遍历算法访问根结点的次序，我们介绍三种遍历算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。 前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 除前序、中序和后序遍历算法外，二叉树还有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。 二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得当前队头结点，访问该结点； （3.b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列； （3.c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列； （4）结束。 7.3.3 二叉树遍历的应用 1 打印二叉树 2 查找数据元素 查找数据元素： 在二叉树中查找数据