怎么根据二叉树的前序,中序,确定它的后序
可以。但是只有前后求中就不行。用递归去算吧。二分。例如前:abcdfe
中:badfce
即
a
/
\
b
c
/
\
d
e
\
f
这时,先拿到前序的a,a必定是这棵树的根,然后在中序中找到a,把a前a后的分为2部分,即b和dfce;然后按照1:4将前序剩余部分分开,得到b和cdfe;然后分别递归;因为是求后序,所以在两边递归完了再输出本子树的根。
怎么根据二叉树的前序,中序,确定它的后序
二叉树遍历分为三类:前序遍历,中序遍历和后序遍历。
前序遍历:先访问根节点,然后遍历左子树,最后遍历右子树;并且在遍历左,右子树时,仍需先访问根节点,然后遍历左子树,最后遍历右子树。
中序遍历:先遍历左子树,然后访问根节点,最后遍历右子树;并且在遍历左,右子树时,仍先历左子树,然后访问根节点,最后遍历右子树。
后序遍历:先遍历左子树,然后遍历右子树,最后访问根节点;并且在遍历左,右子树时,仍先历左子树,然后遍历右子树,最后访问根节点。
由中序和后序可以知道B,C,D,E是左子树,H,F,G是右子树,A是根节点。因为后序遍历最后访问的是根节点。在左子树中C是D和B的子节点,E是C的子节点,在右子树中H是G和F的子节点,
A是根节点。最后可以推出前序序列是:AECDBHGF
绛旓細渚濇嵁鍓嶅簭閬嶅巻搴忓垪鍙‘瀹氭牴缁撶偣涓篈锛涘啀渚濇嵁涓簭閬嶅巻搴忓垪鍙煡鍏跺乏瀛愭爲鐢盌BE鏋勬垚锛屽彸瀛愭爲涓篎C锛涘張鐢卞乏瀛愭爲鐨勫墠搴忛亶鍘嗗簭鍒楀彲鐭ュ叾鏍圭粨鐐逛负B锛岀敱涓簭閬嶅巻搴忓垪鍙煡鍏跺乏瀛愭爲涓篋锛屽彸瀛愭爲鐢盓鏋勬垚銆傚悓鐞嗘帹绠桭C鐨勬帓鍒楅『搴忥紝鍦ㄨ崏绋跨焊涓婄敾鍑烘爲鐨勭粨鏋勶紝寰楀嚭绛旀涓:DEBFCA銆鏍规嵁浜屽弶鏍戠殑鍓嶅簭搴鍒楀拰涓簭搴鍒楀彲浠ョ敾...
绛旓細浜屽弶鏍戠殑鍓嶅簭涓簭鍚庡簭鐪嬫硶濡備笅锛氬厛搴忛亶鍘嗭紙鍏堟牴閬嶅巻锛夛細鍏堣闂牴鑺傜偣锛岀劧鍚庤闂乏瀛愭爲锛屾渶鍚庤闂彸瀛愭爲銆備緥濡傦紝瀵逛簬浜屽弶鏍1涓2涓3涓4涓5锛屽厛搴忛亶鍘嗙殑缁撴灉涓1涓2涓3涓4涓5銆備腑搴忛亶鍘嗭紙涓牴閬嶅巻锛夛細鍏堣闂乏瀛愭爲锛岀劧鍚庤闂牴鑺傜偣锛屾渶鍚庤闂彸瀛愭爲銆備緥濡傦紝瀵逛簬浜屽弶鏍1涓2涓3涓4涓5锛屼腑搴閬嶅巻鐨...
绛旓細瀹屽叏鍙互銆備緥濡傦細鍏堝簭abdecf锛屼腑搴dbeafc銆傚垎鏋愭濊矾銆1銆佸厛搴忓氨鏄牴宸﹀彸锛屼腑搴忓氨鏄乏鏍瑰彸銆傛墍浠ュ湪鍏堝簭涓璦鍦ㄥ墠鍗充负鏍广傚湪涓簭涓壘鍒癮锛屽垯dbe涓哄叾宸﹀瓙鏍戯紝fc涓哄叾鍙冲瓙鏍戙2銆乨be宸﹀瓙鏍戝湪鍏堝簭涓璪鍦ㄥ墠璇存槑b涓烘牴锛屽垯涓簭涓璬涓篵宸﹀瓙鏍戯紝e涓篵鍙冲瓙鏍戙3銆佸悓鐞唂c鍦ㄥ厛搴忎腑c鍦ㄥ墠璇存槑c涓烘牴锛屼腑搴忎腑...
绛旓細鍙堢敱浜涓簭閬嶅巻宸︽牴鍙充负8 6锛屽彲鐭8涓烘牴鑺傜偣6鐨勫乏瀛愭爲 鍥犳璇ュ瓙鏍戞牴鑺傜偣涓6锛屽乏瀛愭爲涓8锛屾棤鍙冲瓙鏍 濡傛灉鎸変綘璇寸殑鍙充负8锛岄偅涔堝叾涓簭閬嶅巻搴斾负6 8鑰屼笉鏄8 6 鎬讳箣鍏堥氳繃鍓嶅簭閬嶅巻鍙互纭畾鏍硅妭鐐癸紝鍐嶉氳繃涓簭閬嶅巻鎵嶈兘纭畾宸﹀彸瀛愭爲 涓瀹氳涓よ呯粨鍚堟墠鑳藉緱鍒浜屽弶鏍戠殑瀹屾暣缁撴瀯锛屼笉鑳藉彧鐪嬪叾涓箣涓 鐮佸瓧涓嶆槗...
绛旓細鐢鍓嶅簭閬嶅巻锛孌EG鍦˙鑺傜偣涓嬮潰锛岀敱涓簭閬嶅巻锛孌鏄疊鐨勫乏鑺傜偣锛孏E鏄疊鐨勫彸鑺傜偣銆傜敱鍓嶅簭閬嶅巻锛孍鏄疓鐨勬牴鑺傜偣锛岀敱涓簭閬嶅巻锛孏鏄疎鐨勫乏瀛愯妭鐐广傜敱鍓嶅簭閬嶅巻锛孋鏄浜屽弶鏍戠殑鍙虫牴鑺傜偣锛岀敱涓簭閬嶅巻锛孋涓嶅惈宸﹀瓙鑺傜偣锛孒F涓篊鐨勫彸瀛愯妭鐐广傜敱鍓嶅簭閬嶅巻锛孎涓篐鐨勬牴鑺傜偣锛岀敱涓簭閬嶅巻锛孒涓篎鐨勫乏瀛愯妭鐐广傚湪浜屽弶鏍...
绛旓細1銆佸厛搴忔垨涓簭涓虹┖鍒欒繑鍥烇紝鍚﹀垯锛岄氳繃鍏堝簭搴鍒楀垱寤烘牴缁撶偣锛屽啀閫氳繃鏍硅妭鐐瑰湪涓簭閬嶅巻鐨勪綅缃壘鍑哄乏鍙冲瓙鏍戙2銆佸湪鏍圭粷鐐圭殑宸﹀瓙鏍戜腑锛屾壘宸﹀瓙鏍戠殑鏍圭粨鐐癸紙鍦ㄥ厛搴忎腑鎵撅級锛岃浆姝ラ1銆3銆佸湪鏍硅妭鐐圭殑鍙冲瓙鏍戜腑锛屾壘鍙冲瓙鏍戠殑鏍圭粨鐐癸紙鍦ㄥ厛搴忎腑鎵撅級锛岃浆姝ラ1銆鏍规嵁涓婅堪绠楁硶锛屽彲浠ョ湅鍑哄垱寤哄嚭浜屽弶鏍戠殑鍏抽敭鍦ㄤ簬鍏...
绛旓細涓銆鍏堝簭閬嶅巻 锛1銆佽闂牴鑺傜偣 2銆佸墠搴忛亶鍘 宸 瀛愭爲 3銆佸墠搴忛亶鍘 鍙冲瓙 鏍 浜屻涓簭閬嶅巻 锛1銆佷腑搴忛亶鍘嗗乏瀛愭爲 2銆佽闂牴鑺傜偣 3銆佷腑搴忛亶鍘嗗彸瀛愭爲 涓夈佸悗搴 閬嶅巻锛1銆佸悗搴忛亶鍘 宸﹀瓙鏍 2銆佸悗搴忛亶鍘嗗彸瀛愭爲 3銆佽闂牴鑺傜偣 涓嬮潰浠嬬粛涓涓嬩緥瀛愪笌鏂规硶锛1銆佺敾鏍戞眰娉曪細绗竴姝锛屾牴鎹鍓嶅簭閬嶅巻鐨勭壒鐐...
绛旓細�浜屽弶鎺搴忔爲瀵逛簩鍙夋爲浣滀簡杩涗竴姝ョ殑闄愬畾锛氭牴缁撶偣鐨勬潈鍊煎ぇ浜庯紙鎴栧皬浜庯級宸﹀瓙鏍戜腑鎵鏈夌粨鐐圭殑鏉冨硷紱鏍圭粨鐐圭殑鏉冨煎皬浜庯紙鎴栧ぇ浜庯級鍏跺彸瀛愭爲涓墍鏈夌粨鐐圭殑鏉冨笺�閭d箞濡備綍鏍规嵁涓夌閬嶅巻搴忓垪涔嬮棿鐨勫叧绯诲強浜屽弶鎺掑簭鏍戞潵蹇熻繕鍘熶竴妫典簩鍙夋爲锛熶笅闈互浜屽弶鏍戠殑鍓嶅簭鍜涓簭閬嶅巻搴忓垪涓哄熀纭锛屽埄鐢ㄤ簩鍙夋帓搴忔爲鐨...
绛旓細鐭ラ亾涓簭 骞朵笖鐭ラ亾鍏堝簭鍜屽悗搴忓叾涓箣涓灏辫兘纭畾涓棰椾簩鍙夋爲銆備緥濡備腑搴忓拰鍏堝簭銆傚墠搴忎负 a b d e c 涓簭涓猴細 d b e a c 1.鏍规嵁鍏堝簭绗竴涓猘鐭ラ亾锛浜屽弶鏍戠殑鏍硅妭鐐逛负a 2.瀵瑰簲涓簭锛鐭ラ亾a宸﹁竟鐨勯兘鏄湪a鐨勫乏瀛愭爲,鍙宠竟鐨勫湪鍙冲瓙鏍戜笂銆3.dbe鍦╝鐨勫乏瀛愭爲涓婏紝鐒跺悗鏍规嵁鍓嶅簭涔嬪悗b鍦ㄨ繖涓夎呯殑鏈鍓嶉潰 ...
绛旓細棣栧厛锛岄鐩彲鑳芥湁闂锛屾濊矾锛屽湪鍏堝簭搴鍒椾腑鎵炬牴锛屼腑搴忓簭鍒椾腑鍖哄垎宸﹀彸瀛愭爲锛岄掑綊灏卞彲浠ヤ簡銆傜敱鍏堝簭搴忓垪ABCDEFG,鍙煡锛岃鏍戠殑鏍逛负A锛岀敱涓簭DBCAFEG鍙煡锛孉鍓嶉潰鐨凞BC涓鸿鏍戠殑宸﹀瓙鏍戯紝A鍚庨潰鐨凢EG鐨勫叾鍙冲瓙鏍戙傜户缁垎鏋愶紝鍘熷簭鍒楀厛搴忚鍒嗕负涓ょ粍锛孊CD鍜孍FG锛屼腑搴忓垎鍒负DBC鍜孎EG锛屽厛搴BCD锛屼腑搴廌BC杩欐5浠...