关于二叉树的递归遍历还是不理解 那位高手能不能详细讲一下!!! 二叉树非递归后序遍历的思想是什么 越详细越好 急急!!!!
\u4e8c\u53c9\u6811 \u4e2d\u5e8f\u904d\u5386\u9012\u5f52\u7b97\u6cd5\u540e\u5e8f\u904d\u5386\u9012\u5f52\u7b97\u6cd5\u80fd\u8be6\u7ec6\u8bb2\u4e00\u4e0b\u5417\uff1f\u771f\u6b63\u5b9e\u7528\u7f16\u7a0b\u4e2d\uff0c\u4e5f\u6ca1\u6709\u5fc5\u8981\u592a\u8ba1\u8f83\u3002
\u6309\u7167\u4e8c\u53c9\u6811\u540e\u5e8f\u904d\u5386\u7684\u5b9a\u4e49\uff0c\u65e0\u8bba\u662f\u8bbf\u95ee\u6574\u9897\u6811\u8fd8\u662f\u5176\u5b50\u6811\u5747\u5e94\u8be5\u9075\u5faa\u9009\u8bbf\u95ee\u6839\u7ed3\u70b9\u7684\u5de6\u5b50\u6811\uff0c\u7136\u540e\u8bbf\u95ee\u6839\u7ed3\u70b9\u7684\u53f3\u5b50\u6811\uff0c\u6700\u540e\u8bbf\u95ee\u6839\u7ed3\u70b9\u7684\u89c4\u5f8b\u3002\u56e0\u6b64\u5bf9\u4e8e\u4e00\u68f5\u6811\uff08\u5b50\u6811\uff09t \uff0c\u5982\u679c t \u975e\u7a7a\uff0c\u9996\u5148\u5e94\u8be5\u8fdb\u5165t\u7684\u5de6\u5b50\u6811\u8bbf\u95ee\uff0c\u6b64\u65f6\u7531\u4e8et\u7684\u53f3\u5b50\u6811\u53ca\u6839\u7ed3\u70b9\u5c1a\u672a\u8bbf\u95ee\uff0c\u56e0\u6b64\u5fc5\u987b\u5c06t\u4fdd\u5b58\u8d77\u6765\uff0c\u653e\u5165\u6808\u4e2d\uff0c\u4ee5\u4fbf\u8bbf\u95ee\u5b8c\u5de6\u5b50\u6811\u540e\uff0c\u4ece\u6808\u4e2d\u53d6\u51fat\uff0c\u8fdb\u884c\u5176\u53f3\u5b50\u6811\u53ca\u6839\u7ed3\u70b9\u7684\u8bbf\u95ee\u3002\u8fd9\u91cc\u503c\u5f97\u6ce8\u610f\u7684\u662f\uff0c\u5f53\u4e00\u4e2a\u5143\u7d20\u4f4d\u4e8e\u6808\u9876\u5373\u5c06\u5904\u7406\u65f6\uff0c\u5176\u5de6\u5b50\u6811\u7684\u8bbf\u95ee\u4e00\u5b9a\u5df2\u7ecf\u5b8c\u6210\uff0c\u5982\u679c\u5176\u53f3\u5b50\u6811\u5c1a\u672a\u904d\u5386\uff0c\u63a5\u4e0b\u6765\u5e94\u8be5\u8fdb\u5165\u5176\u53f3\u5b50\u6811\u7684\u8bbf\u95ee\uff0c\u800c\u6b64\u65f6\u8be5\u6808\u9876\u5143\u7d20\u662f\u4e0d\u80fd\u51fa\u6808\u7684\uff0c\u56e0\u4e3a\u5176\u6839\u7ed3\u70b9\u8fd8\u672a\u88ab\u8bbf\u95ee\uff1b\u53ea\u6709\u7b49\u5230\u5176\u53f3\u5b50\u6811\u4e5f\u8bbf\u95ee\u5b8c\u6210\u540e\uff0c\u8be5\u6808\u9876\u5143\u7d20\u624d\u80fd\u51fa\u6808\uff0c\u5e76\u8f93\u5176\u6839\u7ed3\u70b9\u7684\u503c\u3002\u56e0\u6b64\uff0c\u5728\u4e8c\u53c9\u6811\u540e\u5e8f\u904d\u5386\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5fc5\u987b\u4f7f\u7528seq.stack\u7c7b\u578b\u4e2d\u7684\u6570\u7ec4tag\uff0c\u5176\u6bcf\u4e2a\u5143\u7d20\u53d6\u503c\u4e3a0\u62161\uff0c\u7528\u4e8e\u6807\u8bc6\u6808\u4e2d\u6bcf\u4e2a\u5143\u7d20\u7684\u72b6\u6001\u3002\u5f53\u4e00\u4e2a\u5143\u7d20\u521a\u8fdb\u6808\u65f6\uff0c\u5176\u5bf9\u5e94\u7684tag\u503c\u7f6e0\uff1b\u5f53\u5b83\u7b2c\u4e00\u6b21\u4f4d\u4e8e\u6808\u9876\u5373\u5c06\u88ab\u5904\u7406\u65f6\uff0c\u5176tag\u503c\u4e3a0\uff0c\u610f\u5473\u7740\u5e94\u8be5\u8bbf\u95ee\u5176\u53f3\u5b50\u6811\uff0c\u4e8e\u662f\u5c06\u5176\u53f3\u5b50\u6811\u4f5c\u4e3a\u5f53\u524d\u5904\u7406\u7684\u5bf9\u8c61\uff0c\u6b64\u65f6\u8be5\u6808\u9876\u5143\u7d20\u4ecd\u5e94\u8be5\u4fdd\u7559\u5728\u6808\u4e2d\uff0c\u5e76\u5c06\u5176\u5bf9\u5e94\u7684tag\u503c\u6539\u4e3a1\uff1b\u5f53\u5176\u53f3\u5b50\u6811\u8bbf\u95ee\u5b8c\u6210\u540e\uff0c\u8be5\u5143\u7d20\u53c8\u4e00\u6b21\u4f4d\u4e8e\u6808\u9876\uff0c\u800c\u6b64\u65f6\u5176tag\u503c\u4e3a1\uff0c\u610f\u5473\u7740\u5e94\u8be5\u8bbf\u95ee\u5176\u6839\u7ed3\u70b9\uff0c\u5e76\u5c06\u5176\u51fa\u6808\u3002\u5728\u6574\u4e2a\u4e8c\u53c9\u6811\u540e\u5e8f\u904d\u5386\u7684\u8fc7\u7a0b\u4e2d\uff0c\u7a0b\u5e8f\u8981\u505a\u7684\u5de5\u4f5c\u59cb\u7ec8\u5206\u6210\u4e24\u4e2a\u90e8\u5206\uff1a\u5f53\u524d\u6b63\u5728\u5904\u7406\u7684\u6811\uff08\u5b50\u6811\uff09\u548c\u4fdd\u5b58\u5728\u6808\u4e2d\u5f85\u5904\u7406\u7684\u90e8\u5206\u3002\u53ea\u6709\u8fd9\u4e24\u90e8\u5206\u7684\u5de5\u4f5c\u5747\u5b8c\u6210\u540e\uff0c\u7a0b\u5e8f\u65b9\u80fd\u7ed3\u675f\u3002
\uff08\u4ee5\u4e0a\u5b58\u624b\u5de5\u8f93\u5165\uff09
先序遍历:就是先访问根节点,再访问其左子树。最后访问右子树。
A
/ \
B C
/ \ / \
D E F G
对于遍历来说无论是哪种遍历,采取的思路是遍历左子树和右子树的时候,把左子树和右子树当成一棵新的完整的二叉树来对待,按照指定的遍历方法进行遍历,就比较容易理解了。
例如:先序遍历
1、首先访问根节点A,然后接下来要去访问它的左子树
2、将它的左子树当成一棵完整的二叉树:
B
/ \
D E
这个你要采用先序来进行遍历的话,还是先遍历根节点,然后左子树,然后右子树。那么这个时候必定要先访问根节点B了。
3、再将B的左子树当成一棵新的二叉树:
D
由于其没有子树了,就只有一个根节点。所以这个时候就访问这个根节点D
4、同样的道理再去访问B的右子树E。
5、到这个地方,对于根节点A的左子树才完整遍历了。
6、同样的道理接着去访问A的右子树,还是将它的右子树当成一个新的二叉树,进行遍历。遍历结果是CFG。
7、最终的遍历结果就是ABDECFG。
/* 我的理解是递归A->B->D,然后就回到A了,怎么到了B就停了 去访问E,就是这点我不理解 ,请你帮我理一下思路,到底是怎么回事啊???*/
你的理解只是单纯的理解为访问左子树的时候,只是左边的是它的左子树,其实在访问的时候只要是处在A左边的全部都是它的左子树。。。
希望我的回答对你有所帮助。。。。。
主要有三种遍历方法,先序遍历,中序遍历,后序遍历。
先序遍历:就是先访问根节点,再访问其左子树。最后访问右子树。
A
/ \
B C
/ \ / \ B
D E F G / \
例如:先访问A,再访问其左子树 D E ,那么,对于这个树,先访问其根节点B,再访问其左子树D。D没有左右子树。于是访问B的右子树E。E没有子树。返回A,访问A的右子树。即:C 与其左子树F和右子树G。最后得出遍历序列是:ABDECFG。
中序遍历:就是先访问左子树,再访问其根节点。最后访问右子树。
遍历方法如上:最后遍历序列:DBEAFCG
后序遍历:先访问左子树,再访问其右子树。最后访问根节点。
同样方法:遍历序列:DEBFGCA
绛旓細鏈鍚閫掑綊鍦閬嶅巻鍙冲瓙鏍戙- 涓簭閬嶅巻锛圛n-order Traversal锛夛細棣栧厛閫掑綊鍦伴亶鍘嗗乏瀛愭爲锛岀劧鍚庤闂牴鑺傜偣锛屾渶鍚庨掑綊鍦伴亶鍘嗗彸瀛愭爲銆- 鍚庡簭閬嶅巻锛圥ost-order Traversal锛夛細棣栧厛閫掑綊鍦伴亶鍘嗗乏瀛愭爲锛岀劧鍚庨掑綊鍦伴亶鍘嗗彸瀛愭爲锛屾渶鍚庤闂牴鑺傜偣銆3. 浠ヤ笂鏄鍏充簬浜屽弶鏍戠殑瀹氫箟鍜岄亶鍘嗘柟娉曠殑姒傝堪锛屽笇鏈涘鎮ㄦ湁鎵甯姪銆
绛旓細杩欎笉灏辨槸鍦ㄤ簩鍙夋帓搴忔爲涓鐨勯掑綊鏌ユ壘锛岀湅绋嬪簭 tree& find(const T& d,tree& t){ if(t==NULL)return t;濡傛灉浜屽弶鏍涓虹┖鍒欒繑鍥炵┖锛屾煡鎵惧け璐 if(t->data==d)return t;鍚﹀垯锛屽鏋滃綋鍓嶆牴缁撶偣鍏抽敭鐮佷负d锛屽垯鏌ユ壘鎴愬姛锛屽綋鍓嶆牴缁撶偣涓哄緟鏌ユ壘缁撶偣 if(d>t->data)return find(d,t->right);濡傛灉姣旀牴鐨...
绛旓細鑻ユ湁锛夊拰宸﹀瓙鑺傜偣锛堣嫢鏈夛級鎸夐『搴忓叆鏍堬紝鐩磋嚦鏍堢┖銆備腑搴忛亶鍘嗗拰鍚庡簭閬嶅巻鐨勯潪閫掑綊绠楁硶绫讳技锛屼絾鎿嶄綔椤哄簭绋嶆湁涓嶅悓锛屽叿浣撴楠ゆ秹鍙婂垽鏂妭鐐圭殑瀛愯妭鐐圭姸鎬併傛棤璁烘槸閫掑綊杩樻槸闈為掑綊锛浜屽弶鏍戦亶鍘閮芥槸鐞嗚В鏍缁撴瀯鍜屾搷浣滄爲鏁版嵁鐨勯噸瑕佸熀纭銆傞氳繃鎺屾彙杩欎簺鏂规硶锛屾垜浠彲浠ユ湁鏁堝湴鍦ㄥ疄闄呴棶棰樹腑搴旂敤浜屽弶鏍戞暟鎹粨鏋勩
绛旓細瑕佹兂鎶婃墍鏈夌殑鏁版嵁閮借闂埌鍒欏繀闇鎸夌収涓瀹氱殑鍘熷垯锛屽嵆褰撳墠缁撶偣鐨勪笅涓涓粨鐐规槸鍝釜缁撶偣銆傛棤璁烘槸鍏堛佷腑杩樻槸鍚庡簭绠楁硶閮芥槸鍏堝皢宸︾粨鐐硅涓轰笅涓涓粨鐐癸紝褰撳乏缁撶偣涓嶅瓨鍦紙鍗充负绌烘椂锛夋墠灏嗗彸缁撶偣瑙嗕綔涓嬩竴涓粨鐐癸紝濡傛灉鍙崇粨鐐逛篃涓嶅瓨鍦ㄥ氨杩斿洖褰撳墠缁撶偣鐨勪笂灞傜粨鐐瑰啀鍚戝彸璁块棶锛屽姝ょ被鎺ㄣ備簬鏄浜屽弶鏍戠殑閬嶅巻闂灏辫...
绛旓細鈶 } 鈶 } // InOrder 閬嶅巻搴忓垪 锛庨亶鍘浜屽弶鏍戠殑鎵ц韪抗 涓夌閫掑綊閬嶅巻绠楁硶鐨勬悳绱㈣矾绾跨浉鍚岋紙濡備笅鍥捐櫄绾挎墍绀猴級 鍏蜂綋绾胯矾涓 浠庢牴缁撶偣鍑哄彂 閫嗘椂閽堟部鐫浜屽弶鏍戝缂樼Щ鍔 瀵规瘡涓粨鐐瑰潎閫斿緞涓夋 鏈鍚庡洖鍒版牴缁撶偣 锛庨亶鍘嗗簭鍒 锛 锛 涓簭搴忓垪 涓簭閬嶅巻浜屽弶鏍戞椂 瀵圭粨鐐圭殑璁块棶娆″簭涓轰腑搴忓簭鍒椼愪緥銆戜腑...
绛旓細鍙屾寚閽堟槸鍙互鐩存帴淇敼浜屽弶鏍鑺傜偣锛屼篃鍙互淇敼鑺傜偣鐨勫硷紝鍏锋湁鏇村ソ鐨勭伒娲绘 鑰屽紩鐢ㄥ舰鍙傚彧鑳戒慨鏀硅妭鐐瑰硷紝涓嶈兘淇敼鑺傜偣銆傜畝鍗曠殑姣斿柣灏辨槸锛屽弻鎸囬拡鍙互鍍忔満鍣ㄤ竴鏍锋崲闆朵欢鎴栬呯洿鎺ヤ慨闆朵欢锛屽紩鐢ㄥ舰鍙傚彧鑳戒慨闆朵欢銆
绛旓細鏇磋娉ㄦ剰鐨勬槸锛屽厛搴忚皟鐢鐨勯掑綊鍑芥暟杩樻病鎵ц瀹岋紝鍦ㄥ厛搴忚皟鐢ㄧ殑鏈閲屽眰锛岃鎵ц杩欎釜鍑芥暟鐨勬渶鍚庝竴涓鍙ワ紝鍗冲厛搴忚闂彸瀛愭爲銆傚湪浜嗚В閫掑綊鍑芥暟鏃讹紝瑕佹敞鎰忓嚱鏁版槸涓灞備竴灞傛墽琛岀殑锛屾妸娌℃湁璋冪敤鐨勫嚱鏁扮湅浣滃摝鏄涓灞傦紝绗竴娆¤皟鐢ㄧ殑鏃跺欙紝锛屽娍蹇呬細绗簩娆¢亣鍒拌皟鐢ㄥ嚱鏁帮紝鍙樻垚绗簩灞傦紝锛岋紝...
绛旓細鍏堝簭鍒楀彿涓鸿繖涓紝閭d箞鍦ㄧ紪杈戠殑鏃跺欙紝鍙互鍏堣繘琛岀敤椤哄簭鐨勬柟寮忥紝鐒跺悗鍐嶈繘琛屻傚悗搴忓簭鍒楁槸CBA銆傛牴鎹墠搴忥紝鍙互纭畾A涓烘牴锛孉鍦ㄤ腑搴忎腑鐨勪綅缃紝鍙互纭畾CB涓篈鐨勫乏瀛愭爲涓婄殑缁撶偣锛屾病鏈夊彸瀛愭爲銆傜‘瀹欰涔嬪悗锛屽啀鐪嬩腑搴忕浜屽间负B锛屾煡鐪婤鍦ㄤ腑搴忎腑鐨勪綅缃紝C鍦˙宸﹁竟锛岀‘瀹欳涓築鐨勫乏瀛愭爲銆
绛旓細鍚庡簭閬嶅巻锛圥ostorderTraversal锛夛紙LRN锛夛細璁块棶鑺傜偣鍙戠敓鍦ㄩ亶鍘嗗乏鍙冲瓙鏍戜箣鍚庛傚湪浜屽弶鏍戠殑閬嶅巻绠楁硶涓紝浠ヤ腑搴忛亶鍘嗕负渚嬶紝鍏跺畾涔夊涓嬶細濡傛灉浜屽弶鏍戦潪绌猴紝灏辨寜鐓у乏瀛愭爲銆佹牴鑺傜偣銆佸彸瀛愭爲鐨勯『搴忚繘琛屾搷浣溿傚厛搴忛亶鍘嗗拰鍚庡簭閬嶅巻鐨勫畾涔夌被浼硷紝鍙槸璁块棶鏍硅妭鐐圭殑浣嶇疆涓嶅悓銆傞亶鍘嗛『搴忕殑浣撶幇鍙氳繃浜屽弶鏍戠殑鎼滅储璺嚎鐞嗚В锛屼粠鏍...
绛旓細锛3锛変腑搴閬嶅巻鍙冲瓙鏍 濡傚彸鍥炬墍绀浜屽弶鏍锛屼腑鏍归亶鍘嗙粨鏋滐細DBEAFC 3銆佸悗鏍归亶鍘嗕竴鑸寚鍚庡簭閬嶅巻锛屾寚鍦ㄨ闂牴缁撶偣銆侀亶鍘嗗乏瀛愭爲涓庨亶鍘嗗彸瀛愭爲涓夎呬腑锛岄鍏堥亶鍘嗗乏瀛愭爲锛岀劧鍚庨亶鍘嗗彸瀛愭爲锛屾渶鍚庨亶鍘嗚闂牴缁撶偣锛屽湪閬嶅巻宸︺佸彸瀛愭爲鏃讹紝浠嶇劧鍏堥亶鍘嗗乏瀛愭爲锛岀劧鍚庨亶鍘嗗彸瀛愭爲锛屾渶鍚庨亶鍘嗘牴缁撶偣銆傚悗搴忛亶鍘嗘湁閫掑綊绠楁硶鍜岄潪閫掑綊...