php站点搭建,企业电话号码查询网站,推网站,电子商务网站功能需求前言 在数据结构中树是一种很重要的数据结构#xff0c;很多其他的数据结构和算法都是通过树衍生出来的#xff0c;比如#xff1a;堆#xff0c;AVL树#xff0c;红黑色等本质上都是一棵树#xff0c;他们只是树的一种特殊结构#xff0c;还有其他比如linux系统的文件系…前言 在数据结构中树是一种很重要的数据结构很多其他的数据结构和算法都是通过树衍生出来的比如堆AVL树红黑色等本质上都是一棵树他们只是树的一种特殊结构还有其他比如linux系统的文件系统就是一棵树。下面让我们一起来学习一下树的结构和特点吧
1.树的概念 树是一种非线性的数据结构它是由nn 0个有限的节点组成的具有层次结构的集合把它叫做树是因为它看起来像一颗倒挂的树也就是说它根朝上而叶子朝下的。 》有一个特殊的节点 称为根节点根节点没有前驱节点 》除了根节点外其余节点被分为MM0个相互不想交的集合T1T2T3,...Tm,其中每一个集合Ti1 i m又是一颗结构与树类似的子树。每棵子树的根节点有且只有一个前驱可以有多个后继。 》因此树是递归定义的 注意树的结构中子树之间不能有交集否则就不是树形结构
2.与树相关 节点的度一个节点含有子树的个数例如上图中A的度为6D的度为1。 叶子节点或者终端节点度为零的节点被称为叶子结点。例如HIPQ。 非终端节点或者分支节点度不为零的节点上图中的BCD,E... 双亲节点或者父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点。 孩子节点或者子节点 一个节点含有的子树的根节点称为该节点的子节点如上图的B是A的孩子节点。 兄弟节点具有相同父亲节点的节点互称为兄弟节点。 树的度一棵树中最大节点的度称为树的度如上图树的度为6. 节点的层次从根节点开始根为第一层根的子节点为第二层以此类推。 树的高度或者深度树中节点的最大层次如上图树的高度为4. 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图HI互为堂兄弟。 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先。 子孙以某节点为根的子树中的任意一节点都称为该节点的子孙。如上图A节点是所有节点的子孙。 森林由M棵互不相交的树的集合称为森林。 3.树的表示方法 树的结构相对线性表就复杂多了要存储起来很麻烦既要保存值域也要保存节点与节点之间的关系实际中树的表示方法有很多种如双亲表示法孩子表示法 孩子双亲保护法以及孩子兄弟保护法。在这里介绍最简单的孩子兄弟保护法。
typedef int DataType; struct Node { struct Node* _firstChild1;//第一个孩子节点 struct Node* _pNextBrother;//指向其下一个兄弟节点 DataType _data;//节点中的数据域 }; 4.树的应用 树可以表示文件系统的目录树结构如图
