代码拉取完成,页面将自动刷新
节点的度: 一个节点含有的子树的个数称为节点的度
树的度 : 一棵树中,最大的节点的度称为树的度
叶节点或终端节点:度为零的节点
非终端节点或分支节点: 度不为零的节点
父亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点
兄弟节点: 具有相同父节点的节点互称为兄弟节点
节点的层次: 从根节点开始,根为第一层,根的子节点为第二层,以此类推
深度:对于任意节点n, n的深度为从根到n的唯一路径长,根的深度为0
高度: 对于任意节点n,n的高度为从n到一片树叶的最长路径厂,所有树叶的高度为0
堂兄弟节点:父节点在同一层的节点互称堂兄节点
子孙: 以某节点为根的子树中任一节点都称为该节点的子孙
森林:由m(m>0)颗互不相交的树的集合称为森林
- 无序树
- 有序树
- 二叉树
- 完全二叉树
- 满二叉树
- 平衡二叉树
- 排序二叉树
- 霍夫曼树
- B树
1. 动态创建节点
2. 搜索结点
3. 搜索父节点
4. 遍历
1) 先序 根-左-右
2) 中序 左-根-右
3) 后序 左-右-根
5. 二叉树的深度
6. 查找最大值和最小值
7. 删除节点
1) 删除没有子节点的节点
2) 删除有一个子节点的节点
3) 删除有两个子节点的节点
3) 删除根节点
8. 二叉树的效率
一颗满树,每层节点数大概为2的n-1幂方,那么最底层的节点个数比树的其它节点数多1,因此,查找、插入或删除节点的操作大约有一半都需要找到底层的节点,另外四分之一的节点在倒数第二层,依次类推。
总共N层共有2n-1个节点,那么时间复杂度为O(logn),底数为2。
在有1000000 个数据项的无序数组和链表中,查找数据项平均会比较500000 次,但是在有1000000个节点的二叉树中,只需要20次或更少的比较即可。
有序数组可以很快的找到数据项,但是插入数据项的平均需要移动 500000 次数据项,在 1000000 个节点的二叉树中插入数据项需要20次或更少比较,在加上很短的时间来连接数据项。
同样,从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项,而在 1000000 个节点的二叉树中删除节点只需要20次或更少的次数来找到他,然后在花一点时间来找到它的后继节点,一点时间来断开节点以及连接后继节点。
所以,树对所有常用数据结构的操作都有很高的效率。
遍历可能不如其他操作快,但是在大型数据库中,遍历是很少使用的操作,它更常用于程序中的辅助算法来解析算术或其它表达式。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。