数据结构6.1:树的基本概念

树结构

为什么需要树这种数据结构

1,数组存储方式的分析

优点:通过索引访问元素,速度块,对于有序数组还可以用二分查找提高检索速度

缺点:如果要检索具体的某个值,或者需要增删(需要创建新数组)会比较麻烦

2,链式存储方式的分析

优点:增删效率优秀

缺点:检索效率低

3,树存储方式

能提高数据的存取效率,比如利用二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也能保证数据的插入删除和修改的速度.

以二叉排序树为例

[7,3,10,1,5,9,12]

比父节点小的子节点放在左边,大的放在右边

当检索时,每次比较可以排除一半的元素,有较高的检索效率

当添加时,只需要按规则添加在对应的节点下即可

删除叶节点时,只需将其父节点的指针移除即可

树的常用术语

1,节点

2,根节点:最顶端的节点

3,父节点

4,子节点

5,叶节点:没有子节点的节点

6,节点的权(节点值):节点内存放的数据

7,路径:从根节点到节点的路线

8,层:处于同一个级别的节点为一层

9,子树:节点的所有后代节点构成该节点的子树

10,树的高度:即树的最大层

11,森林:多颗子树构成森林

二叉树

每个节点最多只能存在两个子节点的一种形式称为二叉树

二叉树的子节点分为左节点和右节点

二叉树概念

如果所有叶子节点都在最后一层,且节点总数为2^n-1(n为层数),则称为满二叉树

如果二叉树的所有叶子节点都在最后一层或者倒数第二层,且最后一层的叶子节点在左侧连续,倒数第二层的叶子节点在右边连续,则称之为完全二叉树

二叉树的遍历

二叉树的前序遍历

先输出父节点,再遍历左子树和右子树

二叉树的中序遍历

先遍历左子树,再输出父节点,再遍历右子树

二叉树的后序遍历

先遍历左子树,再遍历右子树,最后输出父节点

代码实现放在下一节