数据结构--树
@(数据结构)
树是节点的有限集合
基本概念
树.png
- 双亲(父结点) ：A是BCD的双亲，双亲指的是一个结点
- 孩子（子结点）：BCD是A的子结点
- 度：当前结点直接的孩子，A的度是3，B的度为2，C的度为0
- 叶子（叶结点）：终端结点（C、E、F、G、H）
- 根（根结点）：非终端结点（A、B、D）
- 有序树：如果E和F不可以换顺序就是有序
- 无序树：E和F可以换顺序，不影响逻辑就是无序树
- 祖先：E的 祖先 是 A 、B
- 子孙：下面全部结点都是A的子孙
- 深度：从上而下，为一到三层的深度
- 结点深度：A的结点深度为1，B为2，E为3
- 树深度：当前树的最大深度
二叉树
所有结点的度都小于等于2
不用的遍历其实就是访问根结点的顺序的不同
前序遍历
前序遍历.png
- 首先访问根结点
- 访问顺序 ：根结点 --> 左结点 --> 右结点
- 对于上图的树，前序遍历结果为（忽略结点C）：
- A - B - E - F - D - G - H
中序遍历
中序遍历.png
- 中间访问根结点
- 访问顺序：左结点 --> 根结点 --> 右结点
- 对于上图的树，中序遍历结果为（忽略结点C）：
- E - B - F - A - G - D - H
后序遍历
后序遍历
- 最后访问根结点
- 访问顺序： 左结点 --> 右结点 --> 根节点
- 对于上图的树，后序遍历结果为（忽略结点C）：
- E - F - B - G - H - D - A
数组编码概述
-
放入数组的顺序就是从上到下，从左到右
数组与结点的转换.png 关于使用数组来实现二叉树，基本就是通过上图的关系，让数组下标和节点位置产生关联，基本就和线性表中的顺序表实现差不多
链表实现二叉树
-
之前的文章中有写到了关于线性表中链表的实现，而在二叉树中，链表的实现可以把它想象成是 三链表的实现， 每一个结点都持有着
- 自己的父结点指针
- 自己的左结点指针
- 自己的右结点的指针
关键一点就是对于结点的查找，因为无论是增加还是删除结点都基本运用到查找方法，通过结点不断的指向，一层一层去追溯来找到目标结点。
对于二叉树的实现方面简单略过了，因为基本和线性表中的思路是一致的，重点把握二叉树的概率，以及三种方式的遍历。
