网站建设教程pdf下载,做视频网站犯法吗,网页设计与网站建设书籍,上海工装设计公司排名树形结构广泛存在于客观世界中#xff0c;如族谱、目录、社会组织、各种事物的分类等#xff0c;都可用树形结构表示。树形结构在计算机领域应用广泛#xff0c;如操作系统中的目录结构#xff1b;源程序编译时#xff0c;可用树表示源程序的语法结构#xff1b;在数据库…树形结构广泛存在于客观世界中如族谱、目录、社会组织、各种事物的分类等都可用树形结构表示。树形结构在计算机领域应用广泛如操作系统中的目录结构源程序编译时可用树表示源程序的语法结构在数据库系统中树结构也是信息的重要组织形式之一。简单地说一切具有层次关系或包含关系的问题都可用树形结构描述。
▶1.树的基本概念和特征
图看上去像一棵倒置的树“树”由此得名。图示法表示树形结构时通常根在上叶在下。树的箭头方向总是从上到下即从父节点指向子节点因此可以简单地用连线代替箭头这是画树形结构时的约定。
一棵树由n(n0)个元素组成的有限集合其中每个元素称为节点树有一个特定的根节点(root);除根节点外其余节点被分成m(m0)个互不相交的子集(子树)。 树上任一节点所拥有子树的数量称为该节点的度。图4-26中节点C的度为3,节点B的度为1,节点D、H、F、1、J的度为0。度为0的节点称为叶子或终端节点度大于0的节点称为非终端节点或分支点。树中节点B是节点D的直接前趋因此称B为D的父节点称D为B的孩子或子节点。与父节点相回的节点互称为兄弟如E、F、G是兄弟节点。一棵树或子树上的任何节点(不包括根本身)称为根的子孙。树中节点的层数(或深度)从根开始算起根的层数为1,其余节点的层数为双亲节点层数加1。在一棵树中如果从一个节点出发按层次自上而下沿着一个个树枝到达另一个节点则称它们之间存在一条路径路径的长度等于路径上的节点数减1。森林指若干棵互不相交树的集合实际上一棵树去掉根节点后就成为森林。 树是一种“分支层次”结构。所谓“分支”是指树中任一节点的子孙可以它们所在子树的不同划分成不同的“分支”;所谓“层次”是指树上所有节点可以按层划分成不同的“层次”。在实际应用中树中的一个节点可用来存储实际问题中的一个数据元素而节点之间的逻辑关系往往用来表示数据元素之间的某种重要关系。 例在3D游戏中经常把游戏场景组织在一个树结构中这是为了可以快速判断出游戏的可视区域。其算法思想是如果当前节点完全不可见那么它的所有子节点也必然完全不可见如果当前节点完全可见那么它的所有子结点也必然完全可见如果当前节点部分可见就必须依次判断它的子节点这是一个递归的算法。 树的基本运算包括建树(CREATE)、树遍历、剪枝(DELETE)、求根(ROOT)、求双亲(PARENT)、求孩子(CHILD)等操作。
▶2.二叉树的存储结构
1)二叉树
二叉树的特点是除了叶以外的节点都有2个子树如图4-27所示。二叉树的2个子树有左右之分颠倒左右就是不一样的二叉树了所以二叉树左右不能随便颠倒。由此还可以推出三叉树、四叉树、五叉树、六叉树等。
2)二叉树的链表存储结构
二叉树有两类存储结构链式存储结构和顺序存储结构。最常用的是二叉树节点链表存储结构(简称为二叉树链表)。
链表存储结构中Data称为数据域用于存储节点中的数据元素Lchid称为左孩子域用于存放指向本节点左孩子的指针《简称为左指针);与此类似Rchid称为右指针每个二叉树链表还有一个指向根节点的指针该指针称为根指针。根指针具有标识二叉树链表的作用对二叉树链表的访问从根指针开始。值得注意的是二叉树链表中每个存储节点的每个指针域必须有一个值这个值 或者是指向该节点一个孩子的指针或者是空标志(null或^)。
二叉树的多数基本运算(如求根、求左右子树等)很容易实现。但求双亲运算(PARENT)比较麻烦而且时间性能不高。如果在实际问题中需要经常做求双亲运算则采用二叉树链表为存储结构显然不合适。这时可以采用三叉树链表作为存储结构。
3)二叉树的顺序存储结构
程序设计语言中并没有“树”这种数据类型因此二叉树的顺序存储结构由一维数组构成二叉树的节点按次序分别存入数组的各个单元。一维数组的下标就是节点位置指针每个节点中有一个指向各自父亲节点的数组下标。显然节点的存储次序很重要存储次序应能反映节点之间的逻辑关系(父子关系),否则二叉树的运算就难以实现。为了节省查询时间可以规定儿子的数组下标值大于父亲的数组下标值而兄弟节点的数组下标值随兄弟从左到右递增。
在顺序存储结构中由于节点的存储位置就是它的编号(即下标),因此节点之间可通过它们的下标确定关系。如果二叉树不是完全二叉树就必须将其转化为完全二叉树。可通过在二叉树“残缺”位置上增设“虚节点”的方法将其转化成一棵完全二叉树。然后对得到的完全二叉树重新按层编号然后再按编号将各节点存入数组各个“虚节点”在数组中用空标志△表示。经过变换的顺序存储结构可以用完全二叉树类似的方法实现二叉树数据结构的基本运算。显然上述方法解决了非完全二叉树的顺序存储问题但同时也造成了存储空间的浪费。可见这是一种以空间换取性能的计算思维方式。
▶3.二叉树的遍历
树的遍历是指沿着某条搜索路线依次对树中每个节点访问一次且仅访问一次。树的遍历方法有广度优先遍历和深度优先遍历。二叉树访问一个节点就是对该节点的数据域进行某种处理处理内容依具体问题而定。 二叉树由三部分组成根(N)、左子树(L)和右子树(R)。遍历运算的关键在于访问节点的“次序”,二叉树的遍历可分解成三项子任务访问根节点遍历左子树(依次访问左子树的全部节点);遍历右子树(依次访问右子树的全部节点)。树的遍历方法主要有“广度优先遍历”和“深度优先遍历”。通常限定为“先左后右”,这样就减少了一些遍历方法。树的深度优先遍历又可分为前序遍历(NLR,根一左—右),后序遍历(LRN,左—右一根)和中序遍历(LNR,左—根一右),其中中序遍历只有对二叉树才有意义。 A)
