二叉树的遍历有几种方式?
1、先根遍历一般是先序遍历(Pre-order),按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中,先根后左再右。巧记:根左右。
首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。
例如,下图所示二叉树的先根遍历结果是:ABDECF
2、中根遍历一般指中序遍历,在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。
中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回,否则:(1)中序遍历左子树
(2)访问根结点
(3)中序遍历右子树
如右图所示二叉树,中根遍历结果:DBEAFC
3、后根遍历一般指后序遍历,指在访问根结点、遍历左子树与遍历右子树三者中,首先遍历左子树,然后遍历右子树,最后遍历访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。后序遍历有递归算法和非递归算法两种。
如右图所示二叉树,后根遍历结果:DEBFCA
4、左子树就是以当前节点看,它的左子节点那一分支的子树,该子树以当前节点左子节点为根。
5、右子树就是以当前节点看,它的右子节点那一分支的子树,该子树以当前节点右子节点为根。左右子树只在二叉树中有意义,因为二叉树非左即右。
6、二叉树
在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
绛旓細1銆佸厛鏍归亶鍘嗕竴鑸槸鍏堝簭閬嶅巻(Pre-order)锛屾寜鐓ф牴宸﹀彸鐨勯『搴忔部涓瀹氳矾寰勭粡杩囪矾寰勪笂鎵鏈夌殑缁撶偣銆傚湪浜屽弶鏍戜腑锛屽厛鏍瑰悗宸﹀啀鍙炽傚阀璁帮細鏍瑰乏鍙炽傞鍏堣闂牴缁撶偣鐒跺悗閬嶅巻宸﹀瓙鏍戯紝鏈鍚庨亶鍘嗗彸瀛愭爲銆傚湪閬嶅巻宸︺佸彸瀛愭爲鏃讹紝浠嶇劧鍏堣闂牴缁撶偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲锛屽鏋滀簩鍙夋爲涓虹┖鍒欒繑鍥炪備緥濡傦紝涓嬪浘鎵绀轰簩...
绛旓細浜屽弶鏍戞槸涓绉嶆爲褰㈢粨鏋勶紝姣忎釜鑺傜偣鏈澶氭湁涓や釜瀛愯妭鐐癸紝鍒嗗埆绉颁负宸﹀瓙鑺傜偣鍜屽彸瀛愯妭鐐广浜屽弶鏍戠殑閬嶅巻鏂瑰紡鏈変笁绉嶏細鍓嶅簭閬嶅巻銆佷腑搴忛亶鍘嗗拰鍚庡簭閬嶅巻銆傚墠搴忛亶鍘嗙殑鏂瑰紡鏄鍏堣闂牴鑺傜偣锛岀劧鍚庤闂乏瀛愭爲锛屾渶鍚庤闂彸瀛愭爲銆備腑搴忛亶鍘嗙殑鏂瑰紡鏄鍏堣闂乏瀛愭爲锛屾帴鐫璁块棶鏍圭粨鐐癸紝鏈鍚庤闂彸瀛愭爲銆傚悗搴忛亶鍘嗙殑鏂瑰紡鏄鍏堣...
绛旓細浜屽弶鏍戦亶鍘嗘柟娉曟渶甯哥敤鐨勫ぇ鑷存湁鍥涚锛氬厛搴忛亶鍘锛屼篃鍙厛鏍归亶鍘嗐傚氨鏄厛璁块棶鏍圭粨鐐癸紝鍐嶈闂乏瀛愭爲锛屾渶鍚庤闂彸瀛愭爲銆備腑搴忛亶鍘嗭紝涔熷彨涓牴閬嶅巻銆傚氨鏄厛璁块棶宸﹀瓙鏍戯紝鍐嶈闂牴鑺傜偣锛屾渶鍚庤闂彸瀛愭爲銆傚悗搴忛亶鍘嗭紝涔熷彨鍚庢牴閬嶅巻銆傚氨鏄厛璁块棶宸﹀瓙鏍戯紝鍐嶈闂彸瀛愭爲锛屾渶鍚庤闂牴缁撶偣銆傛寜灞傛閬嶅巻锛屽氨鏄浜屽弶鏍戜粠涓...
绛旓細浜屽弶鏍戞湁涓夌閬嶅巻鏂规硶锛鍏堝簭閬嶅巻锛岄鍏堣闂牴锛屽啀鍏堝簭閬嶅巻宸﹀瓙鏍戯紝鏈鍚庡厛搴忛亶鍘嗗彸瀛愭爲銆備腑搴忛亶鍘嗭紝棣栧厛涓簭閬嶅巻宸﹀瓙鏍戯紝鍐嶈闂牴锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆傚悗搴忛亶鍘嗭紝棣栧厛鍚庡簭閬嶅巻宸﹀瓙鏍戯紝鍐嶅悗搴忛亶鍘嗗彸瀛愭爲锛屾渶鍚庤闂牴銆
绛旓細浜屽弶鏍戠殑閬嶅巻鏄寚涓嶉噸澶嶅湴璁块棶浜屽弶鏍戜腑鐨勬墍鏈夌粨鐐广浜屽弶鏍戠殑閬嶅巻鍙互鍒嗕负浠ヤ笅涓夌锛氾紙1锛夊墠搴忛亶鍘嗭紙DLR锛夛細鑻ヤ簩鍙夋爲涓虹┖锛屽垯缁撴潫杩斿洖銆傚惁鍒欙細棣栧厛璁块棶鏍圭粨鐐癸紝鐒跺悗閬嶅巻宸﹀瓙鏍戯紝鏈鍚庨亶鍘嗗彸瀛愭爲锛涘苟涓旓紝鍦ㄩ亶鍘嗗乏鍙冲瓙鏍戞椂锛屼粛鐒跺厛璁块棶鏍圭粨鐐癸紝鐒跺悗閬嶅巻宸﹀瓙鏍戯紝鏈鍚庨亶鍘嗗彸瀛愭爲銆傦紙2锛変腑搴忛亶鍘嗭紙LDR锛夛細鑻...
绛旓細鏍戠殑閬嶅巻涓夌椤哄簭濡備笅锛1銆佸墠搴忛亶鍘:鏍硅妭鐐+宸﹀瓙鏍+鍙冲瓙鏍戙2銆侀亶鍘嗗乏瀛愭爲鍜屽彸瀛愭爲鏃讹紝浠嶇劧鍏堣闂牴鑺傜偣锛岀劧鍚庨亶鍘嗗乏瀛愭爲锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆涓簭閬嶅巻:宸﹀瓙鏍+鏍硅妭鐐+鍙冲瓙鏍戙3銆侀亶鍘嗗乏鍙冲瓙鏍戞椂锛屼粛鐒跺厛閬嶅巻宸﹀瓙鏍戯紝鍐嶉亶鍘嗘牴鑺傜偣锛屽悗閬嶅巻鍙冲瓙鏍戙傚悗搴忛亶鍘:宸﹀瓙鏍+鍙冲瓙鏍+鏍硅妭鐐广傞亶鍘嗗乏鍙冲瓙鏍戞椂锛屼粛鐒...
绛旓細1锛庨亶鍘嗘柟妗 浠庝簩鍙夋爲鐨勯掑綊瀹氫箟鍙煡锛屼竴妫甸潪绌虹殑浜屽弶鏍戠敱鏍圭粨鐐瑰強宸︺佸彸瀛愭爲杩欎笁涓熀鏈儴鍒嗙粍鎴愩傚洜姝わ紝鍦ㄤ换涓缁欏畾缁撶偣涓婏紝鍙互鎸夋煇绉嶆搴忔墽琛屼笁涓搷浣滐細 锛1锛夎闂粨鐐规湰韬(N)锛 锛2锛夐亶鍘嗚缁撶偣鐨勫乏瀛愭爲(L)锛 锛3锛夐亶鍘嗚缁撶偣鐨勫彸瀛愭爲(R)銆備互涓涓夌鎿嶄綔鏈夊叚绉嶆墽琛屾搴忥細 NLR銆丩NR銆丩RN銆丯RL...
绛旓細浜屽弶鏍戠殑閬嶅巻鏂规硶閫氬父鏈夛細鍏堟牴閬嶅巻鎴栧厛搴忛亶鍘嗭細棣栧厛璁块棶鏍硅妭鐐癸紝鎺ョ潃閬嶅巻宸﹀瓙鏍戯紝鏈鍚庨亶鍘嗗彸瀛愭爲銆涓牴閬嶅巻鎴栦腑搴忛亶鍘锛氶鍏堥亶鍘嗗乏瀛愭爲锛岀劧鍚庤闂牴鑺傜偣锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆傚悗鏍归亶鍘嗘垨鍚庡簭閬嶅巻锛氶鍏堥亶鍘嗗乏瀛愭爲锛岀劧鍚庨亶鍘嗗彸瀛愭爲锛屾渶鍚庤闂牴缁撶偣銆傛寜灞傛閬嶅巻鎴栧搴︿紭鍏堥亶鍘嗭紝浠庢牴鑺傜偣寮濮嬭闂紝浠庝笂寰涓嬭闂...
绛旓細1锛夊厛搴忛亶鍘嗭紝鎸夌収鏍瑰乏鍙崇殑椤哄簭娌夸竴瀹氳矾寰勭粡杩囪矾寰勪笂鎵鏈夌殑缁撶偣銆傚湪浜屽弶鏍戜腑锛屽厛鏍瑰悗宸﹀啀鍙炽2锛涓簭閬嶅巻锛岄鍏堥亶鍘嗗乏瀛愭爲锛岀劧鍚庤闂牴缁撶偣锛屾渶鍚庨亶鍘嗗彸瀛愭爲銆3锛夊悗搴忛亶鍘嗭紝鍙鍋氬乏鍙虫牴銆傚湪浜屽弶鏍戜腑锛屽厛宸﹀悗鍙冲啀鏍癸紝鍗抽鍏堥亶鍘嗗乏瀛愭爲锛岀劧鍚庨亶鍘嗗彸瀛愭爲锛屾渶鍚庤闂牴缁撶偣銆4锛夎繖妫典簩鍙夋爲鐨勬牴鑺傜偣鏄疉...
绛旓細浣嗕笉甯哥敤锛屾澶勪笉鍋氳В閲婏級銆1.鍓嶅簭閬嶅巻锛氭牴鑺傜偣->宸﹀瓙鏍->鍙冲瓙鏍戯紙鏍硅妭鐐瑰湪鍓嶉潰锛夈2.涓簭閬嶅巻锛氬乏瀛愭爲->鏍硅妭鐐->鍙冲瓙鏍戯紙鏍硅妭鐐瑰湪涓棿锛夈3.鍚庡簭閬嶅巻锛氬乏瀛愭爲->鍙冲瓙鏍->鏍硅妭鐐癸紙鏍硅妭鐐瑰湪鍚庤竟锛夈備緥濡傦細姹備笅闈㈡爲鐨涓夌閬嶅巻锛氬墠搴忛亶鍘嗭細abdefgc锛涗腑搴忛亶鍘嗭細debgfac锛涘悗搴忛亶鍘嗭細edgfbca銆