三河市燕郊建委网站:二叉树是什么

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

　　( 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 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的二叉树，然后再用后序遍历得出结果。

买本数据结构看看吧！光说也说不明白！

一看就懂

这是什么啊，这么长，看不懂