java数据结构和算法——二叉树的介绍

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

1、数组存储方式的分析

• 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
• 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

2、链式存储方式的分析

• 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)
• 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

3、树存储方式的分析

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

二、二叉树的示意图及树的常用术语

1、二叉树的示意图
2、树的常用术语(结合示意图理解)

• 节点：示意图中每一个圆圈，其实是每一个对象表示一个节点。
• 根节点：示意图中A，因为A上面没有父节点就是根节点。
• 父节点：示意图中A是B和C的父节点，B又是D和E的父节点。
• 子节点：示意图中B和C是A的子节点，D和E是B的子节点。
• 叶子节点 (没有子节点的节点)：示意图中H、E、F、G没有子节点，所以叫叶子节点。
• 节点的权(节点值)：示意图中如果A表示Emp雇员对象，该Emp雇员对象有id编号属性，该属性的值如果是10，即10就是节点的权或者节点的值。
• 路径(从root节点即根节点找到该节点的路线)：示意图中比如查找D节点，需要从根节点A开始查找，先找到B,再从B找到D，从A到B再到D的路线叫做路径。
• 层：示意图中从所有节点从横向查看，A表示第一层，B和C表示第二层，D和E和F和G表示第三层，H表示第四层。
• 子树: 示意图中虚线三角形组成结构是A的子树。
• 树的高度(最大层数):示意图中最大层数为4层。
• 森林 ：多颗子树构成森林。

三、二叉树的概念

• 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

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

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

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