二叉树前序中序后序
二叉树前序中序后序如下：
①前序遍历的方式是：首先访问根节点，然后访问左子树，最后访问右子树。
前序遍历序列：F C A D B E H G M。
②中序遍历的方式是：首先访问左子树，接着访问根结点，最后访问右子树。
中序遍历序列：A C B D F H E M G。
③后序遍历的方式是：首先访问左子树，接着访问右子树，最后访问根结点。
后序遍历序列：A B D C H M G E F。
④相同的特点：
左子树总是在右子树的之前遍历。
遍历都可以用递归的方式来描述。
中序遍历的序列中任取一个结点，该结点的左子树右子树一定分别在该结点左右，其他遍历序列也是如此。
遍历实质就是看每个结点及其子结点，谁先满足访问的要求，比如上图A结点，在后续遍历整个二叉树中A及其子结点先满足-访问完左右结点-，所以先访问A结点。
⑤由序列逆推二叉树
给定一个序列无法确定二叉树结构。
给定中序+前/后序则可以确定二叉树结构。
绛旓細瑙ｏ細绗竴姝ワ細鏍规嵁鍓嶅簭閬嶅巻绗竴涓妭鐐逛负鏍硅妭鐐瑰緱鐭ワ紝A涓烘牴 绗簩姝ワ細鏍规嵁涓簭DBEAC寰楃煡锛孉鍓嶉潰鐨勬槸宸﹀瓙鏍戯紝璇存槑 DBE鍦 A宸︿晶锛孋鍦ㄥ彸渚э紝鐩墠鍙互寰楀嚭AC鐨勪綅缃 绗笁姝ワ細鏍规嵁鍓╀笅鐨勫墠搴 BDEC 寰楃煡锛孊涓烘牴 绗洓姝ワ細鏍规嵁鍓╀笅鐨勪腑搴 DBE 寰楃煡锛孌鍦˙宸︿晶锛孍鍦˙鍙充晶锛屾墍浠ュ彲浠ョ敾鍑烘暣涓浜屽弶鏍鍥 鏈枃...
绛旓細鍏跺疄杩欎釜椤哄簭灏辨槸琛ㄧず鏍硅妭鐐规墍鍦ㄧ殑浣嶇疆锛屽乏瀛愭爲鍜屽彸瀛愭爲鐨勯『搴忔槸鍥哄畾鐨勶紝閮芥槸鍏堝乏鍚庡彸銆傛墍浠ユ牴缁撶偣涓庡乏鍙冲瓙鏍戠殑鍏崇郴灏辨瀯鎴愪簡涓夌椤哄簭锛1. 鑻ュ湪宸﹀彸瀛愭爲鐨勫墠闈㈣璁块棶鍙仛鍓嶅簭锛屽叾椤哄簭涓烘牴宸﹀彸 2. 鑻ュ湪宸﹀彸瀛愭爲鐨勪腑闂磋璁块棶鍙仛涓簭锛屽叾椤哄簭涓哄乏鏍瑰彸 3. 鑻ュ湪宸﹀彸瀛愭爲鐨勫悗闈㈣璁块棶鍙仛鍚庡簭锛屽叾椤哄簭涓...
绛旓細鍐嶆牴鎹涓簭閬嶅巻搴忓垪锛屽彲鐭鏄疍鐨勫乏瀛╁瓙锛屽洜涓篋鏄敱E銆丏鍜孎鏋勬垚鐨浜屽弶鏍鐨勬牴缁撶偣锛孍鍦―鍓嶈璁块棶锛屾牴鎹腑搴忛亶鍘嗙殑椤哄簭锛屽彲鐭鏄疍鐨勫乏瀛╁瓙銆傝孎鏄疍鐨勫彸瀛╁瓙锛孎鍦―鍚庤璁块棶锛屾牴鎹腑搴忛亶鍘嗙殑椤哄簭锛屽彲鐭鏄疍鐨勫彸瀛╁瓙銆傚鍥4鈥11鎵绀恒傝嚦姝わ紝浜屽弶鏍戣纭畾涓嬫潵浜嗐傛垜浠啀瀵瑰畠杩涜鍚庡簭閬嶅巻锛屽緱鍒板悗搴...
绛旓細銆愮瓟妗堛戯細B 鏈鑰冩煡鐨勬槸浜屽弶鏍鐨勯亶鍘嗚繃绋嬨傚湪鏈涓紝鐢变簬鍓嶅簭閬嶅巻棣栧厛璁块棶鐨勬槸鏍圭粨鐐癸紝鎵浠ユ牴缁撶偣鏄疉锛屽張鐢变簬鍚庡簭閬嶅巻鏈鍚庤闂殑鏄牴缁撶偣锛屾墍浠ユ帓闄ら夐」A锛涙牴鎹涓簭搴鍒楃煡閬擄紝DBC鏄乏瀛愭爲鐨勭粨鐐癸紝FEG鏄彸瀛愭爲鐨勭粨鐐广
绛旓細浜屽弶鏍鐨勫厛搴忥紝涓簭锛鍚庡簭纭畾鐨勬柟娉曞涓嬶細1銆佹牴鎹悗搴忛亶鍘嗙殑鐗圭偣锛屾垜浠煡閬撳悗搴忛亶鍘嗘渶鍚庝竴涓粨鐐瑰嵆涓烘牴缁撶偣锛屽嵆鏍圭粨鐐逛负G銆2銆佽瀵熶腑搴忛亶鍘咥DEFGHMZ銆傚叾涓璻oot鑺傜偣G宸︿晶鐨凙DEF蹇呯劧鏄痳0ot鐨勫乏瀛愭爲锛孏鍙充晶鐨凥MZ蹇呯劧鏄痳oot鐨勫彸瀛愭爲銆3銆佽瀵熷乏瀛愭爲ADEF锛屽乏瀛愭爲鐨勪腑鐨勬牴鑺傜偣蹇呯劧鏄ぇ鏍戠殑root鐨刲eft...
绛旓細娆㈣繋鏉ュ埌鐨摜鐨勭畻娉曠郴鍒楋紝鎴戜滑灏嗕竴璧锋帰绱浜屽弶鏍鐨勪笘鐣屻備簩鍙夋爲鏄竴绉嶇嫭鐗圭殑鏍戝舰缁撴瀯锛屾瘡涓妭鐐规渶澶氭湁涓や釜瀛愯妭鐐癸紝鍒嗗埆绉颁负宸﹀瓙鏍戝拰鍙冲瓙鏍戯紝灏卞儚瀹冪殑鍚嶅瓧鎵鎻忚堪鐨勯偅鏍枫傞亶鍘嗕簩鍙夋爲鏄悊瑙ｅ叾缁撴瀯鐨勫叧閿紝鍥涚鍩烘湰閬嶅巻鏂瑰紡鍖呮嫭鍓嶅簭銆涓簭銆鍚庡簭鍜屽眰搴忋傚墠搴忛亶鍘嗛伒寰牴鑺傜偣 -> 宸﹀瀛 -> 鍙冲瀛愮殑椤哄簭锛...
绛旓細鍐嶄粠涓簭搴鍒桟DBEAGHFK鍙互鐭ラ亾锛孋DBE鏄牴A鐨勫乏瀛愭爲涓殑缁撶偣锛岃孏HFK鏄牴A鐨勫彸瀛愭爲涓殑缁撶偣銆傜幇鍦ㄦ垜浠潵鍒嗘瀽宸﹀瓙鏍戜腑鐨勬儏鍐碉紝鍚屾牱鐢鍚庡簭搴鍒椾腑DCEB鍙互鐪嬪嚭B鏄乏瀛愭爲鐨勬牴缁撶偣锛岀敱涓簭搴忓垪CDBE鍙互鐪嬪嚭E鏄疊鐨勫彸瀛愭爲鐨勭粨鐐广傚悓鐞嗭紝鎴戜滑鍙互鍒嗘瀽鍑烘暣涓簩鍙夋爲鐨勭粨鐐瑰垎甯冦傛浜屽弶鏍戝墠搴閬嶅巻鐨勭粨鏋滀负...
绛旓細浜屽弶鏍鐨鍚庡簭涓篏銆丏銆丅銆両銆丠銆丒銆丗銆丆銆丄銆傜敱鍓鍓嶅簭绗竴涓负A锛屾墍浠ユ牴鑺傜偣锛屾墍浠鐨勫乏瀛愭爲涓篋銆丟銆丅锛屽彸瀛愭爲涓篍銆両銆丠銆丆銆丗銆傜浜屼釜鏍硅妭鐐逛负B锛屽張鐢涓簭鐨勫嚭B鐨勫乏瀛愭爲涓篋銆丟锛岀劧鍚庡緱鍑篋鐨勫彸瀛愭爲涓篏锛孋涓篈鐨勫彸瀛愭爲锛屼緷娆¤繘琛屽垽鏂紝鏈鍚庣殑鍑轰簩鍙夋爲鐨勫簭鍒椼備簩鍙夋爲鍥撅紝濡備笅鍥撅細...
绛旓細鑻ヤ簩鍙夋爲涓虹┖鍒欑粨鏉熻繑鍥烇紝鍚﹀垯锛氾紙1锛鍚庡簭閬嶅巻宸﹀瓙鏍戙傦紙2锛夊悗搴忛亶鍘嗗彸瀛愭爲銆傦紙3锛夎闂牴缁撶偣銆傛敞鎰忕殑鏄細閬嶅巻宸﹀彸瀛愭爲鏃朵粛鐒堕噰鐢ㄥ悗搴忛亶鍘嗘柟娉曘傚涓婂浘鎵绀浜屽弶鏍 鍓嶅簭閬嶅巻锛屼篃鍙厛鏍归亶鍘嗭紝閬嶅巻鐨勯『搴忔槸锛屾牴锛屽乏瀛愭爲锛屽彸瀛愭爲 閬嶅巻缁撴灉锛歛,b,e,f,c,g 涓簭閬嶅巻锛屼篃鍙腑鏍归亶鍘嗭紝椤哄簭鏄 宸﹀瓙鏍...
绛旓細涓銆佸厛搴忛亶鍘嗭細1銆佽闂牴鑺傜偣 2銆鍓嶅簭閬嶅巻宸﹀瓙鏍 3銆佸墠搴忛亶鍘嗗彸瀛愭爲 浜屻涓簭閬嶅巻锛1銆佷腑搴忛亶鍘嗗乏瀛愭爲 2銆佽闂牴鑺傜偣 3銆佷腑搴忛亶鍘嗗彸瀛愭爲 涓夈鍚庡簭閬嶅巻锛1銆佸悗搴忛亶鍘嗗乏瀛愭爲 2銆佸悗搴忛亶鍘嗗彸瀛愭爲 3銆佽闂牴鑺傜偣 涓嬮潰浠嬬粛涓涓嬩緥瀛愪笌鏂规硶锛1銆佺敾鏍戞眰娉曪細绗竴姝ワ紝鏍规嵁鍓嶅簭閬嶅巻鐨勭壒鐐癸紝鎴戜滑鐭ラ亾鏍...
