二叉树及其遍历

什么是二叉树？它是一种树型结构，简单地说，形如下面的图形称为二叉树。

 

 

 

 

       ( a )     (b )           ( c )          (d )       ( e )

除空二叉树外，有一个唯一的根接点，左、右子树都是二叉树。

可以得知：

1、  二叉树的每个结点至多只有二棵子树（即不存在结点的度大于2的结点）。

2、  二叉树的子树有左右之分，其次序不能任意颠倒。

 

二叉树的性质：

1、  在二叉树的第i层上至多有2^i-1个结点（i>=1）。

请推导：

 

 

2、深度为k的二叉树最多有2^k-1个结点。

请推导：

 

 

3、  对任何一棵二叉树T，如果其终端结点数为n0个，度为2的结点数为n2个，则n0=n2+1个。

请推导：

 

 

 

满二叉树：是指一棵深度为K且有2^k-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 7     C） 1 34 +5*56 7/-

    D） 1 34 5* +56 7/-    E） 1 34+5 56 7-*/

解：表达式(1+34)*5-56/7 的后缀表达式即为该表达式对应的二叉树的后序遍历。

所以，首先按运算优先级关系画出(1+34)*5-56/7的二叉树，然后再用后序遍历得出结果。