[小学教育]数据结构第6章树.pptVIP

1 第六章 树 树的定义及运算 树的定义及运算 树的定义及运算 3.关于树的基本术语 树的基本术语 树的基本运算 树的基本运算 6.1.2树的性质 树的性质 树的性质 6.2 二叉树 二叉树的定义 2.二叉树的基本运算 二叉树的基本运算 6.2.2二叉树的性质 二叉树的性质 二叉树的性质 二叉树的性质 二叉树的性质 第六章习题（1） 6.2.3二叉树的存储结构 顺序存储结构 二叉树的存储结构 链式存储结构 建立二叉链表 建立二叉链表 6.3二叉树的遍历 二叉树的遍历 遍历的递归算法 6.3.2 非递归遍历二叉树的算法 前序非递归遍历 2.中序遍历二叉树的非递归算法 中序非递归遍历 3.后序遍历二叉树的非递归算法 后序非递归遍历 后序非递归遍历 4.按层次遍历二叉树 按层次遍历 6.3.3遍历算法的应用 遍历算法的应用 3．求二叉树的深度 求二叉树的深度 4．表达式求值 表达式求值 6.4二叉树的线索化 二叉树的线索化 二叉树的线索化 线索树的建立 求前驱、后继 6.4.2线索二叉树的遍历 线索二叉树的遍历 6.4.3线索二叉树的更新 第六章习题（2） 6.5树和森林 双亲表示法 2.孩子表示法 孩子表示法 （3）孩子链表示法 孩子链表示法 3.孩子-兄弟表示法（或二叉树表示法） 6.5.2森林和二叉树的转换 2.森林F转换成二叉树BT(F?BT) 3.二叉树BT恢复成森林F（BT?F） 6.5.3树和森林的遍历 树和森林的遍历 树和森林的遍历 树和森林的遍历 6.6二叉树应用举例 2．树的路径长度 Huffman树（或H树） Huffman树 Huffman树 构造H树的C语言算法 构造H树的C语言算法 构造H树 6.5.2Huffman编码及译码 Huffman编码 Huffman编码 Huffman编码 2．Huffman译码 Huffman译码 第六章习题（3） 上机题4 第六章小结 方法：先将F中各树转换成二叉树；然后各二叉树通过根的右指针相连。 例6-23 设森林F={T1，T2，T3}，将其转换成二叉树的过程如图6.43: A B D C F E H I G J T1 T2 T3 A B D C F E H I G J 这是F?BT的逆变换。 方法：对BT中任一结点，其Lchild所指结点仍为孩子，而Rchild所指结点为它的右兄弟，即“左孩子，右兄弟”。 如对例6-23中的二叉树BT，恢复成森林F的过程为：A的左子B为A的第一子，A的右子E为A的右兄弟，因A是根，所以E应为另一棵树的根；B的左子为空，故B一定为叶子，而C为B的右兄弟，依次类推。 A B D C F E H I G J D C H J I F G A B E 二叉树BT 森林F 树和森林的遍历是二叉树遍历的推广，即按某种规则（或次序）将树或森林中每个结点访问且仅访问一次。 1．先根遍历树T 方法：若T≠∧ ，先访问T的根结点，然后从左至右依次遍历根下的各子树。对各子树的遍历们采用先根遍历方法（递归）。 例6-24 设树T如图6.45所示。对其按先根遍历的过程为：访问根结点A；A有三棵子树，依次按先根遍历。因第一棵子树只有一个结点B，访问之，第二棵子树的根为C，访问C，再遍历C下的D和E；接着再遍历A的第三棵子树，即访问结点F。 A B F D C E 图6.45 先根序列: A B C D E F 2．后根遍历树T 方法：若T≠∧，从左至右遍历根下的各子树，最后访问根结点。对各子树的遍历采用后根遍历算法。 对例6-24中的对T，后根遍历过程为：先遍历根A的第一棵子树，即访问B；然后遍历A的第二棵子树，仍旧采用后根遍历法，访问序列应为（D,E,C）；接着遍历A的第三棵子树，即访问结点F；最后访问总的根结点A。 A B F D C E 图6.45 A 后根序列: B C D E F 3．先序遍历森林F 设F={ T1,T2,………..,Tm }，其中Ti(1≤i≤m)为F中第i棵子树。 方法：若F≠φ，则： （1）访问F中T1之根； （2）先序遍历T1之根下的各子树（子森林）； （3）先序遍历除T1之外的森林（T2,……,Tm）。 显然(2)、(3)为递归调用，即：若子森林存在，仍按先序遍历方法对其遍历。如对例6-23中的森林F，先序遍历结果为：（A,B,C,D,E,F,G,H,I,J）。 此方法等价为：先将F转换二叉树BT，然后对BT按前序（DLR）遍历，其结果是一样的。 D C H J I F G A B E T1 T2 T3