Completed
标签
二叉树
相关企业
难度
简单
二叉树种类
二叉树包括普通二叉树、满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树、红黑树、B树、B+树、B*树
普通二叉树
普通二叉树没有任何性质，每个节点的子节点可以是0或1或2
满二叉树
满二叉树的每一层节点都有两个子节点
完全二叉树
完全二叉树除了最后一层不是满的，其余层全是满的，且最后一层的所有节点都在左边
二叉搜索树
二叉搜索树的每个节点的左节点（如果存在）的值小于当前节点的值，右节点（如果存在）的值大于当前节点的值
平衡二叉搜索树
在二叉搜索树的基础上更加平衡，一个节点的左右两个树的高度差不大于1
红黑树、B树、B+树、B*树
待完善……
二叉树的存储方式
二叉树主要是以链表格式存储，也可以使用数组格式存储
链表存储
每个节点包括一个val、一个左节点和一个右节点，直接访问left或right即可到达当前节点的左节点和右节点
数组存储
数组存储以顺序存储的方式，按每行依次填入数组，看起来可能更直观，但当想找到当前节点的左右节点时就比较麻烦。如下标i的左节点为i*2+1，右节点为i*2+2
二叉树的遍历
二叉树的所有遍历，无论如何修改都逃不出前序遍历、中序遍历、后续遍历和层序遍历。前三个多用递归实现，层序遍历多用队列实现。以下遍历举例，都以下图的二叉树为例，以当前二叉树的根节点4来划分，分为左，中，右。
前序遍历
这里的前，指的是”中左右”里“中”的位置在前。在遍历一个节点的时候，先输出中节点，也就是自己的值，再输出当前节点的左节点的值，再输出当前节点右节点的值。下面一步步展示当前二叉树的前序遍历
下面是前序遍历这个以root为根节点的树的代码实现
中序遍历
类似的，这里的中，指的是”左中右”里的”中”的位置在中间。在遍历每一个节点的时候，先输出当前节点的左节点的值，再输出中节点，也就是自己的值，再输出当前节点右节点的值，下列步骤同上
下面是中序遍历这个以root为根节点的树的代码实现
后序遍历
类似的，这里的后，指的是“左右中”里的“中”的位置在最后。在遍历每一个节点的时候，先输出当前节点的左节点的值，再输出当前节点右节点的值，再输出中节点，也就是自己的值，下列步骤同上
下面是后序遍历这个以root为根节点的树的代码实现
层序遍历
层序遍历与前三者不同，多用队列来实现，和其名字一样，就是一层一层的遍历输出二叉树的值
