另一方面,树的概念http://www.Sina.com/:由n (n0 )个节点组成的集合,对于n-1,具有:
有一个被称为根节点的特殊节点,根节点没有前驱节点,除了根节点之外,其馀的节点被分为m(m0 )个互不相交的集合T1、t2、 TM,其中的各集合ti(1=I=m ) 每个子树的根节点都有一个前驱节点,只有一个节点可以有0个以上的后续节点。 因此,各部分树的根节点
树:节点包含一个数据元素和到其他子树的多个分支(指针/索引)
结点:节点拥有的子树的数量
结点的度:角度为0的节点称为叶节点,叶节点也称为终止节点
叶结点:角度不为0的节点(一棵树中除叶节点之外的所有节点都是分支节点) ) ) ) ) ) )。
分支结点(非终端结点):从根节点到经由该节点的分支上的所有节点
祖先结点:以某个节点作为根节点的子树内的所有节点
子孙结点:如果在树某个节点上有孩子节点,则将该节点称为该孩子节点的父母节点
双亲结点(前驱结点):树中一个节点的子树的根节点
孩子结点(后继结点):具有相同父母的节点
兄弟结点:树中所有节点的最大速度
树的度从根节点到树中某个节点的路径上的分支数(根节点的层次为1,其他节点的层次为父母节点的层次加1 ) ) ) ) ) ) ) )。
结点的层次:树中所有节点分层结构的最大值
树的深度:树中所有节点的各子树T0、T1…是有秩序的,也就是说是有秩序的树。 在这里,T1被称为根的第一部分树,T2被称为根的第二部分树
二、树的存储结构计算机存储树的信息需要同时存储节点的数据元素信息和节点间的逻辑关系信息
有序树:父母表示法、子女表示法、父母子女表示法、ljdjd表示法
树的存储结构用指针表示各节点的父母节点
struct Node { struct Node* _pParent; int _data; (;
优点:找一个节点父母节点操作方便
缺点:不方便查找节点的子节点
1、双亲表示法用指针指向每个节点的子节点
struct Node { struct Node* _pChild1; struct Node* _pChild2; struct Node* _pChild3; int _data; (;
优点:找一个节点父母节点操作不方便
缺点:查找节点的子节点很方便
2、孩子表示法用指针表示各个节点的父母节点和各个节点的孩子节点双方。 即父母表示法、孩子表示法
struct Node { struct Node* _pParent; struct Node* _pChild1; struct Node* _pChild2; struct Node* _pChild3; int _data; (; 优点:找某个节点的父母和孩子的节点非常方便
3、双亲孩子表示法表示每个节点的第一子节点,还表示每个节点的下一个兄弟节点
struct Node { struct Node* _pChild1; //第一个子节点struct Node* _pNextBrother; //指向下一个兄弟节点int _data; //节点中的数据域;
三.树的应用文件系统