二叉树是一种树形存储结构,每个节点最多有两个子节点,通常叫做左子树和右子树。
更多二叉树的介绍可查看维基百科
注释最顶部的节点称为根节点
,在节点下方与该节点直接相连的节点叫做子节点
,反过来称为父节点
,没有子节点的称为叶子节点
,从根节点到最底下的叶子节点经过的节点数就是树的高度,也就是树的最大层数。在上面的二叉树中,1是根节点,2和3是1的子节点,1是2的父节点,4,5,6,7是叶子节点,树的高度是3。
上面这个二叉树也称为满二叉树,因为它满足除最后一层以外,其它层的节点都有两个子节点,除了满二叉树,还有一种常提到的是完全二叉树,它的特点是除最后一层以外,其它层都是满的,最后一层要么是满的,要么就是右边缺若干个节点,下面这个就是完全二叉树。
还有一些经常能听到或者用到的二叉树,比如
还有一种树,虽然不是二叉树,但是也经常用到,那就是Trie树,又叫前缀树和字典树,可以用来高效的查找字符串。
关于二叉树,最基础的就是二叉树的遍历,二叉树常见的遍历有以下几种:
上面这棵树的几种遍历结果。
前序遍历:[1,2,4,5,3,6,7]
中序遍历:[4,2,5,1,6,3,7]
后序遍历:[4,5,2,6,7,3,1]
层次遍历:[1,2,3,4,5,6,7]
下面是二叉树几种遍历方式的Java代码实现,除了层次遍历外,都有递归和迭代的实现。