2011考研考研備考數(shù)據(jù)結(jié)構(gòu)之出棧序列的研究[2]_跨考網(wǎng)

假設(shè)入棧操作由正數(shù)表示，出棧操作由負(fù)數(shù)表示，正數(shù)和負(fù)數(shù)都看作一個(gè)符號(hào)。在每一組人棧和出棧序列前加一個(gè)符號(hào)O，將該串稱為前置符號(hào)O的入棧和出棧序列(文中簡(jiǎn)稱前置O棧序列)，該序列構(gòu)成2n+ 1個(gè)符號(hào)的串，把該串看作一棵二叉樹的前序遍歷序列，如圖1所示，當(dāng)n為1時(shí)，僅有一種前置O棧序列：O、+1、-1，O表示棧底，+1表示1入棧，-1表示1出棧，對(duì)應(yīng)的二叉樹如圖1 (a)所示。在圖1 (a)的某個(gè)葉子結(jié)點(diǎn)上增加一對(duì)左右孩子，則形成圖1 (b)的兩棵樹，正好對(duì)應(yīng)n=2時(shí)的兩種前置O棧序列。圖1(b)的第一棵樹的前序遍歷為O、+1、+2、-2、-1，其意義是，O棧底，1入棧，2入棧，-2出棧，-l出棧，同理，圖1(b)的第2棵樹的前序遍歷為O、+1、-1、+2、-2，分別表示O棧底，1入棧、 -l出棧、2入棧、-2出棧。在圖l(b)任一棵樹的任一葉子結(jié)點(diǎn)上增加一對(duì)左右孩子， 則構(gòu)成一棵新的二叉樹，新產(chǎn)生的樹共有6棵，在這6棵樹中有兩棵樹同構(gòu)（兩棵樹具有相同的形

狀），所以當(dāng)n=3時(shí)共有5種出棧序列。?

前置O棧序列對(duì)應(yīng)的二叉樹具有以下性質(zhì) ：