神马文学网二叉树及其遍历
来源：百度文库 编辑：神马文学网 时间：2024/04/27 12:04:25
二叉树及其遍历
什么是二叉树？它是一种树型结构，简单地说，形如下面的图形称为二叉树。
( 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的二叉树，然后再用后序遍历得出结果。