重要概念
节点的度:一个节点含有的子树的个数称为该节点的度(就是看有多少根线和此节点相连); 如上图:A的度为6。
叶节点或终端节点:度为0的节点称为叶节点(往下找没有和此节点相连的点);如上图:B、C、H、I...等节点为叶节点。
非终端节点或分支节点:度不为0的节点;如上图:D、E、F、G...等节点为分支节点。
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;如上图:A是B的父节点。
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点(通俗点讲就是和父节点相对称);如上图:B是A的子节点。
兄弟节点:具有相同父节点的节点称为兄弟节点(亲兄弟);如上图B、C是兄弟节点,B、D是兄弟节点,C、D是兄弟节点,他们都有一个相同的父节点A。
树的度:一棵树中,最大的节点的度称为树的度;如上图:树的度为6(因为A拥有最大节点度)。
节点的层次:从根开始定义起,根为第一层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次;如上图:树的高度为4。
节点的祖先:从根到该节点所经分支上所有节点;如上图:A是所有节点的祖先(A是B的父节点,也可以说A是B的祖先)。
子孙:以某节点为根的子树中任一节点都成为该节点的子孙。如上图:所有节点都是A的子孙;以E为根的子树,I、J、P、Q都是E的子孙。
森林:由m(m>0)颗互不相交的多棵树的集合称为森林;
树的表示方式
①顺序表存孩子的指针
C语言
structTreeNode{ intdata ; structTreeNode*child1; structTreeNode*child2; ... }
C++
structTreeNode{ intdata ; vector<structTreeNode*>childs; }
②左孩子右兄弟
typedefintDataType; structNode{ structNode*_firstChild1; //第一个孩子的结点structNode*_pNextBrother; //指向其下一个兄弟结点Datatype_data; //结点中的数据域}
③双亲表示法
树在实际中的运用
表示文件系统的目录树结构。