树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。
正常的树:
数据结构中的树:
树形结构中,子树之间不能相交,否则便不是树形结构
一个树可以看成根节点和多棵子树,多颗子树又可以看出一个全新的树,分为根节点和多颗子树
节点的度:一个节点含有的子树的个数成为该节点的度;例如上图中:A的度为 6 ,E的度为 2
叶子节点(终端节点):度为0的节点,好比:真实的树叶子后面就没有东西了,所以叫叶子节点或终端节点,例如上图中的: B C H I … …
分支节点(非终端节点):度不为0的节点,好比:真实的树后面还有东西它肯定是树干,不可能是叶子,所以叫分支节点或非终端节点,例如上图: A D E F … …
双亲节点(父节点):若一个节点后面还有节点,那么它就叫做这个节点的父节点;例如:D是H的父节点
孩子节点(子节点):如果一个节点有父节点,那么他就是这个父节点的子节点;例如: B是A的子节点
树的度: 一棵树,最大节点的度就是这颗树的度;上图树的度就是6
节点的层次: 从根节点定义起,根为第1层,根的子节点为第2层,依次递推
树的高度或深度:现实生活中,我们把树用高度定义,数据结构中树反过来了,所以我们又多了一种定义的方法用深度表示高度;树中最大的层次叫做树的高度或深度;上图中树的高度:4
节点的祖先:从根到该节点所走过的所有节点;例如:Q的祖先->A->E->J
兄弟节点:具有相同父节点的节点成为兄弟节点;例如:I 和 J就是兄弟节点
堂兄弟节点:这两个节点的双亲互为亲兄弟;例如:H和I就是堂兄弟
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林 ;
注:
1、一个子节点只能有一个父节点,但是一个父节点可以有多个子子节点,就好比现实生活
2、这些只是概念,只要知道他们各自代表啥意思就好,加粗的重点记忆
树形结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系。
大家是不是觉得用链表存储就可以了,但是,一个树的度不确定,你如何规定结构体中孩子指针的个数呢?
typedef int DataType;
struct Node
{
DataType data; // 结点中的数据域
struct Node* child1;
struct Node* child2;
struct Node* child3;
};
这样写,如果有一个节点的度为6,这个结构就错误了。
尽管你知道树的度,也不好表示
你知道它的度为3,但是有些度又为1,你定义三个孩子指针不就浪费了。
这些我们都不用思考了,有大神给我们想出来如何解决了,我们只管使用就好。
实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里就简单的了解其中最常用的孩子兄弟表示法
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
怎么样,是不是觉得好巧啊,自己怎么想不出来呢?大神嘛,还是很少的,万里挑一。
用这中方法不管你的度是多少,我都只用两个指针就可以表示完了。
著名的Linux系统,它的目录结构就是树形结构。
Windows中的存储结构是森林。