|
假设入栈操作由正数表示出栈操作由负数表示正数和负数都看作一个符号在每一组人栈和出栈序列前加一个符号O将该串称为前置符号O的入栈和出栈序列(文中简称前置O栈序列)该序列构成n+ 个符号的串把该串看作一棵二叉树的前序遍历序列如图所示当n为时仅有一种前置O栈序列O+O表示栈底+表示入栈表示出栈对应的二叉树如图 (a)所示在图 (a)的某个叶子结点上增加一对左右孩子则形成图 (b)的两棵树正好对应n=时的两种前置O栈序列图(b)的第一棵树的前序遍历为O++其意义是O栈底入栈入栈出栈l出栈同理图(b)的第棵树的前序遍历为O++分别表示O栈底入栈 l出栈入栈出栈在图l(b)任一棵树的任一叶子结点上增加一对左右孩子 则构成一棵新的二叉树新产生的树共有棵在这棵树中有两棵树同构（两棵树具有相同的形 状）所以当n=时共有种出栈序列 前置O栈序列对应的二叉树具有以下性质 [] [] [] [] [] [] [] [] |
