代码随想录 第8章 二叉树

1、理论知识

（1）、满二叉树

如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。

（2）、完全二叉树

除了底层节点可能没有填满，其余每层的节点数都达到了最大值，并且底层的节点都集中在该层最左边的若干位置。

（3）、二叉搜索树

前面介绍的二叉树都没有数值，而二叉搜索树是有数值的。二叉搜索树是一个有序树，满足如下规则：

一、若它的左子树不为空，则左子树上所有节点的值都小于它的根节点的值。

二、弱它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值。

三、它的左、右子树也分别为二叉排序树。

（4）、平衡二叉搜索树

平衡二叉搜索树又称为AVL树，它是一棵空树，或者它的左右两个字树的高度差的绝对值不超过1，并且两个字树都是一棵平衡二叉树。

2、二叉树的遍历

深度优先：递归、迭代；

广度优先：迭代；

编程语言都是通过栈这种数据结构实现递归的，也就是说，前序、中序、后序遍历都可以通过栈使用非递归的方式实现。

而广度优先遍历一般使用队列实现，这也是由队列先进先出的特点决定的，因为通过先进先出的结构，才能一层一层地遍历二叉树。