数据结构中序和后序怎么画二叉树 知道二叉树先序,中序,后序其中的两个顺序列,如何画出二叉树
\u6570\u636e\u7ed3\u6784\u4e2d\u600e\u6837\u6839\u636e\u4e2d\u5e8f\u5148\u5e8f\u540e\u5e8f\u753b\u51fa\u6811\u5148\u5e8f\u904d\u5386\u4e2d\u7b2c\u4e00\u4e2a\u5143\u7d20\u4e3a\u6839\uff0c\u6839\u636e\u6b64\u6839\u628a\u4e2d\u5e8f\u5e8f\u5217\u5206\u4e3a\u5de6\u53f3\u5b50\u6811\uff0c\u786e\u5b9a\u5de6\u53f3\u5b50\u6811\u4e2d\u5305\u542b\u7684\u5143\u7d20\u540e\u518d\u5206\u522b\u5728\u5148\u5e8f\u5e8f\u5217\u4e2d\u786e\u5b9a\u5de6\u53f3\u5b50\u6811\u7684\u6811\u6839\uff0c\u4f9d\u6b21\u627e\u51fa\u5de6\u53f3\u5b50\u6811\u7684\u6811\u6839\u3002\u3002\u3002
\uff08\u5148\u5e8f\u4e2d\u5e8f\u53ef\u4ee5\uff0c\u540e\u5e8f\u4e2d\u5e8f\u4e5f\u53ef\u4ee5\uff0c\u5fc5\u987b\u8981\u6709\u4e2d\u5e8f\u54df~\uff09
\u4e0d\u77e5\u9053\u8bf4\u7684\u591f\u6e05\u695a\u5417
\uff081\uff09\u7531\u5148\u5e8f\u904d\u5386\u5e8f\u5217\u548c\u540e\u5e8f\u904d\u5386\u5e8f\u5217\u4e0d\u80fd\u552f\u4e00\u786e\u5b9a\u4e00\u68f5\u4e8c\u53c9\u6811\u3002
\uff082\uff09\u7531\u5148\u5e8f\u904d\u5386\u5e8f\u5217\u548c\u4e2d\u5e8f\u904d\u5386\u5e8f\u5217\u80fd\u591f\u552f\u4e00\u786e\u5b9a\u4e00\u68f5\u4e8c\u53c9\u6811\u3002
\u8bbe\u5148\u5e8f\u5e8f\u5217\u4e3a\uff1aa1\uff0ca2\uff0c\u2026\u2026\uff0can \uff0c \u4e2d\u5e8f\u5e8f\u5217\u4e3a\uff1aap1\uff0c\u2026\uff0capi\uff0c a1\uff0c \u2026\uff0capn \u3002\u5219a1\u4e3a\u6839\u7ed3\u70b9\uff1bap1\uff0c\u2026\uff0capi\u4e3a\u5de6\u5b50\u6811\u7684\u4e2d\u5e8f\u5e8f\u5217\uff0ca2\uff0c\u2026\uff0cai-1\u4e3a\u5de6\u5b50\u6811\u7684\u5148\u5e8f\u5e8f\u5217\u3002
\u540c\u6837\uff0c\u4e5f\u53ef\u786e\u5b9a\u53f3\u5b50\u6811\u7684\u4e2d\u5e8f\u548c\u5148\u5e8f\u5e8f\u5217\u3002 \u6309\u7167\u4e0a\u9762\u65b9\u6cd5\u5bf9\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u53ef\u786e\u5b9a\u5404\u81ea\u7684\u6839\u3002\u7ee7\u7eed\u4e0b\u53bb\u5373\u6784\u9020\u51fa\u4e8c\u53c9\u6811\u3002
\uff083\uff09\u7531\u540e\u5e8f\u904d\u5386\u5e8f\u5217\u548c\u4e2d\u5e8f\u904d\u5386\u5e8f\u5217\u80fd\u591f\u552f\u4e00\u786e\u5b9a\u4e00\u68f5\u4e8c\u53c9\u6811\u3002
\u8bbe\u540e\u5e8f\u5e8f\u5217\u4e3a\uff1aa2\uff0c\u2026\u2026\uff0can \uff0c a1\uff1b \u4e2d\u5e8f\u5e8f\u5217\u4e3a\uff1aap1\uff0c\u2026\uff0capi\uff0c a1\uff0c \u2026\uff0capn \u3002\u5219 a1\u4e3a\u6839\u7ed3\u70b9\uff1bap1\uff0c\u2026\uff0capi\u4e3a\u5de6\u5b50\u6811\u7684\u4e2d\u5e8f\u5e8f\u5217\uff0ca2\uff0c\u2026\uff0cai-1\u4e3a\u5de6\u5b50\u6811\u7684\u540e\u5e8f\u5e8f\u5217\u3002
\u540c\u6837\uff0c\u4e5f\u53ef\u786e\u5b9a\u53f3\u5b50\u6811\u7684\u4e2d\u5e8f\u548c\u540e\u5e8f\u5e8f\u5217\u3002\u6309\u7167\u4e0a\u9762\u65b9\u6cd5\u5bf9\u5de6\u5b50\u6811\u548c\u53f3\u5b50\u6811\u53ef\u786e\u5b9a\u5404\u81ea\u7684\u6839\u3002\u7ee7\u7eed\u4e0b\u53bb\u5373\u6784\u9020\u51fa\u4e8c\u53c9\u6811\u3002
知道后序,就能找到“根”,是最后一个节点。
知道“根”节点,就好办了,从中序中把根结点找到,它左边是左子树的中序,
右边是右子树的中序,知道这两子树的中序,就能从后序中,把左子序、右子树
找出来(据中序的左、右子树的结点数)。
这样,根节点找出来了,左子数的后序、中序就分离出来了,右子数也分离出来了,
这个问题,就化成两个新树的问题。同样的办法如此,就是递归成两个子树的新问题。
如果用程序,一样用递归就做出来了。
举个例子
中序:dgbaechf //左根右
后序:gdbehfca //左右根
(1)确定根
由后序得
中序:(dgb)a(echf) 后序:(gdb)(ehfc)a
(2)确定左节点
由上已知,左节点没有有节点
(3)确定右节点
中序【(e)c(hf)】 后序:【(e)(hf)c】
确定整棵树为
---------a--------
------b-----c-----
---d-----e----f---
------g-----h-----
绛旓細鐭ラ亾鍚庡簭锛屽氨鑳芥壘鍒扳滄牴鈥濓紝鏄渶鍚庝竴涓妭鐐广傜煡閬撯滄牴鈥濊妭鐐癸紝灏卞ソ鍔炰簡锛屼粠涓簭涓妸鏍圭粨鐐规壘鍒帮紝瀹冨乏杈规槸宸﹀瓙鏍戠殑涓簭锛屽彸杈规槸鍙冲瓙鏍戠殑涓簭锛岀煡閬撹繖涓ゅ瓙鏍戠殑涓簭锛屽氨鑳戒粠鍚庡簭涓紝鎶婂乏瀛愬簭銆佸彸瀛愭爲 鎵惧嚭鏉ワ紙鎹腑搴忕殑宸︺佸彸瀛愭爲鐨勭粨鐐规暟锛夈傝繖鏍凤紝鏍硅妭鐐规壘鍑烘潵浜嗭紝宸﹀瓙鏁扮殑鍚庡簭銆佷腑搴忓氨鍒嗙鍑...
绛旓細1銆侀潪閫掑綊鍓嶅簭閬嶅巻 鍙h瘈锛氭牴宸﹀彸銆傚墠搴忛亶鍘嗛鍏堣闂牴缁撶偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆傚湪閬嶅巻宸︺佸彸瀛愭爲鏃讹紝浠嶇劧鍏堣闂牴鑺傜偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆1.1 鍏蜂綋娴佺▼ 1.2 鍏蜂綋浠g爜 2銆侀潪閫掑綊涓簭閬嶅巻 涓簭閬嶅巻鏄滃乏鏍瑰彸"锛屽嵆鍏堥亶鍘嗗乏瀛愭爲鑺傜偣锛屽啀閬嶅巻鏍硅妭鐐癸紝鍐嶉亶鍘嗗彸瀛愭爲鑺傜偣 2...
绛旓細瀛愭爲涓簭閬嶅巻涓4 7 2锛屽墠搴忛亶鍘嗕负2 4 7 鍥犱负鍓嶅簭閬嶅巻涓烘牴宸﹀彸锛屽彲浠ョ‘瀹氬叾鏍硅妭鐐逛负2 浣嗗悗缁4 7鍙兘鏄竴宸︿竴鍙筹紝涔熷彲鑳介兘鏄乏鎴栭兘鏄彸锛岃繕瑕佺粨鍚堜腑搴忛亶鍘嗘潵鐪 鍥犱负涓簭閬嶅巻涓哄乏鏍瑰彸锛屾牴鑺傜偣宸茬粡纭畾涓2锛岄偅涔堝叾宸﹁竟鐨4 7閮芥槸宸﹀瓙鏍 鍥犳涓よ呯患鍚堝悗鍙煡鏍硅妭鐐2鐨勫乏瀛愭爲涓4 7锛屾病鏈夊彸瀛愭爲 ...
绛旓細鍙冲瓙鏍 鍓嶅簭锛 C K G锛 涓簭锛 K C G 鎴戜滑鍙互鏍规嵁鍓嶅簭锛岀‘璁涓烘牴鑺傜偣锛屽乏鑺傜偣K锛屽彸鑺傜偣 G 杩欐牱锛屾垜浠殑浜屽弶鏍戝氨鐢诲ソ鍟︺傘
绛旓細鏁版嵁缁撴瀯涓庣畻娉曗浜屽弶鏍鐨勫眰搴忋佸墠搴忎腑搴忓悗搴忛亶鍘嗚瑙e眰搴忛亶鍘嗘槸鎸夊眰娆¢『搴忛亶鍘嗕簩鍙夋爲锛屽叧閿湪浜庡潎琛″鐞嗗乏鍙冲瓙鑺傜偣锛屽洜姝わ紝閲囩敤闃熷垪浣滀负鏁版嵁缁撴瀯銆傚叾浠g爜瀹炵幇鐩磋鏄撴噦锛屼富瑕侀氳繃閫愬眰娣诲姞鑺傜偣鍒伴槦鍒楋紝鐒跺悗渚濇鍙栧嚭澶勭悊銆傚墠搴忋涓簭鍜屽悗搴閬嶅巻鍒欒繍鐢ㄩ掑綊鏂规硶锛岀被浼间簬娣卞害浼樺厛鎼滅储銆傚墠搴忛亶鍘嗚鍒欐槸鏍硅妭鐐 -> ...
绛旓細浜屽弶鏍閬嶅巻鏂瑰紡鏄鏁版嵁缁撴瀯鐨勫熀纭鐭ヨ瘑锛屼綔涓鸿绠楁満涓撲笟鐨勫ぇ瀛︾敓锛屾垜鐨勭悊瑙e涓嬶細1銆 鍓嶅簭閬嶅巻 瀹冪殑閬嶅巻椤哄簭鏄細鍏堣闂牴缁撶偣锛屽啀杩涘叆杩欎釜鏍圭粨鐐圭殑宸﹀瓙鏍戯紱浠ヤ笂杩版柟寮忛亶鍘嗗畬鎵鏈夊乏瀛愭爲鍚庯紝鍐嶈繘鍏ュ畠鐨勫彸瀛愭爲锛屼互鍚屾牱鐨勬柟寮忛亶鍘嗗彸瀛愭爲涓殑缁撶偣锛屽嵆鏍圭粨鐐光啋宸﹀瓙鏍戔啋鍙冲瓙鏍戙備笅鍥句腑1涓轰富鏍圭粨鐐癸紝245涓哄乏瀛愭爲...
绛旓細鏈変簡杩欐牱鐨勫噯澶囷紝灏卞彲浠ョ湅鐪嬪浣曠敓鎴愪竴妫浜屽弶鏍浜嗐傚亣璁句簩鍙夋爲鐨勭粨鐐瑰潎涓轰竴涓瓧绗︼紝鎶婂垰鎵嶅墠搴閬嶅巻搴忓垪AB#D##C##鐢ㄩ敭鐩樻尐涓緭鍏ワ紝瀹炵幇鐨勭畻娉曞涓嬫墍绀恒備簩鍙夋爲寤虹珛瀹炵幇浠g爜涓锛屽涓嬫墍绀恒//鍒涘缓鏍//鎸夊厛鍚庢搴忚緭鍏ヤ簩鍙夋爲涓粨鐐圭殑鍊(涓涓瓧绗),#琛ㄧず绌烘爲//鏋勯犱簩鍙夐摼琛ㄨ〃绀虹殑浜屽弶鏍態iTree CreateTree...
绛旓細棣栧厛瑕佹悶鏄庣櫧浜屽弶鏍鐨勫嚑绉嶉亶鍘嗘柟娉曪細锛1锛夈佸厛搴忛亶鍘嗘硶锛氭牴宸﹀彸锛涳紙2锛夈涓簭閬嶅巻娉曪細宸︽牴鍙筹紱锛3锛夈鍚庡簭閬嶅巻娉曪細宸﹀彸鏍广傚叾涓牴锛氳〃绀烘牴鑺傜偣锛涘乏锛氳〃绀哄乏瀛愭爲锛涘彸锛氳〃绀哄彸瀛愭爲銆傝嚦浜庤皥鍒濡備綍鐢鍏堝簭閬嶅巻鐨勬祦绋嬪浘锛屽彲浠ヨ繖鏍疯冭檻锛氭寜鐓ч掑綊鐨勭畻娉曡繘琛岄亶鍘嗕竴妫典簩鍙夋爲銆傜▼搴忛鍏堣闂牴鑺傜偣锛屽鏋滄牴鑺傜偣...
绛旓細鍏堝簭閬嶅巻缁撴灉涓猴細ABD HI EJCFKG 涓簭閬嶅巻 涓簭閬嶅巻鍙互鐪嬫垚锛浜屽弶鏍姣忎釜鑺傜偣锛屽瀭鐩存柟鍚戞姇褰变笅鏉(鍙互鐞嗚В涓烘瘡涓妭鐐逛粠鏈宸﹁竟寮濮嬪瀭鐩存帀鍒板湴涓)锛岀劧鍚庝粠宸﹀線鍙虫暟锛屽緱鍑虹殑缁撴灉渚挎槸涓簭閬嶅巻鐨勭粨鏋溿傚阀璁帮細宸︽牴鍙 涓亶鍘嗙粨鏋滀负锛欻DIBEJAFKCG 鍚庡簭閬嶅巻 鍚庡簭閬嶅巻灏卞儚鏄壀钁¤悇锛屾垜浠鎶婁竴涓茶憽钀勫壀鎴愪竴棰...
绛旓細1銆侀鍏堢涓姝ヨ嫢鑺傜偣鍙冲乏瀛愭爲锛屽垯宸﹂摼鍩焞child鎸囩ず鍏跺乏瀛╁瓙锛坙tag=0锛,鍚﹀垯锛屼护宸﹂摼鍩熸寚绀哄叾鍓嶉┍锛坙tag=1锛夈傝嫢缁撶偣鏈夊彸瀛愭爲锛屽垯鍙抽摼鍩焤child鎸囩ず鍏跺彸瀛╁瓙锛坮tag=0锛,鍚﹀垯锛屼护鍙抽摼鍩熸寚绀哄叾鍚庣户锛坮tag=1锛夈2銆佺劧鍚庡嚮浜呭疄鐜拌繖涓杩囩▼锛岃鎸囬拡p鎸囧悜褰撳墠缁撶偣锛宲re濮嬬粓鎸囧悜鍒氬垰璁块棶杩囩殑缁撶偣锛屽嵆p鐨...