1、理论知识
(1)、满二叉树
如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。
(2)、完全二叉树
除了底层节点可能没有填满,其余每层的节点数都达到了最大值,并且底层的节点都集中在该层最左边的若干位置。
(3)、二叉搜索树
前面介绍的二叉树都没有数值,而二叉搜索树是有数值的。二叉搜索树是一个有序树,满足如下规则:
一、若它的左子树不为空,则左子树上所有节点的值都小于它的根节点的值。
二、弱它的右子树不为空,则右子树上所有节点的值都大于它的根节点的值。
三、它的左、右子树也分别为二叉排序树。
(4)、平衡二叉搜索树
平衡二叉搜索树又称为AVL树,它是一棵空树,或者它的左右两个字树的高度差的绝对值不超过1,并且两个字树都是一棵平衡二叉树。
2、二叉树的遍历
深度优先:递归、迭代;
广度优先:迭代;
编程语言都是通过栈这种数据结构实现递归的,也就是说,前序、中序、后序遍历都可以通过栈使用非递归的方式实现。文章来源:https://www.uudwc.com/A/8dnw9/
而广度优先遍历一般使用队列实现,这也是由队列先进先出的特点决定的,因为通过先进先出的结构,才能一层一层地遍历二叉树。文章来源地址https://www.uudwc.com/A/8dnw9/