《解决二叉树的编程问题精选PPT.ppt》由会员分享，可在线阅读，更多相关《解决二叉树的编程问题精选PPT.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、解决二叉树的编程问题第1页，此课件共25页哦目标目标在本章中，你将达到以下目标：理解二叉树的两种存储结构解决二叉树的编程问题构造哈夫曼编码第2页，此课件共25页哦学习情境学习情境用二叉树解决快速搜索磁盘文件中的编程用二叉树解决快速搜索磁盘文件中的编程问题描述问题描述磁盘上有一个文件，物理上随机存储了很多记录，如下表(a)，每条记录有一个关键字(职工号)段唯一的标识该记录。为了方便对表(a)的记录进行增、删、改、查，一般需要建立索引表(b)。现需要实现如下的功能：选择一种数据结构在内存中存放索引表，通过该数据结构能高效地插入、删除和搜索索引表；输入任一关键字，显示出查询该关键字的路径。第3页，此
2、课件共25页哦认识二叉树认识二叉树分析二叉树的逻辑结构分析二叉树的逻辑结构1、二叉树的定义二叉树（Binary Tree）是n(n0)个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。左子树右子树左子树右子树、二叉树的种形态第4页，此课件共25页哦认识二叉树认识二叉树分析二叉树的逻辑结构分析二叉树的逻辑结构、二叉树的相关术语（1）结点的度。结点的度。结点所拥有的子树的个数称为该结点的度。（2）叶结点。叶结点。度为0的结点称为叶结点，或者称为终端结点。（
3、3）分枝结点。分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。（4）左孩子、右孩子、双亲。左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）路径、路径长度。路径、路径长度。如果一棵树的一串结点n1,n2,nk有如下关系：结点ni是ni+1的父结点（1i1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i1，则序号为i的结点是根结点，无双亲结点。（2）如果2in，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左
4、孩子。（3）如果2i1n，则序号为i的结点的右孩子结点的序号为2i1；如果2i1n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i1）/2，左孩子的编号为2i1，右孩子的编号为2i2。第9页，此课件共25页哦用顺序存储结构表示二叉树用顺序存储结构表示二叉树 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系。图7.6(a)的顺序存储如图7.7：第10页，此课件共25页
5、哦用顺序存储结构表示二叉树用顺序存储结构表示二叉树 对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。第11页，此课件共25页哦用链式存储结构表示二叉树用链式存储结构表示二叉树 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链表来指示着元素的逻辑关系。（1）二叉链表存储）二叉链表存储链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。图7.11(
6、a)给出了图7.6(b)所示的一棵二叉树的二叉链表示。第12页，此课件共25页哦用链式存储结构表示二叉树用链式存储结构表示二叉树（）三叉链表存储（）三叉链表存储在三叉链表存储中，每个结点由四个域组成。parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点。图7.13给出了图7.6(b)所示的一棵二叉树的三叉链表示。第13页，此课件共25页哦实现链式存储的二叉树的基本操作实现链式存储的二叉树的基本操作public LinkBiTree(T val)public LinkBiTree(T val,Node lp,Node rp)public bool IsEm
7、pty()public Node Root()public Node GetLChild(Node p)public Node GetRChild(Node p)public void InsertL(T val,Node p)public void InsertR(T val,Node p)public Node DeleteL(Node p)public Node DeleteR(Node p)public Node Search(Node root,T value)public bool IsLeaf(Node p)具体操作参与具体操作参与P140-143第14页，此课件共25页哦二叉树
8、的遍历与实现二叉树的遍历与实现 二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。第15页，此课件共25页哦二叉树的遍历与实现二叉树的遍历与实现 1先序遍先序遍历（DLR）
9、先序遍历的递归过程为：若二叉树为空，遍历结束。否则，(1)访问根结点；(2)先序遍历根结点的左子树；(3)先序遍历根结点的右子树。public void preorder(Node ptr)if(IsEmpty()Console.WriteLine(Tree is empty);return;if(ptr!=null)Console.Write(ptr.Data+);preorder(ptr.LChild);preorder(ptr.RChild);第16页，此课件共25页哦二叉树的遍历与实现二叉树的遍历与实现 2中序遍历（中序遍历（LDR）中序遍历的递归过程为：若二叉树为空，遍历结束。否则，
10、（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。public void inorder(Node ptr)if(IsEmpty()Console.WriteLine(Tree is empty);return;if(ptr!=null)inorder(ptr.LChild);Console.Write(ptr.Data+);inorder(ptr.RChild);第17页，此课件共25页哦二叉树的遍历与实现二叉树的遍历与实现 3后序遍历（后序遍历（LRD）后序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树
11、。（3）访问根结点；public void postorder(Node ptr)if(IsEmpty()Console.WriteLine(Tree is empty);return;if(ptr!=null)postorder(ptr.LChild);postorder(ptr.RChild);Console.Write(ptr.Data +);第18页，此课件共25页哦二叉树的遍历与实现二叉树的遍历与实现 4层次遍历层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。public void LevelOrde
12、r(Node root)if(root=null)/根结点为空根结点为空 return;/设置一个队列保存层序遍历的结点设置一个队列保存层序遍历的结点 CSeqQueueNode sq=new CSeqQueueNode(50);/根结点入队根结点入队 sq.EnQueue(root);while(!sq.IsEmpty()/队列非空，结点没有处理完队列非空，结点没有处理完 Node tmp=sq.DeQueue();/结点出队结点出队 Console.WriteLine(o,tmp);/处理当前结点处理当前结点 if(tmp.LChild!=null)sq.EnQueue(tmp.LChil
13、d);/将当前结点的左孩子结点入队将当前结点的左孩子结点入队 if(tmp.RChild!=null)sq.EnQueue(tmp.RChild);/将当前结点的右孩子结点入队将当前结点的右孩子结点入队 第19页，此课件共25页哦用二叉搜索树解决快速搜索磁盘文件中记录的问题用二叉搜索树解决快速搜索磁盘文件中记录的问题 在二叉树中，如果一个结点的左子结点的值永远小于该结点的值，而右子结点的值永远大于该结点的值，这样的二叉树为二叉搜索树。图7.2 为基于图7.1(b)所示的索引表建立的二叉搜索树，用二叉搜索树解决快速搜磁盘文件记录代码 参参见P147-150第20页，此课件共25页哦问题描述：统计
14、出二叉树中叶子结点的数目 基本要求动态构建二叉树用递归实现该算法活动：二叉树操作活动：二叉树操作第21页，此课件共25页哦最优二叉树最优二叉树哈夫曼树哈夫曼树 最优二叉树，也称哈夫曼（最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。构造的具有最小带权路径长度的二叉树。设二叉树具有设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应叶结个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应叶结点权值的乘积之和叫做二叉树的带权路径长度，记为：点权值的乘积之和叫做二叉树的
15、带权路径长度，记为：例：例：4个叶结点，其权值分别为个叶结点，其权值分别为1，3，5，7，可构造出形状不同的多个二叉树。带权路，可构造出形状不同的多个二叉树。带权路径长度将各不相同。图径长度将各不相同。图7.19给出了其中给出了其中5个不同形状的二叉树。个不同形状的二叉树。第22页，此课件共25页哦最优二叉树最优二叉树哈夫曼树哈夫曼树 构造算法构造算法（1）由给定的）由给定的n个权值个权值W1，W2，Wn构造构造n棵只有一个叶结点的二叉树，从而得棵只有一个叶结点的二叉树，从而得到一个二叉树的集合到一个二叉树的集合FT1，T2，Tn；（2）在）在F中选取根结点的权值最小和次小的两棵二叉树作为左、
16、右子树构造一棵新的二中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；（3）在集合）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；中；（4）重复（）重复（2）（）（3）两步，当）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。叶结点权值叶结点权值集合为集合为W1，3，5，7的哈夫曼的哈夫曼树
17、的构造过树的构造过程。程。第23页，此课件共25页哦小结小结在本章中，你已经学到：二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成二叉树中的相关概念：结点的度，叶结点，分枝结点，左孩子、右孩子、双亲，路径、路径长度，祖先、子孙，结点的层数，树的深度，树的度，满二叉树，完全二叉树。二叉树的5个性质。性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i1）。性质2 一棵深度为k的二叉树中，最多具有2k1个结点。性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有
18、:n0n21。性质4 具有n个结点的完全二叉树的深度k为log2n+1。第24页，此课件共25页哦小结（续）小结（续）性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：（1）如果i1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i1，则序号为i的结点是根结点，无双亲结点。（2）如果2in，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。3）如果2i1n，则序号为i的结点的右孩子结点的序号为2i1；如果2i1n，则序号为i的结点无右孩子。二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成二叉树的存储主要有三种：顺序存储结构、二叉链表存储、三叉链表存储二叉树的7种基本操作和二叉链表存储结构的类实现。二叉树的四种遍历方法：中序遍历、前序遍历、后续遍历、层次遍历。最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。哈夫曼树的构造算法。第25页，此课件共25页哦