性質按照人棧與出棧的次序建立的二叉樹入棧操作所代表的結點是左孩子出棧所代表的結點是右孩子
性質除葉子結點外其他結點均有左右孩子 且任一結點的左右孩子的標識互反 即表示某一符號的入棧與出棧操作
性質任一前置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+)
[] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22746.html
