您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第06章树和二叉树(Java版).
《数据结构(Java版)(第3版)》第6章树和二叉树6.1树及其抽象数据类型6.2二叉树及其抽象数据类型6.3二叉树的表示和实现6.4线索二叉树6.5Huffman编码与Huffman树6.6树的表示和实现本章是数据结构课程的重中之重,也是难点所在,表现为二叉链表存储结构和递归算法相结合。链式存储结构和递归算法本身就是两个难点,建立二叉树需要将它们有机结合。《数据结构(Java版)(第3版)》目的和要求目的:理解树型结构;掌握链式存储结构表达非线性结构,掌握递归算法设计。•内容:二叉树的定义、性质、存储结构,二叉链表表示的二叉树类;中序线索二叉树;Huffman树;树的定义、存储结构和实现。•要求:理解树和二叉树概念,掌握树和二叉树的表示和实现,掌握递归算法设计。•重点:二叉链表表示的二叉树类;Huffman树;树的定义、存储结构和构造算法。•难点:链式存储结构表达非线性结构;递归算法设计。•实验:树和二叉树的基本操作,链式存储结构表示树和二叉树;递归算法。《数据结构(Java版)(第3版)》6.1树及其抽象数据类型6.1.1树定义6.1.2树的术语6.1.3树的表示法6.1.4树抽象数据类型《数据结构(Java版)(第3版)》6.1.1树定义树(tree)是由n(n≥0)个结点组成的有限集合。n=0的树称为空树;n0的树T:根(root)结点,它没有前驱结点。其他结点分为m棵互不相交的子树。《数据结构(Java版)(第3版)》6.1.2树的术语1.父母、孩子与兄弟结点2.度3.结点层次、树的高度4.边、路径5.无序树、有序树6.森林《数据结构(Java版)(第3版)》6.1.3树的表示法1.图示法2.横向凹入表示法ABEFCGDHIJ3.广义表表示A(B(E,F),C(G),D(H,I,J))《数据结构(Java版)(第3版)》6.1.4树抽象数据类型publicinterfaceTTreeT//树接口{booleanisEmpty();//判断是否空树TreeNodeTgetChild(TreeNodeTp,inti);//返回p第i个孩子TreeNodeTgetParent(TreeNodeTnode);//返回node的父母intcount();//树的结点个数intheight();//树的高度TreeNodeTsearch(Tx);//查找并返回元素为x的结点voidpreOrder();//先根次序遍历树voidpostOrder();//后根次序遍历树voidlevelOrder();//按层次遍历树voidinsertRoot(Tx);//插入元素x作为根结点TreeNodeTinsertChild(TreeNodeTp,Tx,inti);//插入孩子voidremoveChild(TreeNodeTp,inti);//删除孩子}《数据结构(Java版)(第3版)》6.2二叉树及其抽象数据类型6.2.1二叉树定义6.2.2二叉树性质6.2.3二叉树的遍历6.2.4二叉树抽象数据类型《数据结构(Java版)(第3版)》6.2.1二叉树定义二叉树(binarytree)是n个结点的有限集合:空二叉树;由一个根结点、两棵互不相交的左子树和右子树组成。《数据结构(Java版)(第3版)》6.2.2二叉树性质性质1:若根结点的层次为1,则二叉树第i层最多有2i1(i≥1)个结点。性质2:在高度为k的二叉树中,最多有2k1个结点(k≥0)。性质3:设一棵二叉树的叶子结点数为n0,2度结点数为n2,则n0=n2+1。《数据结构(Java版)(第3版)》性质4:n个结点完全二叉树的高度是。性质5:一棵具有n个结点的完全二叉树,对序号为i(0≤in)的结点,有:①若i=0,则i为根结点,无父母结点;若i0,则i的父母结点序号为。②若2i+1n,则i的左孩子结点序号为2i+1;否则i无左孩子。③若2i+2n,则i的右孩子结点序号为2i+2;否则i无右孩子。1log2nk《数据结构(Java版)(第3版)》6.2.3二叉树的遍历先根次序:访问根结点,遍历左子树,遍历右子树。中根次序:遍历左子树,访问根结点,遍历右子树。后根次序:遍历左子树,遍历右子树,访问根结点。先根遍历序列:ABDGCEFH中根遍历序列:DGBAECHF后根遍历序列:GDBEHFCA《数据结构(Java版)(第3版)》6.2.4二叉树抽象数据类型publicinterfaceBinaryTTreeT{booleanisEmpty();//判断是否空intcount();//返回结点个数intheight();//返回高度voidpreOrder();//先根次序遍历voidinOrder();//中根次序遍历voidpostOrder();//后根次序遍历voidlevelOrder();//按层次遍历BinaryNodeTsearch(Tkey);//查找BinaryNodeTgetParent(BinaryNodeTnode);//返回父母voidinsertRoot(Tx);//插入元素x作为根结点BinaryNodeTinsertChild(BinaryNodeTp,Tx,booleanleftChild);voidremoveChild(BinaryNodeTp,booleanleftChild);voidremoveAll();}《数据结构(Java版)(第3版)》6.3二叉树的表示和实现6.3.1二叉树的存储结构6.3.2二叉树的二叉链表实现6.3.3三叉树的二叉链表实现《数据结构(Java版)(第3版)》6.3.1二叉树的存储结构1.二叉树的顺序存储结构《数据结构(Java版)(第3版)》2.二叉树的链式存储结构二叉链表三叉链表《数据结构(Java版)(第3版)》6.3.2二叉树的二叉链表实现1.二叉树的二叉链表结点类publicclassBinaryNodeT{Tdata;//数据元素BinaryNodeTleft,right;//左、右孩子}2.二叉树类publicclassBinaryTreeTimplementsBinaryTTreeT{BinaryNodeTroot;//根结点}《数据结构(Java版)(第3版)》3.二叉树三种次序遍历的递归算法//先根次序遍历以p结点为根的子树privatevoidpreOrder(BinaryNodeTp){if(p!=null)//若二叉树不空{System.out.print(p.data+);//访问当前结点preOrder(p.left);//按先根次序遍历左子树preOrder(p.right);//按先根次序遍历右子树}}【例6.1】构造并遍历二叉树。《数据结构(Java版)(第3版)》4.基于遍历的操作①求结点个数②求高度③查找④获得父母结点《数据结构(Java版)(第3版)》5.构造二叉树(1)先根和中根序列表示《数据结构(Java版)(第3版)》(2)标明空子树的先根序列表示【例6.2】输出二叉树中指定结点的所有祖先结点。《数据结构(Java版)(第3版)》(3)广义表表示《数据结构(Java版)(第3版)》(4)以完全二叉树的层次遍历序列构造链式存储结构的完全二叉树【例6.3】建立二叉链表表示的完全二叉树。BinaryTTree二叉树接口BinaryTree二叉链表存储的二叉树类实现CompleteBinaryTree完全二叉树类继承《数据结构(Java版)(第3版)》6.二叉树的插入和删除操作(1)插入一个结点(2)删除一棵子树rootAB∧C∧E∧F∧∧D∧H∧∧G∧p(a)创建值为X结点并作为p的左孩子,原p的左孩子D作为X结点的左孩子rootAB∧D∧G∧p∧XX∧(b)创建值为Y结点并作为p的右孩子,原p的右孩子F作为Y结点的右孩子∧Yqq《数据结构(Java版)(第3版)》7.二叉树遍历的非递归算法《数据结构(Java版)(第3版)》8.二叉树的层次遍历《数据结构(Java版)(第3版)》6.3.3三叉树的二叉链表实现1.二叉树的三叉链表结点类publicclassTriNodeT{publicTdata;//数据域publicTriNodeTparent,left,right;//父母结点、左和右孩子结点publicintlevel;//结点的层次}《数据结构(Java版)(第3版)》2.三叉链表表示的二叉树类publicclassTriBinaryTreeT{publicTriNodeTroot;//根结点}(1)构造二叉树《数据结构(Java版)(第3版)》(2)插入结点例6.4输出三叉链表存储二叉树的一条直径。p(a)插入值为Xr的结点q作为p的左孩子,原p的左孩子D作为q的左孩子p∧X(b)插入值为X结点q作为p的右孩子,原p的右孩子F作为q的右孩子∧XqqAparentroot∧datarightB∧leftD∧G∧∧Aroot∧CE∧∧F∧H∧∧1level2214533345《数据结构(Java版)(第3版)》6.4线索二叉树6.4.1线索二叉树定义0left指向左孩子ltag1left为线索,指向前驱结点C0rightrtag1right为线索,指向后继结点C《数据结构(Java版)(第3版)》6.4.2中序线索二叉树1.二叉树的中序线索化2.中序线索二叉树类3.中根次序遍历中序线索二叉树【例6.5】构造中序线索二叉树并进行中根次序遍历。4.先根次序遍历中序线索二叉树5.后根次序遍历中序线索二叉树《数据结构(Java版)(第3版)》1.二叉树的中序线索化《数据结构(Java版)(第3版)》2.中序线索二叉树类publicclassThreadBinaryTreeT{publicThreadNodeTroot;}3.中根次序遍历中序线索二叉树《数据结构(Java版)(第3版)》4.先根次序遍历中序线索二叉树《数据结构(Java版)(第3版)》5.后根次序遍历中序线索二叉树《数据结构(Java版)(第3版)》6.5Huffman编码与Huffman树6.5.1Huffman编码存储“AAAABBBCDDBBAAA”,字符集[A、B、D、C],字符出现次数为7、5、2、1,频率为0.47、0.33、0.13、0.07,哈夫曼编码过程为:AAAABBBCDDBBAAA00001010101111101101010000《数据结构(Java版)(第3版)》6.5.2Huffman树1.二叉树的路径长度10PLniil《数据结构(Java版)(第3版)》2.二叉树的外路径长度《数据结构(Java版)(第3版)》3.二叉树的带权外路径长度10WPL()niiiwl75127(b)WPL=7×2+5×3+1×3+2×1=34512DCBA(a)WPL=7×2+5×2+1×2+2×2=30DCBA7521ABDC(c)WPL=7×1+5×2+2×3+1×3=262157DCBA(d)WPL=2×1+1×2+5×3+7×3=40《数据结构(Java版)(第3版)》4.Huffman算法哈夫曼树定义为带权外路径长度最短的二叉树。哈夫曼树不唯一5(c)217ACDB7521ABDC(d)ABDC7A512CAB(a)(b)5271《数据结构(Java版)(第3版)》构造Huffman树并获得Huffman编码5.Huffman编码的译码(d)合并{7}{8},Huffman树(c)合并{3}{5},新树根结点权值为8(b)选择两棵权值最小的二叉树{1}{2}作为左、右子树合并,新树根结点权值为两者之和37512DCBA(a)n个二叉树的森林F312DC75BA7158A35128CD7AB3512CDB1010Huffman编码A:0C:100D:101B:11
本文标题:第06章树和二叉树(Java版).
链接地址:https://www.777doc.com/doc-2152769 .html