栈的出栈序列个数 出栈序列的研究[3]

出栈序列的研究[3]  

性质 按照人栈与出栈的次序建立的二叉树 入栈操作所代表的结点是左孩子 出栈所代表的结点是右孩子  

性质 除叶子结点外 其他结点均有左右孩子   且任一结点的左右孩子的标识互反 即表示某一符号的入栈与出栈操作  

性质 任一前置O栈序列对应唯一的一棵二叉树

根据前置O栈序列的性质构造二叉树的算法描述如下

( ) 建立一个保存指向结点指针的栈stack 

( ) 建立一个仅有一个结点O的二叉树 使指针P指向根结点O 

( ) 接收一个符号ch 如果ch为NULL 则二叉树构造完成 结束  

( ) 建立一个值为ch的结点node

( ) 如果ch 表示人栈操作 则P所指结点的左孩子指向node 将指针P压入stack栈中保存 再使P指向node结点  

( ) 如果ch表示出栈操作 则从stack栈中强出指针值赋予PP所指结点的右孩子指向node再使P指向node结点  

( ) 转( ) 

具有上述性质的二叉树的前序遍历与文献[ ]所提求( ) 到 (n n)不通过y=z的路径一一对应 这种对应关系可描述为 以根结点O为原点 遍历到的结点是某一结点的左子树 就向右走一格 相当于入栈操作 当遍历到的结点是某一结点的右孩子 就向上走一格 相当于出栈操作 这样就形成从( )到(n n )的一条路径 每一个前置O栈序列都对应一条从

( )到(n n )的路径 求具有上述性质的二叉树的总数变为求文献[ ]中所提求从( )到(n n )且中途所经过的点(a b) 满足a≤b的路径数 由文献[ ]可得 这样的路径数为C( n n)／(n+ )