一颗二叉树前序遍历和中序遍历分别是ABDEGCFH、DBGEACHF,则此后序遍历是？请高手解释怎么得的，说明原理！ 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DB...
\u4e00\u9897\u4e8c\u53c9\u6811\u524d\u5e8f\u904d\u5386\u548c\u4e2d\u5e8f\u904d\u5386\u5206\u522b\u662fABDEGCFH\u3001DBGEACHF,\u5219\u6b64\u540e\u5e8f\u904d\u5386\u662f\uff1f\u8bf7\u9ad8\u624b\u89e3\u91ca\u600e\u4e48\u5f97\u7684\uff0c\u8bf4\u660e\u539f\u7406\uff01\u524d\u5e8f\u53ef\u77e5A\u662f\u6839\u7ed3\u70b9\uff0c\u7531A\u5728\u4e2d\u5e8f\u4e2d\u7684\u4f4d\u7f6e\u53ef\u4ee5\u770b\u51faA\u7684\u5de6\u5b50\u6811\u4e0a\u5305\u62ecDBGE\u56db\u4e2a\u7ed3\u70b9\uff0c\u53f3\u5b50\u6811\u4e0a\u5305\u62ecCHF\u4e09\u4e2a\u7ed3\u70b9\u3002\u7531\u524d\u5e8f\u5217\u53ef\u4ee5\u770b\u51faB\u7ed3\u70b9\u662f\u5de6\u5b50\u6811\u7684\u6839\u7ed3\u70b9\uff0c\u518d\u7ed3\u5408B\u5728\u4e0a\u8ff0\u56db\u4e2a\u7ed3\u70b9\u4e2d\u7684\u4f4d\u7f6e\u53ef\u4ee5\u5f97\u51faB\u7684\u5de6\u5b50\u6811\u4e3aD\u53f3\u5b50\u6811\u5305\u542bGE\u4e24\u4e2a\u7ed3\u70b9\u3002\u7531\u524d\u5e8f\u5217E\u5728G\u524d\u9762\uff0c\u8bf4\u660eE\u662fB\u7684\u53f3\u7ed3\u70b9\uff0c\u4e2d\u5e8f\u6392\u5217\u4e2dG\u5728E\u524d\u9762\u8bf4\u660eG\u662fE\u7684\u5de6\u7ed3\u70b9\uff0cA\u7684\u53f3\u5b50\u6811\u4e5f\u53ef\u4ee5\u8fd9\u6837\u63a8\u51fa\u6765\u3002
\u753b\u56fe\u6700\u7b80\u5355\u4e86\uff0c\u7531\u7b2c\u4e00\u5e8f\u5217\u5148\u753b\u4e0a\u6839\u7ed3\u70b9A\uff0c\u7b2c\u4e00\u6570\u5217\u4e2d\u7b2c\u4e8c\u4f4d\u662fB\uff0c\u5728\u7b2c\u4e8c\u4e2a\u6570\u5217\u4e2dB\u5728\u5df2\u786e\u5b9a\u7684A\u7684\u5de6\u4fa7\uff0c\u90a3\u4e48B\u5c31\u662fA\u7684\u5de6\u7ed3\u70b9\uff0cB\u4e5f\u786e\u5b9a\u4e86\u3002\u7b2c\u4e00\u6570\u5217\u4e2d\u7b2c\u4e09\u4f4d\u662fD\uff0cD\u5728\u7b2c\u4e8c\u6570\u5217\u4e2d\u4f4d\u4e8e\u5df2\u786e\u5b9a\u7684B\u7684\u5de6\u4fa7\uff0c\u90a3D\u5c31\u662fB\u7684\u5de6\u7ed3\u70b9\uff1b\u7b2c\u4e00\u6570\u5217\u4e2d\u7b2c\u56db\u4e2a\u662fE\uff0cE\u5728\u7b2c\u4e8c\u4e2a\u6570\u5217\u4e2d\u5df2\u786e\u5b9a\u7684B\u7684\u53f3\u4fa7\uff0c\u90a3\u4e48E\u5c31\u662fB\u7684\u53f3\u7ed3\u70b9\uff1b\u7b2c\u4e94\u4e2a\u662fG\uff0cG\u5728\u7b2c\u4e8c\u6570\u5217\u4e2d\u4f4d\u4e8e\u5df2\u786e\u5b9a\u7684E\u7684\u5de6\u4fa7\uff0c\u90a3\u4e48G\u5c31\u662fE\u7684\u5de6\u7ed3\u70b9\uff1b\u7b2c\u516d\u4e2a\u662fC\uff0cC\u5728\u7b2c\u4e8c\u4e2a\u6570\u5217\u4e2d\u4f4d\u4e8e\u5df2\u786e\u5b9a\u70b9A\u7684\u53f3\u4fa7\uff0cC\u662fA\u7684\u53f3\u7ed3\u70b9\uff1b\u4e0b\u4e00\u4e2a\u662fF\uff0cF\u5728\u5df2\u786e\u5b9a\u7ed3\u70b9C\u7684\u53f3\u4fa7\uff0cF\u662fC\u7684\u53f3\u7ed3\u70b9\uff1b\u6700\u540e\u4e00\u4e2aH\uff0cH\u5728C\u7684\u53f3\u4fa7F\u7684\u5de6\u4fa7\uff0c\u5219F\u662fC\u7684\u5de6\u7ed3\u70b9\u3002\u597d\u4e86\u6574\u4e2a\u4e8c\u53c9\u6811\u51fa\u6765\u4e86\uff0c\u540e\u5e8f\u904d\u5386\u81ea\u5df1\u770b\u5c31\u884c\u4e86\u3002
\u5df2\u77e5\u4e00\u68f5\u4e8c\u53c9\u6811\u524d\u5e8f\u904d\u5386\u548c\u4e2d\u5e8f\u904d\u5386\u5206\u522b\u4e3aABDEGCFH\u548cDBGEACHF\uff0c\u5219\u8be5\u4e8c\u53c9\u6811\u7684\u540e\u5e8f\u904d\u5386\u662fDGEBHFCA\u3002
\u524d\u5e8f\u904d\u5386\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u4e3a\u6839\u8282\u70b9\uff0c\u7531\u524d\u5e8f\u904d\u5386\u53ef\u77e5\uff0cA\u4e3a\u6839\u8282\u70b9\u3002\u4e2d\u5e8f\u904d\u5386\u7684\u6839\u8282\u70b9\u524d\u9762\u7684\u8282\u70b9\u5747\u4e3a\u5de6\u5b50\u6811\u7684\u8282\u70b9\uff0c\u6240\u4ee5\u5de6\u5b50\u6811\u4e0a\u7684\u8282\u70b9\u4e3aDBGE\u3002\u53bb\u6389\u6839\u8282\u70b9\u548c\u5de6\u5b50\u6811\u8282\u70b9\uff0c\u53f3\u5b50\u6570\u8282\u70b9\u4e3aCHF\u3002\u524d\u5e8f\u904d\u5386\u7684\u7b2c\u4e8c\u4e2a\u8282\u70b9\u4e3aB\uff0c\u75312\u77e5B\u4e3a\u5de6\u5b50\u6811\u8282\u70b9\uff0c\u6240\u4ee5B\u4e3a\u5de6\u5b50\u6811\u7684\u6839\u8282\u70b9\u3002
\u7531\u524d\u5e8f\u904d\u5386\uff0cDEG\u5728B\u8282\u70b9\u4e0b\u9762\uff0c\u7531\u4e2d\u5e8f\u904d\u5386\uff0cD\u662fB\u7684\u5de6\u8282\u70b9\uff0cGE\u662fB\u7684\u53f3\u8282\u70b9\u3002\u7531\u524d\u5e8f\u904d\u5386\uff0cE\u662fG\u7684\u6839\u8282\u70b9\uff0c\u7531\u4e2d\u5e8f\u904d\u5386\uff0cG\u662fE\u7684\u5de6\u5b50\u8282\u70b9\u3002\u7531\u524d\u5e8f\u904d\u5386\uff0cC\u662f\u4e8c\u53c9\u6811\u7684\u53f3\u6839\u8282\u70b9\uff0c\u7531\u4e2d\u5e8f\u904d\u5386\uff0cC\u4e0d\u542b\u5de6\u5b50\u8282\u70b9\uff0cHF\u4e3aC\u7684\u53f3\u5b50\u8282\u70b9\u3002\u7531\u524d\u5e8f\u904d\u5386\uff0cF\u4e3aH\u7684\u6839\u8282\u70b9\uff0c\u7531\u4e2d\u5e8f\u904d\u5386\uff0cH\u4e3aF\u7684\u5de6\u5b50\u8282\u70b9\u3002
\u5728\u4e8c\u53c9\u6811\u4e2d\uff0c\u6c42\u540e\u5e8f\u904d\u5386\uff0c\u5148\u5de6\u540e\u53f3\u518d\u6839\uff0c\u5373\u9996\u5148\u904d\u5386\u5de6\u5b50\u6811\uff0c\u7136\u540e\u904d\u5386\u53f3\u5b50\u6811\uff0c\u6700\u540e\u8bbf\u95ee\u6839\u7ed3\u70b9\u3002\u5219\u8be5\u4e8c\u53c9\u6811\u7684\u540e\u5e8f\u904d\u5386\u662fDGEBHFCA\u3002
\u6269\u5c55\u8d44\u6599\uff1a
\u540e\u5e8f\u904d\u5386\u7684\u975e\u9012\u5f52\u7b97\u6cd5\u662f\u4e09\u79cd\u987a\u5e8f\u4e2d\u6700\u590d\u6742\u7684\uff0c\u539f\u56e0\u5728\u4e8e\uff0c\u540e\u5e8f\u904d\u5386\u662f\u5148\u8bbf\u95ee\u5de6\u3001\u53f3\u5b50\u6811,\u518d\u8bbf\u95ee\u6839\u8282\u70b9\uff0c\u800c\u5728\u975e\u9012\u5f52\u7b97\u6cd5\u4e2d\uff0c\u5229\u7528\u6808\u56de\u9000\u5230\u65f6\uff0c\u5e76\u4e0d\u77e5\u9053\u662f\u4ece\u5de6\u5b50\u6811\u56de\u9000\u5230\u6839\u8282\u70b9\uff0c\u8fd8\u662f\u4ece\u53f3\u5b50\u6811\u56de\u9000\u5230\u6839\u8282\u70b9\uff0c\u5982\u679c\u4ece\u5de6\u5b50\u6811\u56de\u9000\u5230\u6839\u8282\u70b9\uff0c\u6b64\u65f6\u5c31\u5e94\u8be5\u53bb\u8bbf\u95ee\u53f3\u5b50\u6811\u3002
\u800c\u5982\u679c\u4ece\u53f3\u5b50\u6811\u56de\u9000\u5230\u6839\u8282\u70b9\uff0c\u6b64\u65f6\u5c31\u5e94\u8be5\u8bbf\u95ee\u6839\u8282\u70b9\u3002\u6240\u4ee5\u76f8\u6bd4\u524d\u5e8f\u548c\u540e\u5e8f\uff0c\u5fc5\u987b\u5f97\u5728\u538b\u6808\u65f6\u6dfb\u52a0\u4fe1\u606f\uff0c\u4ee5\u4fbf\u5728\u9000\u6808\u65f6\u53ef\u4ee5\u77e5\u9053\u662f\u4ece\u5de6\u5b50\u6811\u8fd4\u56de\uff0c\u8fd8\u662f\u4ece\u53f3\u5b50\u6811\u8fd4\u56de\u8fdb\u800c\u51b3\u5b9a\u4e0b\u4e00\u6b65\u7684\u64cd\u4f5c\u3002
后序遍历是DGEBHFCA。
前序遍历的第一个节点为根节点，由前序遍历可知，A为根节点。中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE。
去掉根节点和左子树节点，右子数节点为CHF。前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点。
在二叉树中，求后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。
扩展资料：
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发。
首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
前序可知A是根结点，由A在中序中的位置可以看出A的左子树上包括DBGE四个结点，右子树上包括CHF三个结点。由前序列可以看出B结点是左子树的根结点，再结合B在上述四个结点中的位置可以得出B的左子树为D右子树包含GE两个结点。由前序列E在G前面，说明E是B的右结点，中序排列中G在E前面说明G是E的左结点，A的右子树也可以这样推出来。
画图最简单了，由第一序列先画上根结点A，第一数列中第二位是B，在第二个数列中B在已确定的A的左侧，那么B就是A的左结点，B也确定了。第一数列中第三位是D，D在第二数列中位于已确定的B的左侧，那D就是B的左结点；第一数列中第四个是E，E在第二个数列中已确定的B的右侧，那么E就是B的右结点；第五个是G，G在第二数列中位于已确定的E的左侧，那么G就是E的左结点；第六个是C，C在第二个数列中位于已确定点A的右侧，C是A的右结点；下一个是F，F在已确定结点C的右侧，F是C的右结点；最后一个H，H在C的右侧F的左侧，则F是C的左结点。好了整个二叉树出来了，后序遍历自己看就行了。
前序先访问根节点，因此a是根节点，中序先访问左子树，再访问根，再访问右子树，因为已经确认a为根，所以，从中序可知，dbge为左子树，a为根，chf为右子树。然后对左、右子树分别处理。结果为dgebhfca
由前序遍历确定根的位置，中序遍历确定左右子树包括的结点，然后分成两棵子树的相同子问题来递归求解，如此即可确定树的结构，后序遍历就没问题了。
(DBGE)A(CHF)→((D)B(GE))A(C(HF)→((D)B((G)E))A(C((H)F)，
所以后序遍历为DGEBHFCA
前序就是先根，则A必定是根！！！
从中序就能从A一分为二，分别为左与右的子树；
中序：
左子中序
DBGE
右子中树
CHF
再从前序中分出左、右子树：
前序
左子前序：
BDEG
右子前序
CFH
这个问题递归成两个小问题。同样的方法再分析出两个子树
绛旓細銆愮瓟妗堛戯細B B銆傘愯В鏋愩浜屽弶鏍戠殑閬嶅巻鏈3绉嶏細鍓嶅簭銆佷腑搴鍜屽悗搴忋傚悗搴忛亶鍘嗛鍏堥亶鍘嗗乏瀛愭爲鎴栧乏瀛愮粨鐐癸紝鐒跺悗閬嶅巻鍙冲瓙鏍戞垨鍙冲瓙缁撶偣锛屾渶鍚庤闂牴缁撶偣锛涙湰棰樻牴鎹墠搴忛亶鍘嗗拰涓簭閬嶅巻鐨勭粨鏋滃彲浠ュ緱鍑轰簩鍙夋爲鐨勭粨鏋勶紝鐒跺悗鍐嶅鍏惰繘琛屽悗搴忛亶鍘嗭紝鍥犳绛旀涓洪夐」B銆
绛旓細宸茬煡涓妫典簩鍙夋爲鍓嶅簭閬嶅巻鍜屼腑搴忛亶鍘鍒嗗埆涓篈BDEGCFH鍜孌BGEACHF锛屽垯璇ヤ簩鍙夋爲鐨勫悗搴忛亶鍘嗘槸DGEBHFCA銆傚墠搴忛亶鍘嗙殑绗竴涓妭鐐逛负鏍硅妭鐐癸紝鐢卞墠搴忛亶鍘嗗彲鐭ワ紝A涓烘牴鑺傜偣銆備腑搴忛亶鍘嗙殑鏍硅妭鐐瑰墠闈㈢殑鑺傜偣鍧囦负宸﹀瓙鏍戠殑鑺傜偣锛屾墍浠ュ乏瀛愭爲涓婄殑鑺傜偣涓篋BGE銆傚幓鎺夋牴鑺傜偣鍜屽乏瀛愭爲鑺傜偣锛屽彸瀛愭暟鑺傜偣涓篊HF銆傚墠搴忛亶鍘嗙殑绗簩涓妭...
绛旓細銆愮瓟妗堛戯細A 浜屽弶鏍戠殑鍏堝簭閬嶅巻搴忓垪鍜屼腑搴忛亶鍘搴忓垪涓璧峰彲浠ョ‘瀹氳繖妫典簩鍙夋爲鐨勫舰鎬併傛湰棰樼殑瑙ｉ鎬濊矾鏄厛鏍规嵁棰樿纭畾杩欐５浜屽弶鏍戠殑褰㈡侊紝鐒跺悗鍐嶇敤鍚庡簭閬嶅巻姝や簩鍙夋爲锛屽緱鍒板悗搴忛亶鍘嗗簭鍒椼傛牴鎹厛搴忛亶鍘嗗簭鍒楋紝A鏄簩鍙夋爲鐨勬牴缁撶偣銆傛牴鎹腑搴忛亶鍘嗗簭鍒楋紝鍒欎簩鍙夋爲鐨勫舰鎬佷竴瀹氬鍥4鈥9鎵绀恒9鑰冭檻A鐨勫乏瀛愭爲銆傛牴鎹簩...
绛旓細鍓嶅簭閬嶅巻棣栧厛璁块棶鏍圭粨鐐圭劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆傚湪閬嶅巻宸︺佸彸瀛愭爲鏃讹紝浠嶇劧鍏堣闂牴缁撶偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆涓簭閬嶅巻棣栧厛閬嶅巻宸﹀瓙鏍戯紝鐒跺悗璁块棶鏍圭粨鐐癸紝鏈鍚庨亶鍘嗗彸瀛愭爲銆傝嫢浜屽弶鏍涓虹┖鍒欑粨鏉熻繑鍥炪傚洜姝わ紝A鏄牴缁撶偣锛孊鏄疉鐨勫乏瀛愭爲锛孎鏄疉鐨勫彸瀛愭爲銆侲鏄疊鐨勫乏瀛愭爲锛孋鏄疊鐨勫彸瀛愭爲锛...
绛旓細鍒欒浜屽弶鏍戠殑鍓嶅簭閬嶅巻搴忓垪涓篈BDECF锛屼腑搴忛亶鍘嗗簭鍒椾负DBEAFC锛屽悗搴忛亶鍘嗗簭鍒椾负DEBFCA銆鍏堝簭閬嶅巻浜屽弶鏍瑙勫垯锛氭牴-宸-鍙 1銆佽闂牴缁撶偣锛2銆佸厛搴忛亶鍘嗗乏瀛愭爲锛3銆佸厛搴忛亶鍘嗗彸瀛愭爲銆涓簭閬嶅巻浜屽弶鏍瑙勫垯锛氬乏-鏍-鍙 1銆佸厛涓簭閬嶅巻宸﹀瓙鏍戯紱2銆佸啀璁块棶鏍硅妭鐐癸紱3銆佹渶鍚庤闂腑搴忛亶鍘嗗彸瀛愭爲銆傚悗搴忛亶鍘嗕簩鍙夋爲瑙勫垯...
绛旓細閬嶅巻灏辨槸鎸夌収鏌愭潯璺緞璁块棶鏍涓瘡涓粨鐐癸紝浣挎瘡涓粨鐐硅璁块棶浠呬笖涓娆°傦紙1锛鍏堝簭閬嶅巻锛圖 L R锛夛細璁块棶鏍圭粨鐐癸紱鍏堝簭閬嶅巻宸﹀瓙鏍戯紱鍏堝簭閬嶅巻鍙冲瓙鏍戙傦紙2锛涓簭閬嶅巻锛圠 D R锛夛細涓簭閬嶅巻宸﹀瓙鏍戯紱璁块棶鏍圭粨鐐癸紱涓簭閬嶅巻鍙冲瓙鏍戙傦紙3锛夊悗搴忛亶鍘嗭紙L R D锛夛細鍚庡簭閬嶅巻宸﹀瓙鏍戯紱鍚庡簭閬嶅巻鍙冲瓙鏍戯紱璁块棶鏍圭粨鐐广...
绛旓細鍚搴忛亶鍘涓猴細DGEBHFCA銆傛爲缁撴瀯涓猴細
绛旓細鍏堝簭閬嶅巻涓殑绗竴涓瓧姣岮灏辨槸浜屽弶鏍鐨勬牴缁撶偣锛孉锛屽湪涓簭閬嶅巻涓壘鍒癆锛屼粬鐨勫乏渚ф湁涓変釜瀛楁瘝DBE灏辨槸瀹冪殑宸﹀瓙鏍戠殑涓簭閬嶅巻锛岀劧鍚庡啀鍏堝簭渚垮埄涓悓鏍锋壘鍒癆鍚庨潰鐨勪笁涓瓧姣岯DE锛屽氨鏄牴缁撶偣鐨勫乏瀛愭爲鐨勫厛搴忛亶鍘嗐傜敤鍚屾牱鐨勬柟娉曟壘鍑烘牴缁撶偣鐨勫彸瀛愭爲鐨鍓嶅簭閬嶅巻鍜屼腑搴忛亶鍘锛岀劧鍚庨掑綊浣跨敤鍓嶉潰鐨勬柟娉曞氨鍙互鐢诲嚭鏁翠釜...
绛旓細DGEBHFCA 杩欎釜鏄2鍙夋爲婊村浘褰 妤间富鐪嬬湅鍝垀A / \ B C / \ . \ D E F . / . / G. H 鍚庡簭璁块棶鐨勯『搴忎负 (1)閬嶅巻宸﹀瓙鏍戯紱(2)閬嶅巻鍙冲瓙鏍戯紱(3)璁块棶鏍圭粨鐐广傛墍浠ョ粨鏋滀负DGEBHFCA
绛旓細銆愮瓟妗堛戯細B B銆傘愯В鏋愩戞牴鎹滄牴涓宸︿竴鍙斥濓紝鈥滃乏涓鏍逛竴鍙斥濓紝鈥滃乏涓鍙充竴鏍光鐨勫厛搴銆涓簭銆佸悗搴忛亶鍘鍘熷垯锛屽彲浠ョ煡閬擄紝鍦3绉嶉亶鍘嗘墍浜х敓鐨勫簭鍒椾腑锛屾墍鏈夊彾瀛愮粨鐐圭殑鍏堝悗椤哄簭鏄畬鍏ㄧ浉鍚岀殑銆
