资源描述：
《信息学奥赛初赛指导讲座》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、信息学奥赛初赛指导讲座树的定义树(tree)是包含n(n>O)个结点的有穷集合K,且在K中定义了一个关系N,N满足以下条件：(1)有且仅有一个结点kO,他对于关系N來说没有前驱，称K0为树的根结点。简称为根(root)0(2)除K0夕卜，k中的每个结点，对于关系N來说有且仅有一个前驱。(3)K中各结点，对关系N来说可以有m个后继(m>=O)。若n>l,除根结点Z外的其余数据元素被分为m(m>0)个互不相交的结合Tl,T2,Tm,其中每一个集合Ti(l<=i<=m)本身也是一棵树。树Tl,T2,……Tm称作根结点的子树(subtree)。树也
2、就可以这样定义：树是有根结点和若干颗子树构成的。(上一段来自高林，《数据结构(C++)》，北京清华大学出版社)树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子叵聲谑蘇慕岬愧浣17•艘桓霾愦谓谢坡?在这种层次结构屮有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给岀树的递归定义如下：单个结点是一棵树，树根就是该结点本身。设Tl,T2,..,Tk是树，它们的根结点分别为nl,n2,..,nko用一个新结点n作为nl,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称nl,n2
3、,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称nl,n2,..,nk为结点n的子树。空集合也是树，称为空树。空树中没有结点。二叉树相关：二叉树相关：二叉树的概念：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树"(leftsubtree)和“右子树”(rightsubtree）o二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树（不存在度人于2的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的二叉树的的（i第i层至多有2的（i・l）次方个结点；深度为k的二叉树至多有2人（k）・l个结点，最，如果其终端结点
4、数（即叶子结点数）少有h个结点；对任何一棵二叉树T,如果其终端结点数（即叶子结点数）为nO,度为lo2的结点数为n2,则nO二n2+l。树和二叉树的2个主要差别：1.树中结点的最大度数没有限制，而二叉树结点的最大度数为2；（度指分支）2.树的结点无左、右Z分，而二叉树的结点有左、右Z分且不能颠倒次序。树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法
5、结构。乂如在数据库系统中，树型结构也是信息的重耍组织形式Z-o一切具有层次关系的问题都可用树来描述。（1）完全二义树——若设二叉树的高度为h，Oh层外，其它各层（1〜h・l）的结点数都达到最人个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。（2）满二叉树——除了叶结点外，每一个结点都有左右子叶且叶结点都处在最底层的二叉树。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍历遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。曲于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别
6、表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD（称为后根次序遍历）。前序遍历（先根遍历）:访问根；按先序遍历左子树；按先序遍历右子树。如右图，则前序遍历（先根遍历）其前序遍历为：ABDEGCF中序遍历（中根遍历）：按中序遍历左子树；访问根；按中序遍历右子树。如右图，则中序遍历（中根遍历）其中序遍历为：DBEGAFC后序遍历（后根遍历）：按后序遍历左子树；按后序遍历右子树；访问根。如右图，则后序遍历（后根遍历）其后序遍历为：DGEBFCA层次遍历：即按照层次访问，通常用队列来做。访问根，访问
7、子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）。练习题：二叉树T,己知其前序遍历序列为1243576,中序遍历序列为4215736,贝洪后序遍历序列为（）oA.4257631B.4275631C.4275361D.4723561E.4526371遍历的应用：遍历的应用：如果我们将一个正常的数学表达式用一个二叉树来表示的话，其屮分支结点表示运算符，叶结点表示操作数，运算符前后的操作数分别用左右结点来表示。可见，越深的分支结点处的运算符的优先级越高。例如，数学表达式a+（b-c）*d的二叉
