二叉树的基本概念(为什么需要树这样数据结构+树示意图+二叉树的概念+二叉树的遍历说明)_为什么要有树这种数据结构

二叉树的基本概念

一、为什么需要树这样数据结构

1.数组存储方式分析

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

缺点：如果要检索某一个具体值，效率比较低下

2.链式存储方式分析

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

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

3.树存储方式分析

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

二、树示意图

三、二叉树的概念

• 每个节点最多有两个子节点的树叫做二叉树

• 二叉树有左节点和右节点，即左子树和右子树
  

• 如果二叉树的所有叶子节点都在最后一层并且总结点数 = 2^n-1，(n为层数)，则我们称为满二叉数。

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

四、二叉树的遍历说明

深度优先遍历包括：前序遍历，中序遍历，后序遍历

//前序遍历顺序 父节点 左子树 右子树 A B D H I E C F G
1

//中序遍历顺序 左子树 父节点 右子树 H D I B E A F C G
1

//后序遍历顺序 左子树 右子树 父节点 H I D E B F G C A
1

广度优先遍历

从上到下，从左到右遍历

可以使用队列辅助来写算法