一、树

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

数组存储方式的分析

  • 优点：通过下标方式访问元素，速度快， 对于有序数组 还可以使用二分法查找提高检索速度。

  • 缺点：如果要检索具体某个值，或者插入值（按照一定顺序）会整体移动 ，效率较低

链式存储方式的分析：

  • 优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好）

  • 缺点：在进行检索时，效率仍然比较低，比如（检索某个值，需要从头节点开始遍历）

树存储方式的分析：

  • 能提高数据存储，读取的效率，比如利用 二叉排序树，即可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

image.png

2、树的常用术语

image.png

  • 节点【一个小圆圈就是一个节点】

  • 根节点【最上面的那一个就是根节点，根节点没有父节点】

  • 父节点【A是B和C的父节点】

  • 子节点【B和C是A的子节点】

  • 叶子结点【没有子节点的节点】[H,E,F,G 就是叶子节点，没有子节点]

  • 节点的权【节点的值】

  • 路径【从root节点找到该节点的路线】

  • 层【1层，2层，3层，处于同一个级别的为一层】

  • 子树【虚线三角形是D作为根的子树】

  • 树的高度【最大层数】

  • 森林：多棵子树构成森林

  • 深度【一个节点的深度是从根节点到自己边的刷领】

    3、二叉树的概念

  1. 树有很多种，每个节点最多只能有两个节点的一种形式成为二叉树

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

  3. 示意图

image.png

  1. 如果该二叉树的所有叶子节点都在最后一层，并且节点总数= 2 -1 , n 为层数，我们称为 满二叉树**

image.png

  1. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为 完全二叉树

image.png

4、二叉树的遍历

前序遍历：先输出父节点**，再遍历左子树和右子树**

中序遍历：先遍历左子树，**再输出父节点，再遍历右子树**

后续遍历：先遍历左子树，再遍历右子树，**最后输出父节点**

通过父节点 来区分是什么遍历