引入
前面,我们从只能表示父母的双亲表示法,升级到了能同时表示双亲和孩子的双亲父母表示法,在学习孩子兄弟表示法之前,我们先来看看二叉树是什么。
二叉树
树形数据结构有很多种树
,但二叉树是使用范围最广的,也最具有代表意义,所以学习树,我们不能不提二叉树。
对于二叉树(Binary Tree),你应该知道
- 二叉树是 n($n \geq 0$)个结点的有限集合
- 如果集合为空,我们就说这是一个
空二叉树
- 如果不是空,那就是由两棵
互不相交
的二叉树组成 - 我们称这两棵树分别是根的
左子树
和右子树
。
这个定义,是一个递归的形式
- 树有一个根
- 根下有两棵树,左子树、右子树
- 两个棵树各自有一个根
- 两个根又都有左子树和右子树。
我们来具体看看什么是二叉树,上面这个图,我们发现
- 每个结点都只有两个孩子
- 只要孩子在2或者2以内
- 我们都称这个为二叉树
- 相应的,二叉树中不存在大于2的结点
- 可以只有一个、也可以没有子树,单必须小于等于2
左子树和右子树
- 顺序是有区别的
- 即时树中只有一棵子树,我们也要说清楚是左子树还是右子树
- 上面这两个就是完全不同的二叉树,一个是左子树、一个是右子树
二叉树的五种基本形态
- 空二叉树,即什么都没有,
没有根也没有结点。
- 只有一个根节点的二叉树。
- 根节点只有左子树的二叉树
- 根节点只有右子树的二叉树
- 根节点既有右子树也有左子树的二叉树
二叉树的特点
拥有三个结点的普通树
只有以上两种情况
- 两层,即根结点下带有两个结点
- 三层,即根节点下带有一个结点,这个结点下又有一个结点
拥有三个结点的二叉树
就会有以上五种情况
- 因为要区分左右,所以可以是
- 根-左-右(两层)
- 根-左-左
- 根-右-右
- 根-左-右(三层)
- 根-右-左(三层)
切记
二叉树是分左右的!我们下节课讲几种特殊的二叉树。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。