|
性质按照人栈与出栈的次序建立的二叉树入栈操作所代表的结点是左孩子出栈所代表的结点是右孩子 性质除叶子结点外其他结点均有左右孩子 且任一结点的左右孩子的标识互反 即表示某一符号的入栈与出栈操作 性质任一前置O栈序列对应唯一的一棵二叉树 根据前置O栈序列的性质构造二叉树的算法描述如下 () 建立一个保存指向结点指针的栈stack () 建立一个仅有一个结点O的二叉树使指针P指向根结点O () 接收一个符号ch如果ch为NULL则二叉树构造完成结束 () 建立一个值为ch的结点node () 如果ch 表示人栈操作则P所指结点的左孩子指向node将指针P压入stack栈中保存再使P指向node结点 () 如果ch表示出栈操作则从stack栈中强出指针值赋予PP所指结点的右孩子指向node 再使P指向node结点 () 转() 具有上述性质的二叉树的前序遍历与文献[]所提求() 到 (nn)不通过y=z的路径一一对应这种对应关系可描述为以根结点O为原点遍历到的结点是某一结点的左子树 就向右走一格相当于入栈操作当遍历到的结点是某一结点的右孩子就向上走一格相当于出栈操作这样就形成从()到(nn )的一条路径每一个前置O栈序列都对应一条从 ()到(nn )的路径求具有上述性质的二叉树的总数变为求文献[]中所提求从()到(nn ) 且中途所经过的点(ab)满足a≤b的路径数由文献[]可得这样的路径数为C(nn)／(n+) [] [] [] [] [] [] [] [] |
