- 树
- 二叉树
- 二叉树的性质
- 常见的二叉树
- 满二叉树
- 完全二叉树
- 二分搜索树
- 二叉树的遍历
- 前序遍历
- 小结
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
- 有一个特殊的节点,称为根节点,根节点没有前驱节点
- 除根节点外,其余节点被分成M(M > 0)个互不相交的集合,每棵子树的根节点有且只有一个前驱,可以有0个或多个后继
- 树是递归定义的
出现树这种结构,基本上就是高效的查找与搜索的语义
树的基本概念
-
子树不相交
-
除了根节点没有父节点以外,每个节点有且只有一个父节点
-
树中边的个数x(两个节点连成一条边),和树中节点的个数n的关系,x = n - 1
-
树和节点的度
树的度:该树中最大的节点的度,就是树的度
节点的度:该节点包含子树的个数,就称为节点的度,该节点有1个子树该节点的度就为1,有两个子树就为2
-
叶子节点,度为0的节点就是叶子节点,非叶子节点,度不为0的节点
-
根节点:没有父节点的节点,树中有且只有一个树节点
-
节点的层次:从根节点开始数,根节点为第一层,根节点的子树就为第二层,根节点子树的子树就位第三层,依此类推
-
树的高度:当前树中节点层次最大的即为树的高度
树的每个节点最多有两个子树,不存在度大于2的节点,这样的树称为二叉树
二叉树的子树有左右之分,其子树的次序不能颠倒,因此二叉树是有序树
这两颗树并不相等,是两个完全不同的树
二叉树的性质- 在深度为k的的二叉树中最多存在2^k -1 个节点
- 在第k层中,该层最多有2^(k - 1)个节点
- 因为二叉树都满足节点个数n和边长x ,具有 x = n - 1 ,因此在二叉树中,度为2的节点和度为0的节点有以下关系,度为2的节点个数为n2,度为0的节点个数为n0
- n0 = n2 + 1 ------> 推导 二叉树中结点满足 n0+n1+n2 = n ,边长满足n1 + 2n2 = n -1
满二叉树:在该二叉树中,每一层的节点个数都是该层的最大值
完全二叉树完全二叉树:完全二叉树的结点编号,和对应的满二叉树相应位置的结点编号一致
完全二叉树只能是最后一层是不满的,并且结点都是靠左排列
在完全二叉树中,若存在度为1的节点,这个节点必然只有左子树没有右子树,且这个结点在二叉树中只能存在一个,否则就不是完全二叉树
关于完全二叉树的编号问题
1.若根节点从1开始编号
任意一个节点x,既存在子树也有父节点,则该节点的父节点编号为 “x/2”,左子树的节点编号为"2x",右子树的编号为"2x+1";
2.若根节点从0开始编号
任意一个节点x,既存在子树也有父节点,则该节点的父节点编号为"(x-1)/2",左子树的节点编号为"2x+1",右子树的节点编号为"2x+2";
二分搜索树二分搜索树(BST):节点值之间有大小关系
左子树节点值 < 根节点值 < 右子树节点值
若在BST中查找一个元素,就是二分查找,若比根节点小就在左树中查找,若比根节点大就在右树中查找,若相等,说明找到了
二叉树的遍历二叉树的遍历,是二叉树的基础操作,所有二叉树的问题的解决思路基本都是遍历问题的衍生
遍历的概念:按照一定的顺序访问这个集合的所有元素,做到不重复,不遗漏
对于二叉树来说,一共有四种遍历方式,分别是:”前序遍历、中序遍历、后序遍历和层序遍历",前序、中序、后序遍历称为深度优先遍历(dfs),层序遍历称为广度优先遍历()
前序遍历前序遍历:先访问根节点,再递归访问左子树,之后再递归访问右子树
根左右的访问顺序
中序遍历:先递归访问左子树,然后访问根节点,之后递归访问右子树
左根右的访问顺序
后序遍历:先递归访问左子树,再递归访问右子树,最后访问根节点
左右根的访问顺序
层序遍历:从上至下,一层层先左后右遍历
上面的二叉树的各种遍历结果为
前序遍历:ABDEC
先访问根节点A,直接输出根节点A,因为是先递归访问左子树,所以向左走,走到B直接输出,然后B还有左子树继续向左走,走到D也是直接输出D,之后因为D的左子树为空,就访问B的右子树E,E的左右子树都为空,所以输出E,此时A的左子树已经全部访问,就到访问A的右子树C,C的左右子树都为空,输出C,所以是ABDEC
中序遍历:DBEAC
先访问根节点A,此时不能输出要第二次访问到才能输出,向左走走到B,同理继续向左走走到D,D也继续向左走,左树为空返回,再次访问到D,此时就可以输出D,访问完D又回到了根节点B,B是第二次访问,也可以输出,然后访问B的右子树E,接着访问E的左子树,E的左子树为空,第二次访问E输出E,E的右子树为空,此时A的左子树访问完毕,返回到A此时第二次访问A输出A,接着访问A的右子树C,C的左右子树为空,输出C
后序遍历:DEBCA
先访问根节点A,此时不能输出要第三次访问到才能输出,向左走走到B,B有左右子树一样不能输出继续向左访问,走到D,D向左访问为空回到D此时第二次访问到,之后再向右访问也是空再回到D,此时第三次访问到D输出D,之后回到B节点此时第二次访问到B节点不输出,向右访问走到E,E和D同理左右子树都为空,第三次访问到E输出E,之后再返回访问到B,此时第三次访问到输出B,这时A的左子树已经访问完毕,返回到A,第二次访问到A不输出,向右访问C,C的左右子树为空输出C,随后返回访问A,A第三次访问输出A
层序遍历:ABCDE
直接从上至下,从左到右依次访问
此二叉树的各种结果为
前序遍历:A B D E G H C F
中序遍历:D B G H E A C F
后序遍历:D H G E B F C A
层序遍历:A B C D E F G H
小结1.前序遍历的第一个节点一定是根节点
2.中序遍历左子树在根节点的左侧,如B节点的左子树D在B的左侧,E在B的右侧,而E这个节点只有左子树所以G在E的左侧,而右侧为空,任何一个结点都满足
3.后序遍历的最后一个节点一定是根节点
后序遍历的结果一转置,reverse就变成了ACFBEGHD,变成了"根右左"访问顺序



