二叉树详解
一:什么是树
1:概念
树是一种非线性的数据结构,它是由n个节点组成的一个具有层次关系的集合,把它叫做树的原因是因为它看起来像一棵倒挂着得树,根朝上,叶子朝下:如图所示:
注意:
树形结构中子树之间不能有交集,否则就不是树形结构
2:树的特点##
1:子树是不能相交的;
2:除了根节点以外,每个节点有且仅有一个父节点;
3:一个N个节点的树有N-1条边;
3:树的一些重要概念
结点的度:一个结点含有子树的个数称为结点的度.如上图,A结点的度为3,B结点的度为2;
树的度:一棵树中,所有结点度的最大值称为树的度
叶子节点:度为0的结点称为叶子结点
结点的层次:从根结点开始,根为第一层,根的子结点为第二层,以此类推
树的高度:树中结点的最大层次,上图树的高度就是3
二:二叉树
1:二叉树的概念
一棵二叉树是由根结点,左子树,右子树组成的,而左子树又是由根结点,左子树,右子树组成的,右子树也是由根结点,左子树,右子树组成的.
所以二叉树是递归定义的
2:二叉树的特点
1:二叉树不存在度大于2的结点;
2:二叉树的子树有左右之分,次序不能颠倒;
3:特殊的二叉树:
1:满二叉树:每一层结点个数都是2^(n-1)个结点(n表示二叉树的层数,从1开始)
如下图:
2:完全二叉树:
二叉树的结点是从上到下,从左到右,依次存放的.
如下图:
三:二叉树的性质
1:若规定根结点的层数为1,则一棵非空二叉树的第i层最多放2^(N-1)个结点.
2:若规定根节点的二叉树的深度为1,则深度为k的二叉树的最大结点数是2^k-1;
3:假设:叶子结点个数有n0个,度为2的结点个数有n2个,则n0=n2+1;
4:共奇数个结点的完全二叉树,没有度为1的结点;共偶数个节点的完全二叉树,只有一个度为1的结点
5:具有n个结点的完全二叉树的深度为log(n+1)向上取整,(log(n)+1向下取整)
6:假设给完全二叉树编号,(从0开始),则编号为i的结点,父节点为(i-1)/2;
左孩子编号为:2i+1,如果2i+1<n,则没有左孩子
右孩子编号为2i+2,如果2i+2<n,则没有右孩子
四:二叉树的存储
二叉树的存储结构分为:链式存储和顺序存储
在这里主要介绍链式存储
/**
* 孩子表示法
*/
static class TreeNode {
int val;//数值域
TreeNode left;//左孩子的引用,
TreeNode right;//右孩子的引用
}
/**
* 孩子双亲表示法
*/
static class TreeNode{
int val;//数值域
TreeNode left;//左孩子的引用
TreeNode right;//右孩子的引用
TreeNode parent;//当前结点父结点的引用
}