一、树
1、定义：由n个有限节点组成一个具有层次关系的集合,看起来像一颗倒挂的树,特点:
2、特点：
a、每个节点有0个或多个子节点
b、没有父节点的节点称为根节点（A）
c、每一个非根节点有且只有一个父节点（eg：B和C的父节点为A；D和E和F的父节点为B）
eg：下图的F节点有2个父节点，不能称为树结构
d、除了根节点外,每个子节点可以分为多个不相交的子树
二、树的术语
1、节点的度：一个节点含有的子树的个数（节点A的度度为2，B的度为3，D的度为1，I的度为0）
2、树的度：树中所有节点的度的最大值（度为3）
3、叶节点：度为0的节点（I、J、K）
4、子节点：一个节点含有的子树的根节点称为该节点的子节点（B是A的子节点；D是B的子节点；不能说是D是A的子节点）
5、父节点：若一个节点有子节点,那么这个节点就是其子节点的父节点
6、兄弟节点：具有相同父节点的节点互称兄弟节点
7、堂兄弟节点：在同一层的节点互称堂兄弟节点
8、祖先节点：从根到该节点所经路径上的所有节点（A、B、D都是I的祖先节点）
9、子孙节点：以某节点为根的子树中的所有节点（所有节点都是A的祖先节点）
10、节点层次：根节点层次为1,其他节点层次是父节点的层次加1
11、树的深度：树中所有节点的层次的最大值（深度为4）
12、森林：多颗不相交的树的集合
三、二叉树
1、二叉树：每个节点最多含有两个子树的树称为二叉树
2、完全二叉树：除了最底层外,其他各层的节点数目均达到最大值,且最底层的节点应从左往右紧密排列
3、满二叉树：所有叶节点都在最底层的完全二叉树
4、二叉搜索树：对于一个节点,它的左子树上的所有节点的值都比它小,右子树上的所有节点的值都比它大
四、二叉树的存储结构
1、顺序存储: 从上往下,从左往右的将树存到顺序表中
2、优点: 遍历方便,可以用索引来表示节点间的关系
3、缺点: 可能会对存储空间造成极大的浪费
遍历结果为：5，4，C，None，None，G，H，None，None，None，None，M，N，F，O
4、适用于存完全二叉树
5、链式存储: 每个节点具有 左指针域, 数据域, 右指针域, 以此来连接
优点：不会浪费空间
遍历结果为：5，4，C，G，H，M，N，F，O
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/74315.html
