《第七章 树状结构精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章 树状结构精选文档.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章 树状结构本讲稿第一页，共五十三页7.1 何谓树状结构l树树状状结结构构在在计计算算机机信信息息处处理理中中应应用用相相当当广广泛泛，如文件系统、目录组织、菜单管理等。如文件系统、目录组织、菜单管理等。l树树状状结结构构中中常常见见的的是是树树和和二二叉叉树树，本本章章介介绍绍这这两两种种结结构构的的概概念念、存存储储结结构构和和相相关关算算法法，并并研研究究树树、二二叉叉树树之之间间的的相相互互转转换换，最最后后给给出树形结构在现实生活中的一些具体应用。出树形结构在现实生活中的一些具体应用。本讲稿第二页，共五十三页7.1 何谓树状结构l树是树是n（n0）个有限元素（习惯称作结点）的集合
2、）个有限元素（习惯称作结点）的集合T。当。当n=0时，时，称这棵树为空树；当称这棵树为空树；当n0时，集合时，集合T满足如下条件：满足如下条件：l（1）有且只有一个称为根（）有且只有一个称为根（Root）的结点，它没有直接前）的结点，它没有直接前驱，但有零个或多个直接后继；驱，但有零个或多个直接后继；l（2）其余的）其余的n-1个结点可以划分为个结点可以划分为m个互不相交的有限集个互不相交的有限集T1，T2，T3，Tm，其中每个集合，其中每个集合Ti 又是一棵树，称为根（又是一棵树，称为根（Root）的子树。每棵子树的根结点有且只有一个直接前驱，但有零个或的子树。每棵子树的根结点有且只有一个直
3、接前驱，但有零个或多个直接后继。多个直接后继。l可以看出，树的定义用到了递归的方法，即用树来定义树，可以看出，树的定义用到了递归的方法，即用树来定义树，这种方法在后面树（特别是二叉树）的遍历、建立等算法中这种方法在后面树（特别是二叉树）的遍历、建立等算法中经常用到。经常用到。本讲稿第三页，共五十三页7.1.1 何谓树l从图中树T可知，节点A为树T的根节点(root)，B,C,D.,M则为节点A的子节点，若包含其下拥有的所有子节点，则为TreeT的子树(subtree)。例如B是A的子节点，P、Q皆是B的子节点，而B、P、Q为树T的子树。本讲稿第四页，共五十三页7.1.2 树的相关名称及意义l(
4、1)根节点(root node)：一棵树中没有前驱节点的节点，称为根节点。l(6)分支度(度)(degree)：节点的分支度节点的分支度为每个节点所拥有的子节点个数。而一棵树中最大的分支度值，即为该树的分支度树的分支度。l(2)叶节点(leaf node)或终端节点(terminal mode)：一棵树中没有子节点的节点，称为叶节点。叶节点的分支度为0。l(3)非终端节点(nonterminal mode)除了叶节点以外的其它节点，称为非终端节点。l(4)父节点(parent)和子节点(child)：若节点x有一个以节点y为树根(root)的子树，则x为y的父节点，而y为x的子节点。节点的前驱
5、节点称为该节点的父节点。树中一个节点的子树的根节点称为该节点的子节点。本讲稿第五页，共五十三页7.1.2 树的相关名称及意义l(5)兄弟(sibling)：同一个父节点之节点，称为兄弟。如图，B、C、D的父节点均为A，故B、C、D互为兄弟。l(9)祖先(ancestor)：某节点x的祖先是从根到该节点所经分支上的所有节点。l(7)节点的阶层（层次）(level)：阶层为节点之特性值，将根节点之阶层设为1，其子节点为2，依此类推。l(8)高度(height)或深度(depth)：一棵树中的最大阶层值，称为树的高度或深度。l(10)树林(forest)：n0个树的集合称为树林。若将一树的根节点移去
6、，所剩这恰是一树林。本讲稿第六页，共五十三页7.2 二叉树l7.2.1 何谓二叉树二叉树(Binary tree)是树的一种，二叉树中的节点至多只能有两个子节点。二叉树的定义如下：l(1)由有限个节点所构成之集合，此集合可以为空的。l(2)二叉树的根节点下可分成两个子树，称为左子树和右子树，左子树和右子树亦称二叉树。本讲稿第七页，共五十三页7.2.1 何谓二叉树l由二叉树的定义可知，每个节点只能有0、1或2个子树，且每个子树有左右之分。把位于左边的叫做左子树，右边的叫做右子树。即使只有一棵子树时，也要区分它是左子树还是右子树。本讲稿第八页，共五十三页7.2.3 二叉树的相关特色l二叉树的性质：
7、(1)阶层(level)为i的二叉树，最多有2i-1个节点。(2)高度(height)为h的二叉树，最多有2h1个节点。(3)对任一个非空的二叉树而言，若分支度为i的节点各有n i个，则n 0=n 2+1本讲稿第九页，共五十三页l(1)满二叉树(full binary tree)一树中所有叶节点均在同一阶层，而其它非终端节点(nonterminal node)之分支度均为2，则此树为一满二叉树。若该树的高度为h，则此二叉树的节点为2h-1。本讲稿第十页，共五十三页l(2)完全二叉树(complete binary tree)一棵树扣除掉最大阶层那层后为一满二叉树，且阶层最大那层的节点均向左靠齐
8、，则该二叉树称为完全二叉树。在一棵深度为k，结点为n的二叉树中，对树中结点按从上到下，从左到右的顺序编号，完全二叉树中编号为1n的结点分别与满二叉树中编号为1n的结点位置一一对应。本讲稿第十一页，共五十三页7.3 二叉树表示法l二叉树节点的表示法，常用的有下列3种方法：(1)二叉树数组表示法(2)二叉树结构数组表示法(3)二叉树链表表示法l其中“数组表示法”和“结构数组表示法”是属于静态内存空间配置，而“链表表示法”是利用列表结构的方式，属于动态内存空间配置。本讲稿第十二页，共五十三页7.3.1 二叉树数组表示法l对于一棵满二叉树，将其结点从上到下，从左到右顺序编号，再根据编号存入对应下标编号
9、的数组中。l如果该树不为满二叉树，也可对各节点编成在满二叉树中相同位置之节点编号值，再以相同的方式存入数组中，若某一编号没有节点存在，则不存值于数组中。l假设一父节点的编号为n左子节点的编号为：2n，右子节点的编号为：2n+1。本讲稿第十三页，共五十三页7.3.1 二叉树数组表示法l优点：对于任意一个节点都能很容易的找到其父节点、子节点及兄弟。l缺点：这样将导致存储空间的浪费，极端的情况是对于一个二叉树，每个结点只有右孩子而无左孩子时，假设该树的深度为k，则需要2k-1个存储单元，而实际只利用了其中的k个存储单元。本讲稿第十四页，共五十三页7.3.3 二叉树链表表示法（二叉链表）l链表的节点结
10、构如下：l每个节点包含三个域：数据域（Data）：存储结点的数据内容左指针域（left）：指向该节点的左子树右指针域（right）：指向该节点的右子树l由这种链式存储结构构成的二叉树称为二叉链表。本讲稿第十五页，共五十三页7.3.3 二叉树链表表示法（二叉链表）l二叉链表结构的声明如下：lstrust treel struct tree*left;l int data;l struct tree*right;lltypedef struct tree treenode;ltreenode*b_tree;本讲稿第十六页，共五十三页7.4 二叉树的遍历l“遍历”是访问数据结构中的各个数据值，例如：
11、数组和链表可从前端到尾端或从尾端至前端依序访问各个数据值。而二叉树是一种特殊的数据结构，每个节点其下又各有左、右两个分支。l“二叉树的遍历”是以固定的顺序，有系统地访问二叉树中的各节点，且每个节点均恰好被访问一次。本讲稿第十七页，共五十三页l一棵二叉树由根结点、左子树和右子树三部分组成，若依次遍历这三部分，也就遍历了整棵树。这里用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，。若按照从左到右的顺序进行遍历，则有LDR、DLR、LRD三种方式，它们分别称为中序遍历、前序遍历和后序遍历。本讲稿第十八页，共五十三页7.4.1 二叉树的前序遍历l前序遍历二叉树的算法为：若二叉树为空，则遍历结束
12、，否则依次执行以下操作：l（1）访问根结点；l（2）前序遍历根结点的左子树；l（3）前序遍历根结点的右子树。本讲稿第十九页，共五十三页l其具体算法实现如下：lvoid preorder(b_tree point)ll if(point!=NULL)/*遍历的终止条件*/l l printf(%d,point-data);/*处理打印节点内容*/l preorder(point-left);/*处理左子树*/l preorder(point-right);/*处理右子树*/l l本讲稿第二十页，共五十三页7.4.2 二叉树的中序遍历l中序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行
13、以下操作：l（1）中序遍历根结点的左子树；l（2）访问根结点；l（3）中序遍历根结点的右子树。本讲稿第二十一页，共五十三页其具体算法实现如下：lvoid inorder(b_tree point)ll if(point!=NULL)/*遍历的终止条件*/l l inorder(point-left);/*处理左子树*/l printf(%d,point-data);/*处理打印节点内容*/l inorder(point-right);/*处理右子树*/l l本讲稿第二十二页，共五十三页lvoid inorder(b_tree point)ll if(point=NULL)/*遍历的终止条件*/
14、l return;l elsel l inorder(point-left);/*处理左子树*/l printf(%d,point-data);/*处理打印节点内容*/l inorder(point-right);/*处理右子树*/l l本讲稿第二十三页，共五十三页7.4.3 二叉树的后序遍历l后序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行以下操作：l（1）后序遍历根结点的左子树；l（2）后序遍历根结点的右子树；l（3）访问根结点。本讲稿第二十四页，共五十三页l其具体算法实现如下：lvoid postorder(b_tree point)ll if(point!=NULL)/*
15、遍历的终止条件*/l l postorder(point-left);/*处理左子树*/l postorder(point-right);/*处理右子树*/l printf(%d,point-data);/*处理打印节点内容*/l l本讲稿第二十五页，共五十三页l【例】有一棵二叉树的前序遍历序列为A、C、I、K、N、H、L、M，中序遍历序列为I、C、N、K、A、L、M、H，试画出此二叉树。l 由于在前序遍历中首先访问根节点，因此，前序序列中的第一个结点为二叉树的根节点，即A为二叉树的根节点。又由于在中序遍历中访问根节点的次序为居中，左子树的节点居前，右子树的节点居后，因此，在中序序列中，以根结
16、点（A）为分界线，前面的子序列（I、C、N、K）一定在左子树中，后面的子序列（L、M、H）一定在右子树中。同样的道理，对于已经划分出的每一个子序列的所有节点中，位于前序序列最前面的一个节点为子树的根节点，而在中序序列中位于该根节点前面的节点构成左子树的节点子序列，位于该根节点后面的节点构成右子树的节点子序列。按此规则不断循环下去，直到所有的子序列为单个节点为止，其求解过程如图所示。本讲稿第二十六页，共五十三页本讲稿第二十七页，共五十三页7.5 二叉树的建立(递归法)l给定一个二叉树数组结构，使用递归方式建立一棵二叉树，并以中序遍历的方式输出二叉树节点内容。本讲稿第二十八页，共五十三页lb_tr
17、ee create_btree(int*nodelist,int position)ll b_tree newnode;/*声明新节点指针*/l l if(nodelistposition=0|position 15)/*递归的终止条件*/l return NULL;l elsel l /*-建立新节点的内存空间-*/l newnode=(b_tree)malloc(sizeof(treenode);l l /*-建立节点内容-*/l newnode-data=nodelistposition;l /*-递归建立左子树-*/l newnode-left=create_btree(nodelis
18、t,2*position);l /*-递归建立右子树-*/l newnode-right=create_btree(nodelist,2*position+1);l return newnode;/*返回复制树的位置*/l l本讲稿第二十九页，共五十三页7.8 二叉树的复制l使用递归方式建立二叉树，再复制原来的二叉树，并输出原本的二叉树和备份二叉树的节点内容。本讲稿第三十页，共五十三页lb_tree copy_btree(b_tree root)ll b_tree newnode;/*声明新节点指针*/l l if(root=NULL)/*递归的终止条件*/l return NULL;l el
19、sel l /*-建立新节点的内存空间-*/l newnode=(b_tree)malloc(sizeof(treenode);l /*-建立节点内容-*/l newnode-data=root-data;l /*-递归建立左子树-*/l newnode-left=copy_btree(root-left);l /*-递归建立右子树-*/l newnode-right=copy_btree(root-right);l return newnode;/*返回复制树的位置*/l l本讲稿第三十一页，共五十三页7.6 二叉查找树l二叉查找树(Binary search tree)的条件：每个节点的数
20、据要大于左子节点的数据，且要小于右子节点的数据。具体来说：（1）若它的左子树非空，则左子树上所有结点的值均小于根节点的值；（2）若它的右子树非空，则右子树上所有结点的值均大于根节点的值；（3）左、右子树本身也分别为二叉查找树；本讲稿第三十二页，共五十三页l二叉查找树的性质：（1）二叉查找树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字；（2）二叉查找树中，各结点关键字是惟一的（3）按中序遍历该树所得到的中序序列是一个递增有序序列。本讲稿第三十三页，共五十三页7.6 二叉查找树(二叉查找树的插入)l二叉查找树的插入：以第一个元素为根节点依序将元素值与根节点做比较
21、l若元素值大于根节点值，则将该元素值往根节点之右子节点移动，若此右子节点为空，则将元素值存入，否则就重复比较，直到找到适当的空节点为止。l若元素值小于根节点值，则将该元素值往根节点之左子节点移动，若此左子节点为空，则将元素值存入，否则就重复比较，直到找到适当的空节点为止。本讲稿第三十四页，共五十三页lb_tree insert_node(b_tree root,int node)ll /*声明树根指针*/*声明目前节点指针*/*声明父节点指针*/l /*建立新节点的内存空间*/l newnode=(b_tree)malloc(sizeof(treenode);l/*存入节点内容*/*设置右指针
22、初值*/*设置左指针初值*/l if(root=NULL)l return newnode;/*返回新节点的位置*/l elsel l currentnode=root;/*存储目前节点指针*/l while(currentnode!=NULL)l l parentnode=currentnode;/*存储父节点指针*/l if(currentnode-data node)/*比较节点的数值大小*/l currentnode=currentnode-left;/*左子树*/l elsel currentnode=currentnode-right;/*右子树*/l l if(parentnod
23、e-data node)/*将父节点和子节点做连结*/l parentnode-left=newnode;/*子节点为父节点之左子树*/l elsel parentnode-right=newnode;/*子节点为父节点之右子树*/l l return root;/*返回根节点之指针*/l本讲稿第三十五页，共五十三页l二叉查找树的生成二叉查找树的生成l二叉查找树的生成，是从空的二叉查找树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉查找树中。本讲稿第三十六页，共五十三页l二叉查找树的生成算法二叉查找树的生成算法lb_tree create_btree(int*data,
24、int len)ll b_tree root=NULL;/*根节点指针根节点指针*/l int i;l for(i=0;i data=findnode)/*找到了欲寻找的节点*/l return point;/*返回找到节点的指针*/l elsel if(point-data findnode)l point=point-left;/*往左子树找*/l elsel point=point-right;/*往右子树找*/l l return NULL;/*该节点不在此二叉树中*/l本讲稿第三十九页，共五十三页7.7 二叉树(二叉查找树)的节点删除l对于一个二叉树，若欲删除其节点，应先寻找欲删除的
25、节点是否存在于该二叉树中。关于二叉树的节点查找，前面已有详细的介绍，本节将说明如何将节点从二叉树中删除。l由于我们在删除一个节点后，必须要维持满足二叉查找树数据排列的原则：左子节点节点Rthread=1)/*右子节点为引线右子节点为引线*/l point=point-Rchild;/*往右子树前进往右子树前进*/l elsel l point=point-Rchild;/*先到右子节点先到右子节点*/l while(point-Lthread!=1)/*左子节点不是引线左子节点不是引线*/l point=point-Lchild;/*往左子节点前进往左子节点前进*/l l if(point!=
26、root)l printf(%dn,point-data);/*输出节点数据输出节点数据*/l while(point!=root);/*找到开头节点找到开头节点*/l本讲稿第五十一页，共五十三页7.11 一般树转二叉树l欲将一般树转换成二叉树，也就是要将n个分支度变成2个分支，主要有4个步骤：(1)保留所有节点与其左子节点的链接(2)连结所有兄弟节点(拥有同一个父节点的子节点)(3)打断所有节点原本与右子节点的链接(4)将兄弟节点顺时钟转45o本讲稿第五十二页，共五十三页作业l设二叉树以二叉链表进行存储，每个节点的数据域为整数，编写算法，求二叉树节点数据域中的最大整数。本讲稿第五十三页，共五十三页