5-2 案例引入

【案例1】数据压缩问题

将数据文件转换成由0、1组成的二进制串,称之为编码

【案例2】利用二叉树求解表达式的值

以二叉树表示表达式的递归定义如下:

  1. 若表达式为数或简单变量,则相应二叉树中仅有一个根结点,其数据域存放该表达式信息
  2. 若表达式为“第一操作数 运算符 第二操作数“的形式,则相应的二叉树中以左子树表示第一操作数,右子树表示第二操作数,根结点的数据域存放运算符(若为一元运算符,则左子树为空)。其中,操作数本身又为表达式

5-3 树和二叉树的抽象数据类型定义

二叉树的抽象数据类型定义

二叉树的部分操作