二叉树及其遍历
什么是二叉树?它是一种树型结构,简单地说,形如下面的图形称为二叉树。
( a ) (b ) ( c ) (d ) ( e )
除空二叉树外,有一个唯一的根接点,左、右子树都是二叉树。
可以得知:
1、 二叉树的每个结点至多只有二棵子树(即不存在结点的度大于2的结点)。
2、 二叉树的子树有左右之分,其次序不能任意颠倒。
二叉树的性质:
1、 在二叉树的第i层上至多有2i-1个结点(i>=1)。
请推导:
2、深度为k的二叉树最多有2k-1个结点。
请推导:
3、 对任何一棵二叉树T,如果其终端结点数为n0个,度为2的结点数为n2个,则n0=n2+1个。
请推导:
满二叉树:是指一棵深度为K且有2k-1个结点的二叉树。
二叉树的遍历方法
比如:有下列二叉树:
a b e c d f
(先序)先根遍历:(根左右)先访问根,再访问左子树,最后访问右子树,则可得如下的序列:abcdef
(中序)中根遍历:(左根右)先访问左子树,再访问根,最后访问右子树,则可得如下的序列:cbdaef
(后序)后根遍历:(左右根)先访问左子树,再访问右子树,最后访问根,则可得如下的序列:cdbfea
练习:
1、表达式(1+34)*5-56/7 的后缀表达式为( )。
A) 1+34*5-56/7 B) -*+1 34 5/56
D) 1 34 5* +56 7/- E) 1 34+5 56 7-*/
解:表达式(1+34)*5-56/7 的后缀表达式即为该表达式对应的二叉树的后序遍历。
所以,首先按运算优先级关系画出(1+34)*5-56/7的二叉树,然后再用后序遍历得出结果。
联系客服