一只一棵二叉树的先序遍历结果为abcdefghi,中序遍历结果为cbafegdhi,请写出后序遍历结果并画出这棵二叉树 已知一棵二叉树的先序遍历序列为ABCDEFGHIJ,中序遍历...
\u5df2\u77e5\u4e8c\u53c9\u6811\u5982\u4e0b\u56fe\u6240\u793a,\u8bf7\u5199\u51fa\u5148\u5e8f\u904d\u5386,\u4e2d\u5e8f\u904d\u5386\u548c\u540e\u5e8f\u904d\u5386\u5e8f\u5217\u524d\u5e8f\u904d\u5386BEFCGDH
\u4e2d\u5e8f\u904d\u5386FEBGCHD
\u540e\u5e8f\u904d\u5386FEGHDCB
\u5148\u770b\u5148\u5e8f\uff0c\u5176\u7b2c\u4e00\u4e2a\u4e3a\u6811\u7684\u6839\uff0c\u5148\u5e8f\u904d\u5386\u662f\u5148\u6839\u518d\u5de6\u5b50\u6811\u6700\u540e\u53f3\u5b50\u6811\uff0c\u7b2c\u4e00\u4e2a\u80af\u5b9a\u662f\u6811\u7684\u6839\uff0c\u5148\u753bA\uff0cA\u518d\u4e2d\u5e8f\u904d\u5386\u4e2d\u5de6\u53f3\u90fd\u6709\uff0c\u8bf4\u660eA\u6709\u5de6\u5b50\u6811\u4e5f\u6709\u53f3\u5b50\u6811\u3002
A
/ \
\u7136\u540e\u770b\u5148\u5e8f\u7b2c\u4e00\u4e2a\u503c\u662fB\uff0c\u5728\u4e2d\u5e8f\u4e2d\u4e3aA\u7684\u524d\u9762\uff0c\u6240\u4ee5B\u662fA\u7684\u5de6\u5b50\u6811
A
/ \
B
\u7ee7\u7eed\u770b\u5148\u5e8f\uff0c\u63a5\u4e0b\u6765\u662fC\u3001D\uff0cC\u518d\u4e2d\u5e8f\u4e2d\u518dB\u7684\u524d\u9762\uff0c\u6240\u4ee5C\u662fB\u7684\u5de6\u5b50\u6811\uff0cD\u5728B\u540e\u9762\uff0cD\u662fB\u7684\u53f3\u5b50\u6811\u3002
A
/ \
B
/ \
C D
\u63a5\u4e0b\u6765\u662fE\uff0cE\u5728\u4e2d\u5e8f\u662f\u5728D\u540e\u9762A\u524d\u9762\uff0c\u6240\u4ee5E\u662fD\u7684\u53f3\u5b50\u6811
A
/ \
B
/ \
C D
\
E
\u63a5\u7740\u5148\u5e8f\u4e2d\u662fF\uff0cF\u5728\u4e2d\u5e8f\u4e3aA\u540e\u9762\uff0c\u662fA\u7684\u53f3\u5b50\u6811
A
/ \
B F
/ \
C D
\
E
\u4e2d\u5e8f\u4e2d A \u4e0eF\u4e4b\u95f4\u6ca1\u6709\uff0c\u8bf4\u660eF\u6ca1\u6709\u5de6\u5b50\u6811\uff0c\u53ea\u6709\u53f3\u5b50\u6811.\u5982\u4e0a\u9762\u65b9\u6cd5\u7ee7\u7eed\u5206\u6790GHIJ\uff0c\u6700\u7ec8\u4e8c\u53c9\u6811\u5982\u4e0b\uff1a
A
/ \
B F
/ \ \
C D G
\ / \
E H J
\
I
左一定优先于右 ,所以根的位置有三种。
根 左 右、左 根 右、左 右 根。
分别称为先序遍历、中序遍历、后续遍历,子树也一样,到一个子树就遍历一次,按照遍历顺序写下去就好,尤其注意根特殊对待(只有一个所以只写一个)。
后续遍历是:CBEFDA
依据前序遍历序列可确定根结点为A;再依据中序遍历序列可知其左子树由DBE构成,右子树为FC;又由左子树的前序遍历序列可知其根结点为B,由中序遍历序列可知其左子树为D,同理推算FC的排列顺序。
扩展资料:
除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
有且仅有一个开始结点和一个终端结点,其余结点都有且仅有一个前驱结点和一个后继结点。为了区别于树形结构中前驱(即双亲)结点和后继(即孩子)结点的概念,对上述三种线性序列,要在某结点的前驱和后继之前冠以其遍历次序名称。
参考资料来源:百度百科-二叉树遍历
这类题的推导方法见:http://zhidao.baidu.com/question/199520462615190205.html?oldq=1
绛旓細鍚搴忛亶鍘锛氬厛璁块棶宸﹀瓙鏍戯紝鐒跺悗璁块棶鍙冲瓙鏍戯紝鏈鍚庤闂牴鑺傜偣銆備緥濡傦紝瀵逛簬浜屽弶鏍1涓2涓3涓4涓5锛屽悗搴忛亶鍘嗙殑缁撴灉涓4涓5涓2涓3涓1銆傚悗搴忛亶鍘嗗氨鍍忔槸鍓憽钀勶紝鎴戜滑瑕佹妸姣忎竴鏍规灊鏉¢兘澶勭悊濂戒簡锛屽啀澶勭悊钁¤悇涓茬殑椤堕儴銆浜屽弶鏍戠殑鐭ヨ瘑鐐癸細1銆佷簩鍙夋爲鐨勫畾涔夊拰鎬ц川锛氫簩鍙夋爲鏄竴绉嶆爲褰㈢粨鏋勶紝鍏朵腑姣忎釜鑺傜偣鏈澶氭湁涓涓...
绛旓細鍏堝簭鍒楀彿涓鸿繖涓紝閭d箞鍦ㄧ紪杈戠殑鏃跺欙紝鍙互鍏堣繘琛岀敤椤哄簭鐨勬柟寮忥紝鐒跺悗鍐嶈繘琛屻傚悗搴忓簭鍒楁槸CBA銆傛牴鎹鍓嶅簭锛屽彲浠ョ‘瀹欰涓烘牴锛孉鍦涓簭涓鐨勪綅缃紝鍙互纭畾CB涓篈鐨勫乏瀛愭爲涓婄殑缁撶偣锛屾病鏈夊彸瀛愭爲銆傜‘瀹欰涔嬪悗锛屽啀鐪嬩腑搴忕浜屽间负B锛屾煡鐪婤鍦ㄤ腑搴忎腑鐨勪綅缃紝C鍦˙宸﹁竟锛岀‘瀹欳涓築鐨勫乏瀛愭爲銆
绛旓細E D F C B I G H A
绛旓細A / \ B D / / \ C E F 鍚庡簭閬嶅巻搴旇涓猴細CBEFDA 鍏堝簭閬嶅巻鍙‘瀹氭牴缁撶偣涓篈锛屼腑搴忎负CBAEDF锛屼腑搴忎腑A宸﹁竟涓哄乏瀛愭爲鍙宠竟涓哄彸瀛愭爲锛屼緷娆$被鎺紝鍙緱鍑鏍戠殑缁撴瀯`鐒跺悗鍙互寰楀嚭鍚庡簭銆傛垜鏅 涓撻棬涓鸿繖鍘绘敞鍐涓璐﹀彿鍥炴潵灏辫繖涔堝浜轰簡 鍝堝搱鍝堝搱 鐗涗汉鐪熷锛侊紒
绛旓細鏁版嵁缁撴瀯璁$畻鏈轰笓涓氬繀瀛︾煡璇浜屽弶鏍戠殑閬嶅巻 鍏堝簭閬嶅巻 鍏堝簭閬嶅巻鍙互鎯宠薄涓猴紝涓涓皬浜轰粠涓妫典簩鍙夋爲鏍硅妭鐐逛负璧风偣锛屾部鐫浜屽弶鏍戝娌匡紝閫嗘椂閽堣蛋涓鍦堝洖鍒版牴鑺傜偣锛岃矾涓婇亣鍒扮殑鍏冪礌椤哄簭锛屽氨鏄厛搴忛亶鍘嗙殑缁撴灉銆傚阀璁帮細鏍瑰乏鍙 鍏堝簭閬嶅巻缁撴灉涓锛欰BD HI EJCFKG 涓簭閬嶅巻 涓簭閬嶅巻鍙互鐪嬫垚锛屼簩鍙夋爲姣忎釜鑺傜偣锛屽瀭鐩存柟鍚...
绛旓細鏍规嵁鍏堝簭閬嶅巻鍜屼腑搴忛亶鍘嗭紝鎴戜滑鍙互灏嗚繖棰浜屽弶鏍鐢诲嚭鏉ワ紝濡備笅鍥俱傛墍浠ワ紝鏍规嵁鍥剧墖锛屽緱鍑哄眰娆閬嶅巻搴鍒椾负锛欰BCDEFGHI銆
绛旓細浜屽弶鏍鏍硅妭鐐逛负A锛孉鐨勫乏鑺傜偣涓築锛孊鐨勫彸鑺傜偣涓篋锛孉鐨勫彸鑺傜偣涓篊锛孋鐨勫乏鑺傜偣涓篍锛屽悗搴忛亶鍘嗗簭鍒椾负DBECA銆傜敾娉曪細鏍笶锛孍宸鍙矲锛孉鍙矪锛孊鍙矰锛孌宸锛孎鍙矵锛孒宸鍙矷锛孖鍙矺锛孠宸 鍏堢湅鍏堝簭锛屽叾绗涓涓负鏍戠殑鏍癸紝鍏堝簭閬嶅巻鏄鍏堟牴鍐嶅乏瀛愭爲鏈鍚庡彸瀛愭爲锛岀涓涓偗瀹鏄爲鐨鏍癸紝鍏堢敾A锛孉鍐嶄腑...
绛旓細鏁版嵁缁撴瀯棰樼洰,涓妫典簩鍙夋爲鐨勫厛搴忛亶鍘嗕负ABCEIJFGKHD,涓簭閬嶅巻涓築IJEFKGHCDA,鐢诲嚭杩欐5浜屽弶鏍,楹荤儲浼氱殑浜插啓涓涓嬭繃绋,璋㈣阿... 鏁版嵁缁撴瀯棰樼洰,涓妫典簩鍙夋爲鐨勫厛搴忛亶鍘嗕负ABCEIJFGKHD,涓簭閬嶅巻涓築IJEFKGHCDA,鐢诲嚭杩欐5浜屽弶鏍,楹荤儲浼氱殑浜插啓涓涓嬭繃绋,璋㈣阿 灞曞紑 ...
绛旓細鍏堢湅鍏堝簭锛屽叾绗涓涓负鏍戠殑鏍癸紝鍏堝簭閬嶅巻鏄鍏堟牴鍐嶅乏瀛愭爲鏈鍚庡彸瀛愭爲锛岀涓涓偗瀹鏄爲鐨鏍癸紝鍏堢敾A锛孉鍐嶄腑搴忛亶鍘嗕腑宸﹀彸閮芥湁锛岃鏄嶢鏈夊乏瀛愭爲涔熸湁鍙冲瓙鏍戙侫 / \ 鐒跺悗鐪嬪厛搴忕涓涓兼槸B锛屽湪涓搴忎腑涓A鐨勫墠闈紝鎵浠鏄疉鐨勫乏瀛愭爲 A / \ B 缁х画鐪嬪厛搴忥紝鎺ヤ笅鏉ユ槸C銆丏锛孋鍐嶄腑搴忎腑鍐岯鐨...
绛旓細銆愮瓟妗堛戯細B鍏堝簭閬嶅巻鍗冲厛鏍瑰悗宸﹀瓙鏍戝啀鍙冲瓙鏍戯紝涓簭閬嶅巻涓哄厛宸﹀瓙鏍戝悗璺熷啀鍙冲瓙鏍戙傚厛搴忛亶鍘嗙殑鏈寮濮嬬粨鐐笰鍗充负鏁妫垫爲鐨鏍癸紝缁撳悎涓簭閬嶅巻锛孉缁撶偣宸︿晶B鍗充负鏍硅妭鐐笰鐨勫乏瀛愭爲锛屽彸渚CFE鍒欎负A鐨勫彸瀛愭爲锛屽悓鐞嗗彲浠ュ緱鍑篊涓篈鐨勫彸瀛愭爲鐨勬牴鑺傜偣锛孌涓篊鐨勫乏瀛愭爲锛孍F涓篊鐨勫彸瀛愭爲锛孎涓篍鐨勫乏瀛愭爲銆傚彲浠ュ緱鍒板...