- 二叉樹的結(jié)構(gòu)
二叉樹是樹的特殊形式，它包含結(jié)點(diǎn)值（可空）锦亦，左孩子結(jié)點(diǎn)（可空）舶替，右孩子結(jié)點(diǎn)（可空）「茉埃空樹即三者均為空顾瞪，當(dāng)任一結(jié)點(diǎn)只有左孩子或右孩子時(shí)，這顆樹的結(jié)構(gòu)就與鏈表類似了抛蚁。 - 定義一個(gè)二叉樹的結(jié)點(diǎn)代碼清單如下：
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface TreeNode : NSObject
@property(nonatomic,assign) NSInteger value;
@property(nonatomic,strong,nullable) TreeNode* leftChild;
@property(nonatomic,strong,nullable) TreeNode* rightChild;
-(instancetype) initWithData:(NSInteger) data;
@end
NS_ASSUME_NONNULL_END
- 創(chuàng)建一顆二叉樹代碼清單如下：
-(TreeNode*) createTree:(NSArray *)data{
TreeNode* p1 = [[TreeNode alloc] initWithData:1];
TreeNode* p2 = [[TreeNode alloc] initWithData:2];
TreeNode* p3 = [[TreeNode alloc] initWithData:3];
TreeNode* p4 = [[TreeNode alloc] initWithData:4];
TreeNode* p5 = [[TreeNode alloc] initWithData:5];
TreeNode* p6 = [[TreeNode alloc] initWithData:6];
TreeNode* p7 = [[TreeNode alloc] initWithData:7];
TreeNode* p8 = [[TreeNode alloc] initWithData:8];
TreeNode* p9 = [[TreeNode alloc] initWithData:9];
p1.leftChild = p2;
p1.rightChild = p3;
p2.leftChild = p4;
p2.rightChild = p5;
p3.leftChild = p6;
p3.rightChild = p7;
p4.leftChild = p8;
p4.rightChild = p9;
self.root = p1;
return p1;
}
對(duì)應(yīng)的樹抽象結(jié)構(gòu)為：
- 二叉樹的前序遍歷（遞歸）規(guī)則為：根陈醒，左，右
1.先訪問根結(jié)點(diǎn)瞧甩，如果有左孩子結(jié)點(diǎn)再訪問左孩子結(jié)點(diǎn)钉跷，如果有右孩子結(jié)點(diǎn)再訪問右孩子結(jié)點(diǎn)。
2.然后再把左孩子結(jié)點(diǎn)當(dāng)作根結(jié)點(diǎn)肚逸，重復(fù)一次步驟1爷辙。
3.再把右孩子結(jié)點(diǎn)當(dāng)作根結(jié)點(diǎn)，重復(fù)一次步驟1朦促。
4.直到當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)為止膝晾。
前序遍歷的結(jié)果為：1，2务冕，4血当，8，9洒疚，5歹颓，3，6油湖，7
*前序遍歷（遞歸方式）代碼為：
-(void) preOrder:(TreeNode *)root{
if (!root) {
return;
}
[self visitedNode:root];
if(root.leftChild){
[self preOrder:root.leftChild];
}
if(root.rightChild){
[self preOrder:root.rightChild];
}
}
- 前序遍歷(非遞歸借助棧實(shí)現(xiàn)）具體實(shí)現(xiàn)邏輯如下：
1.根結(jié)點(diǎn)入棧
2.while棧不為空時(shí)巍扛，取棧頂元素（假設(shè)為e）并訪問。判斷e是否有左孩子結(jié)點(diǎn)乏德，如果有則入棧撤奸，判斷e是否有右孩子結(jié)點(diǎn)吠昭，如果有則入棧。
- 前序遍歷(非遞歸借助棧實(shí)現(xiàn)）代碼清單為：
/// 非遞歸實(shí)現(xiàn)前序遍歷
/// @param root 根結(jié)點(diǎn)
-(void) iterativePreOrder:(TreeNode*) root{
if (!self.stack) {
self.stack = [[Stack alloc] initWithSize:100];
}
TreeNode* p = root;
if(p){
printf(" \n前序非遞歸遍歷的結(jié)果為:\n ");
[self.stack push:p];
while (![self.stack isEmpty]) {
p = (TreeNode*)[self.stack pop];
[self visitedNode:p];
if(p.rightChild){
[self.stack push:p.rightChild];
}
if(p.leftChild){
[self.stack push:p.leftChild];
}
}
}
}
- 二叉樹的中序遍歷（遞歸）規(guī)則為：左胧瓜，根矢棚，右
1.對(duì)樹中任一結(jié)點(diǎn)判斷當(dāng)前結(jié)點(diǎn)是否有左孩子，如果有左孩子府喳，繼續(xù)尋找蒲肋，直到當(dāng)前結(jié)點(diǎn)沒有左孩子為止才訪問。
2.訪問當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)钝满。
3.訪問當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)兜粘。
4.直到當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)為止。
中序遍歷的結(jié)果為：8弯蚜，4孔轴，9，5碎捺，2路鹰，1，6收厨，3晋柱，7
- 二叉樹的中序遍歷（遞歸）代碼為：
-(void) inOrder:(TreeNode *)root{
if (!root) {
return;
}
if(root.leftChild){
[self inOrder:root.leftChild];
}
[self visitedNode:root];
if(root.rightChild){
[self inOrder:root.rightChild];
}
}
- 二叉樹的中序遍歷（非遞歸)邏輯如下：
對(duì)于任一結(jié)點(diǎn)P，
1.若其左孩子不為空帽氓，則將P入棧并將P的左孩子置為當(dāng)前的P趣斤，然后對(duì)當(dāng)前結(jié)點(diǎn)P再進(jìn)行相同的處理俩块；
2.若其左孩子為空黎休，則取棧頂元素并進(jìn)行出棧操作，訪問該棧頂結(jié)點(diǎn)玉凯，然后將當(dāng)前的P置為棧頂結(jié)點(diǎn)的右孩子势腮；
3.直到P為nil或者棧為空則遍歷結(jié)束。
- 二叉樹的中序遍歷（非遞歸)代碼清單如下：
/// 非遞歸實(shí)現(xiàn)中序遍歷
/// @param root 根結(jié)點(diǎn)
-(void) iterativeInOrder:(TreeNode*) root{
if (!self.stack) {
self.stack = [[Stack alloc] initWithSize:100];
}
printf(" \n中序非遞歸遍歷的結(jié)果為:\n ");
TreeNode* p = root;
while (p || ![self.stack isEmpty]) {
while (p) {
[self.stack push:p];
p = p.leftChild;
}
if (![self.stack isEmpty]) {
p = (TreeNode*)[self.stack pop];
[self visitedNode:p];
p = p.rightChild;
}
}
}
- 二叉樹的后序遍歷（遞歸）規(guī)則為：左漫仆，右捎拯，根
1.對(duì)樹中任一結(jié)點(diǎn)判斷當(dāng)前結(jié)點(diǎn)是否有左孩子，如果有左孩子盲厌，繼續(xù)尋找署照，直到當(dāng)前結(jié)點(diǎn)沒有左孩子為止才訪問。
2.訪問當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)吗浩。
3.訪問當(dāng)前結(jié)點(diǎn)的父親結(jié)點(diǎn)建芙。
4.直到當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)為止。
后序遍歷的結(jié)果為：8懂扼，9禁荸，4右蒲，5，2赶熟，6瑰妄，7，3映砖，1
- 二叉樹的后序遍歷（遞歸）代碼清單：
-(void) postOrder:(TreeNode *)root{
if (!root) {
return;
}
if(root.leftChild){
[self postOrder:root.leftChild];
}
if(root.rightChild){
[self postOrder:root.rightChild];
}
[self visitedNode:root];
}
- 二叉樹的后序遍歷（非遞歸）邏輯：
1.要保證根結(jié)點(diǎn)在左孩子和右孩子訪問之后才能訪問间坐，因此對(duì)于任一結(jié)點(diǎn)P，先將其入棧邑退。如果P不存在左孩子和右孩子眶诈，則可以直接訪問它；
2.或者P存在左孩子或者右孩子瓜饥，但是其左孩子和右孩子都已被訪問過了逝撬，則同樣可以直接訪問該結(jié)點(diǎn)。若非上述兩種情況乓土，則將P的右孩子和左孩子依次入棧宪潮，這樣就保證了每次取棧頂元素的時(shí)候，左孩子在右孩子前面被訪問趣苏，左孩子和右孩子都在根結(jié)點(diǎn)前面被訪問狡相。
- 二叉樹的后序遍歷（非遞歸）代碼清單：
/// 非遞歸實(shí)現(xiàn)后序遍歷
/// @param root 根結(jié)點(diǎn)
-(void) iterativePostOrder:(TreeNode*) root{
if (!self.stack) {
self.stack = [[Stack alloc] initWithSize:100];
}
[self.stack push:root];
TreeNode* cur;
TreeNode* pre;
printf(" \n后序非遞歸遍歷的結(jié)果為:\n ");
while(![self.stack isEmpty]){
cur = (TreeNode*)[self.stack top];
//沒有孩子結(jié)點(diǎn)
BOOL noChild = !cur.leftChild && !cur.rightChild;
//通過判斷上一個(gè)結(jié)點(diǎn)是否為其中的一個(gè)孩子結(jié)點(diǎn)時(shí)，來判斷孩子結(jié)點(diǎn)是否都已經(jīng)被訪問過
//如果當(dāng)前結(jié)點(diǎn)存在左右孩子那么必須等它左右孩子都必需訪問之后才能訪問它
BOOL lastVisitedNode = pre && ([pre isEqual:cur.leftChild] || [pre isEqual: cur.rightChild]);
if (noChild || lastVisitedNode) {
[self visitedNode:cur];
[self.stack pop];
pre = cur;
}else{
if(cur.rightChild){
[self.stack push:cur.rightChild];
}
if(cur.leftChild){
[self.stack push:cur.leftChild];
}
}
}
}
-(void) visitedNode:(TreeNode*)node{
if (node) {
printf(" %ld ",node.value);
}
}
