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

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

1）数组存储方式的分析

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

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cee9OVoE-1647763498870)(C:\Users\86155\AppData\Roaming\Typora\typora-user-images\1647675935792.png)]

2）链式存储方式的分析

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

缺点：在进行检索时，效率任然较低，比如(检索某个值，需要从头结点开始遍历)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iq74wP1i-1647763498871)(C:\Users\86155\AppData\Roaming\Typora\typora-user-images\1647677482746.png)]

3）树存储方式的分析

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6rCkoXWd-1647763498875)(C:\Users\86155\AppData\Roaming\Typora\typora-user-images\1647677850995.png)]

树的示意图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TCqJY1iF-1647763498877)(C:\Users\86155\AppData\Roaming\Typora\typora-user-images\1647678048042.png)]

树的常用术语：

1）节点

2）根节点

3. 父节点

4）子节点

5）叶子节点(没有子节点的节点)

6）节点的权(节点值)

7）路径(从root节点找到该节点的路线)

8. 层

9）子树

10）树的高度(最大层数)

从root节点找到该节点的路线)

8. 层

9）子树

10）树的高度(最大层数)

11）森林：多棵子树构成的森林