這幾天詳細了解了下二叉樹的相關(guān)算法，原因是看了唐boy的一篇博客（你會翻轉(zhuǎn)二叉樹嗎？），還有一篇關(guān)于百度的校園招聘面試經(jīng)歷，深刻體會到二叉樹的重要性。于是乎，從網(wǎng)上收集并整理了一些關(guān)于二叉樹的資料，及相關(guān)算法的實現(xiàn)（主要是Objective-C的，但是算法思想是相通的），以便以后復(fù)習(xí)時查閱。
在計算機科學(xué)中，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”和“右子樹”，左子樹和右子樹同時也是二叉樹。二叉樹的子樹有左右之分，并且次序不能任意顛倒。二叉樹是遞歸定義的，所以一般二叉樹的相關(guān)題目也都可以使用遞歸的思想來解決，當(dāng)然也有一些可以使用非遞歸的思想解決，我下面列出的一些算法有些采用了遞歸，有些是非遞歸的。
二叉排序樹又叫二叉查找樹或者二叉搜索樹，它首先是一個二叉樹，而且必須滿足下面的條件：
1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根節(jié)點的值；
2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
3）左、右子樹也分別為二叉排序樹
4）沒有鍵值相等的節(jié)點（？可能是因為不好處理鍵值相等的節(jié)點到底是左節(jié)點還是右節(jié)點吧）
概念就介紹這么多，都是來自網(wǎng)上，下面主要看算法和具體實現(xiàn)代碼。
采用單項鏈表的形式，只從根節(jié)點指向孩子節(jié)點，不保存父節(jié)點。
/** * 二叉樹節(jié)點 */@interface BinaryTreeNode : NSObject/** * 值 */@PRoperty (nonatomic, assign) NSInteger value;/** * 左節(jié)點 */@property (nonatomic, strong) BinaryTreeNode *leftNode;/** * 右節(jié)點 */@property (nonatomic, strong) BinaryTreeNode *rightNode;@end
二叉樹中左右節(jié)點值本身沒有大小之分，所以如果要創(chuàng)建二叉樹，就需要考慮如何處理某個節(jié)點是左節(jié)點還是右節(jié)點，如何終止某個子樹而切換到另一個子樹。 因此我選擇了二叉排序樹，二叉排序樹中對于左右節(jié)點有明確的要求，程序可以自動根據(jù)鍵值大小自動選擇是左節(jié)點還是右節(jié)點。
/** * 創(chuàng)建二叉排序樹 * 二叉排序樹：左節(jié)點值全部小于根節(jié)點值，右節(jié)點值全部大于根節(jié)點值 * * @param values 數(shù)組 * * @return 二叉樹根節(jié)點 */+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values { BinaryTreeNode *root = nil; for (NSInteger i=0; i<values.count; i++) { NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue]; root = [BinaryTree addTreeNode:root value:value]; } return root;}/** * 向二叉排序樹節(jié)點添加一個節(jié)點 * * @param treeNode 根節(jié)點 * @param value 值 * * @return 根節(jié)點 */+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value { //根節(jié)點不存在，創(chuàng)建節(jié)點 if (!treeNode) { treeNode = [BinaryTreeNode new]; treeNode.value = value; NSLog(@"node:%@", @(value)); } else if (value <= treeNode.value) { NSLog(@"to left"); //值小于根節(jié)點，則插入到左子樹 treeNode.leftNode = [BinaryTree addTreeNode:treeNode.leftNode value:value]; } else { NSLog(@"to right"); //值大于根節(jié)點，則插入到右子樹 treeNode.rightNode = [BinaryTree addTreeNode:treeNode.rightNode value:value]; } return treeNode;}
類似索引操作，按層次遍歷，位置從0開始算。
/** * 二叉樹中某個位置的節(jié)點（按層次遍歷） * * @param index 按層次遍歷樹時的位置(從0開始算) * @param rootNode 樹根節(jié)點 * * @return 節(jié)點 */+ (BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode { //按層次遍歷 if (!rootNode || index < 0) { return nil; } NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊列 [queueArray addObject:rootNode]; //壓入根節(jié)點 while (queueArray.count > 0) { BinaryTreeNode *node = [queueArray firstObject]; if (index == 0) { return node; } [queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點，仿照隊列先進先出原則 index--; //移除節(jié)點，index減少 if (node.leftNode) { [queueArray addObject:node.leftNode]; //壓入左節(jié)點 } if (node.rightNode) { [queueArray addObject:node.rightNode]; //壓入右節(jié)點 } } //層次遍歷完，仍然沒有找到位置，返回nil return nil;}
先訪問根，再遍歷左子樹，再遍歷右子樹。典型的遞歸思想。
/** * 先序遍歷 * 先訪問根，再遍歷左子樹，再遍歷右子樹 * * @param rootNode 根節(jié)點 * @param handler 訪問節(jié)點處理函數(shù) */+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler { if (rootNode) { if (handler) { handler(rootNode); } [self preOrderTraverseTree:rootNode.leftNode handler:handler]; [self preOrderTraverseTree:rootNode.rightNode handler:handler]; }}
調(diào)用方法如下：（用到了block）
NSMutableArray *orderArray = [NSMutableArray array];[BinaryTree preOrderTraverseTree:root handler:^(BinaryTreeNode *treeNode) { [orderArray addObject:@(treeNode.value)];}];NSLog(@"先序遍歷結(jié)果：%@", [orderArray componentsJoinedByString:@","]);
先遍歷左子樹，再訪問根，再遍歷右子樹。
對于二叉排序樹來說，中序遍歷得到的序列是一個從小到大排序好的序列。
/** * 中序遍歷 * 先遍歷左子樹，再訪問根，再遍歷右子樹 * * @param rootNode 根節(jié)點 * @param handler 訪問節(jié)點處理函數(shù) */+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler { if (rootNode) { [self inOrderTraverseTree:rootNode.leftNode handler:handler]; if (handler) { handler(rootNode); } [self inOrderTraverseTree:rootNode.rightNode handler:handler]; }}
先遍歷左子樹，再遍歷右子樹，再訪問根
/** * 后序遍歷 * 先遍歷左子樹，再遍歷右子樹，再訪問根 * * @param rootNode 根節(jié)點 * @param handler 訪問節(jié)點處理函數(shù) */+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler { if (rootNode) { [self postOrderTraverseTree:rootNode.leftNode handler:handler]; [self postOrderTraverseTree:rootNode.rightNode handler:handler]; if (handler) { handler(rootNode); } }}
按照從上到下、從左到右的次序進行遍歷。先遍歷完一層，再遍歷下一層，因此又叫廣度優(yōu)先遍歷。需要用到隊列，在OC里可以用可變數(shù)組來實現(xiàn)。
/** * 層次遍歷（廣度優(yōu)先） * * @param rootNode 二叉樹根節(jié)點 * @param handler 訪問節(jié)點處理函數(shù) */+ (void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler { if (!rootNode) { return; } NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊列 [queueArray addObject:rootNode]; //壓入根節(jié)點 while (queueArray.count > 0) { BinaryTreeNode *node = [queueArray firstObject]; if (handler) { handler(node); } [queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點，仿照隊列先進先出原則 if (node.leftNode) { [queueArray addObject:node.leftNode]; //壓入左節(jié)點 } if (node.rightNode) { [queueArray addObject:node.rightNode]; //壓入右節(jié)點 } }}
二叉樹的深度定義為：從根節(jié)點到葉子結(jié)點依次經(jīng)過的結(jié)點形成樹的一條路徑,最長路徑的長度為樹的深度。
1）如果根節(jié)點為空，則深度為0；
2）如果左右節(jié)點都是空，則深度為1；
3）遞歸思想：二叉樹的深度=max（左子樹的深度，右子樹的深度）+ 1
/** * 二叉樹的深度 * * @param rootNode 二叉樹根節(jié)點 * * @return 二叉樹的深度 */+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return 0; } if (!rootNode.leftNode && !rootNode.rightNode) { return 1; } //左子樹深度 NSInteger leftDepth = [self depthOfTree:rootNode.leftNode]; //右子樹深度 NSInteger rightDepth = [self depthOfTree:rootNode.rightNode]; return MAX(leftDepth, rightDepth) + 1;}
二叉樹的寬度定義為各層節(jié)點數(shù)的最大值。
/** * 二叉樹的寬度 * * @param rootNode 二叉樹根節(jié)點 * * @return 二叉樹寬度 */+ (NSInteger)widthOfTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return 0; } NSMutableArray *queueArray = [NSMutableArray array]; //數(shù)組當(dāng)成隊列 [queueArray addObject:rootNode]; //壓入根節(jié)點 NSInteger maxWidth = 1; //最大的寬度，初始化為1（因為已經(jīng)有根節(jié)點） NSInteger curWidth = 0; //當(dāng)前層的寬度 while (queueArray.count > 0) { curWidth = queueArray.count; //依次彈出當(dāng)前層的節(jié)點 for (NSInteger i=0; i<curWidth; i++) { BinaryTreeNode *node = [queueArray firstObject]; [queueArray removeObjectAtIndex:0]; //彈出最前面的節(jié)點，仿照隊列先進先出原則 //壓入子節(jié)點 if (node.leftNode) { [queueArray addObject:node.leftNode]; } if (node.rightNode) { [queueArray addObject:node.rightNode]; } } //寬度 = 當(dāng)前層節(jié)點數(shù) maxWidth = MAX(maxWidth, queueArray.count); } return maxWidth;}
遞歸思想：二叉樹所有節(jié)點數(shù)=左子樹節(jié)點數(shù)+右子樹節(jié)點數(shù)+1
/** * 二叉樹的所有節(jié)點數(shù) * * @param rootNode 根節(jié)點 * * @return 所有節(jié)點數(shù) */+ (NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return 0; } //節(jié)點數(shù)=左子樹節(jié)點數(shù)+右子樹節(jié)點數(shù)+1（根節(jié)點） return [self numberOfNodesInTree:rootNode.leftNode] + [self numberOfNodesInTree:rootNode.rightNode] + 1;}
1）根節(jié)點為空，則節(jié)點數(shù)為0；
2）層為1，則節(jié)點數(shù)為1（即根節(jié)點）
3）遞歸思想：二叉樹第k層節(jié)點數(shù)=左子樹第k-1層節(jié)點數(shù)+右子樹第k-1層節(jié)點數(shù)
/** * 二叉樹某層中的節(jié)點數(shù) * * @param level 層 * @param rootNode 根節(jié)點 * * @return 層中的節(jié)點數(shù) */+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(BinaryTreeNode *)rootNode { if (!rootNode || level < 1) { //根節(jié)點不存在或者level<0 return 0; } if (level == 1) { //level=1，返回1（根節(jié)點） return 1; } //遞歸：level層節(jié)點數(shù) = 左子樹level-1層節(jié)點數(shù)+右子樹level-1層節(jié)點數(shù) return [self numberOfNodesOnLevel:level-1 inTree:rootNode.leftNode] + [self numberOfNodesOnLevel:level-1 inTree:rootNode.rightNode];}
葉子節(jié)點，又叫終端節(jié)點，是左右子樹都是空的節(jié)點。
/** * 二叉樹葉子節(jié)點數(shù) * * @param rootNode 根節(jié)點 * * @return 葉子節(jié)點數(shù) */+ (NSInteger)numberOfLeafsInTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return 0; } //左子樹和右子樹都是空，說明是葉子節(jié)點 if (!rootNode.leftNode && !rootNode.rightNode) { return 1; } //遞歸：葉子數(shù) = 左子樹葉子數(shù) + 右子樹葉子數(shù) return [self numberOfLeafsInTree:rootNode.leftNode] + [self numberOfLeafsInTree:rootNode.rightNode];}
二叉樹中任意兩個節(jié)點都有且僅有一條路徑，這個路徑的長度叫這兩個節(jié)點的距離。二叉樹中所有節(jié)點之間的距離的最大值就是二叉樹的直徑。
有一種解法，把這個最大距離劃分了3種情況：
1）這2個節(jié)點分別在根節(jié)點的左子樹和右子樹上，他們之間的路徑肯定經(jīng)過根節(jié)點，而且他們肯定是根節(jié)點左右子樹上最遠的葉子節(jié)點（他們到根節(jié)點的距離=左右子樹的深度）。
2）這2個節(jié)點都在左子樹上
3）這2個節(jié)點都在右子樹上
綜上，只要取這3種情況中的最大值，就是二叉樹的直徑。
/** * 二叉樹最大距離（直徑） * * @param rootNode 根節(jié)點 * * @return 最大距離 */+ (NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return 0; }// 方案一：（遞歸次數(shù)較多，效率較低） //分3種情況： //1、最遠距離經(jīng)過根節(jié)點：距離 = 左子樹深度 + 右子樹深度 NSInteger distance = [self depthOfTree:rootNode.leftNode] + [self depthOfTree:rootNode.rightNode]; //2、最遠距離在根節(jié)點左子樹上，即計算左子樹最遠距離 NSInteger disLeft = [self maxDistanceOfTree:rootNode.leftNode]; //3、最遠距離在根節(jié)點右子樹上，即計算右子樹最遠距離 NSInteger disRight = [self maxDistanceOfTree:rootNode.rightNode]; return MAX(MAX(disLeft, disRight), distance);}
這個方案效率較低，因為計算子樹的深度和最遠距離是分開遞歸的，存在重復(fù)遞歸遍歷的情況。其實一次遞歸，就可以分別計算出深度和最遠距離，于是有了第二種方案：
/** * 二叉樹最大距離（直徑） * * @param rootNode 根節(jié)點 * * @return 最大距離 */+ (NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return 0; }// 方案2：將計算節(jié)點深度和最大距離放到一次遞歸中計算，方案一是分別單獨遞歸計算深度和最遠距離 TreeNodeProperty *p = [self propertyOfTreeNode:rootNode]; return p.distance;}/** * 計算樹節(jié)點的最大深度和最大距離 * * @param rootNode 根節(jié)點 * * @return TreeNodeProperty */+ (TreeNodeProperty *)propertyOfTreeNode:(BinaryTreeNode *)rootNode { if (!rootNode) { return nil; } TreeNodeProperty *left = [self propertyOfTreeNode:rootNode.leftNode]; TreeNodeProperty *right = [self propertyOfTreeNode:rootNode.rightNode]; TreeNodeProperty *p = [TreeNodeProperty new]; //節(jié)點的深度depth = 左子樹深度、右子樹深度中最大值+1（+1是因為根節(jié)點占了1個depth） p.depth = MAX(left.depth, right.depth) + 1; //最遠距離 = 左子樹最遠距離、右子樹最遠距離和橫跨左右子樹最遠距離中最大值 p.distance = MAX(MAX(left.distance, right.distance), left.depth+right.depth); return p;}
既是尋路問題，又是查找節(jié)點問題。
定義一個存放路徑的棧（不是隊列了，但是還是用可變數(shù)組來實現(xiàn)的）
1）壓入根節(jié)點，再從左子樹中查找（遞歸進行的），如果未找到，再從右子樹中查找，如果也未找到，則彈出根節(jié)點，再遍歷棧中上一個節(jié)點。
2）如果找到，則棧中存放的節(jié)點就是路徑所經(jīng)過的節(jié)點。
/** * 二叉樹中某個節(jié)點到根節(jié)點的路徑 * * @param treeNode 節(jié)點 * @param rootNode 根節(jié)點 * * @return 存放路徑節(jié)點的數(shù)組 */+ (NSArray *)pathOfTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode { NSMutableArray *pathArray = [NSMutableArray array]; [self isFoundTreeNode:treeNode inTree:rootNode routePath:pathArray]; return pathArray;}/** * 查找某個節(jié)點是否在樹中 * * @param treeNode 待查找的節(jié)點 * @param rootNode 根節(jié)點 * @param path 根節(jié)點到待查找節(jié)點的路徑 * * @return YES：找到，NO：未找到 */+ (BOOL)isFoundTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode routePath:(NSMutableArray *)path { if (!rootNode || !treeNode) { return NO; } //找到節(jié)點 if (rootNode == treeNode) { [path addObject:rootNode]; return YES; } //壓入根節(jié)點，進行遞歸 [path addObject:rootNode]; //先從左子樹中查找 BOOL find = [self isFoundTreeNode:treeNode inTree:rootNode.leftNode routePath:path]; //未找到，再從右子樹查找 if (!find) { find = [self isFoundTreeNode:treeNode inTree:rootNode.rightNode routePath:path]; } //如果2邊都沒查找到，則彈出此根節(jié)點 if (!find) { [path removeLastObject]; } return find;}
首先需要明白，根節(jié)點肯定是二叉樹中任意兩個節(jié)點的公共父節(jié)點（不一定是最近的），因此二叉樹中2個節(jié)點的最近公共父節(jié)點一定在從根節(jié)點到這個節(jié)點的路徑上。因此我們可以先分別找到從根節(jié)點到這2個節(jié)點的路徑，再從這兩個路徑中找到最近的公共父節(jié)點。
/** * 二叉樹中兩個節(jié)點最近的公共父節(jié)點 * * @param nodeA 第一個節(jié)點 * @param nodeB 第二個節(jié)點 * @param rootNode 二叉樹根節(jié)點 * * @return 最近的公共父節(jié)點 */+ (BinaryTreeNode *)parentOfNode:(BinaryTreeNode *)nodeA andNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode { if (!rootNode || !nodeA || !nodeB) { return nil; } if (nodeA == nodeB) { return nodeA; } //從根節(jié)點到節(jié)點A的路徑 NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode]; //從根節(jié)點到節(jié)點B的路徑 NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode]; //其中一個節(jié)點不在樹中，則沒有公共父節(jié)點 if (pathA.count == 0 || pathB == 0) { return nil; } //從后往前推，查找第一個出現(xiàn)的公共節(jié)點 for (NSInteger i = pathA.count-1; i>=0; i--) { for (NSInteger j = pathB.count - 1; j>=0; j--) { if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) { //找到 return [pathA objectAtIndex:i]; } } } return nil;}
從查找最近公共父節(jié)點衍生出來的。
/** * 二叉樹中兩個節(jié)點之間的路徑 * * @param nodeA 第一個節(jié)點 * @param nodeB 第二個節(jié)點 * @param rootNode 二叉樹根節(jié)點 * * @return 兩個節(jié)點間的路徑 */+ (NSArray *)pathFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode { if (!rootNode || !nodeA || !nodeB) { return nil; } NSMutableArray *path = [NSMutableArray array]; if (nodeA == nodeB) { [path addObject:nodeA]; [path addObject:nodeB]; return path; } //從根節(jié)點到節(jié)點A的路徑 NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode]; //從根節(jié)點到節(jié)點B的路徑 NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode]; //其中一個節(jié)點不在樹中，則沒有路徑 if (pathA.count == 0 || pathB == 0) { return nil; } //從后往前推，查找第一個出現(xiàn)的公共節(jié)點 for (NSInteger i = pathA.count-1; i>=0; i--) { [path addObject:[pathA objectAtIndex:i]]; for (NSInteger j = pathB.count - 1; j>=0; j--) { //找到公共父節(jié)點，則將pathB中后面的節(jié)點壓入path if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) { j++; //j++是為了避開公共父節(jié)點 while (j<pathB.count) { [path addObject:[pathB objectAtIndex:j]]; j++; } return path; } } } return nil;}
可以從兩個節(jié)點之間的路徑衍生出來。
/** * 二叉樹兩個節(jié)點之間的距離 * * @param nodeA 第一個節(jié)點 * @param nodeB 第二個節(jié)點 * @param rootNode 二叉樹根節(jié)點 * * @return 兩個節(jié)點間的距離（-1：表示沒有找到路徑） */+ (NSInteger)distanceFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode { if (!rootNode || !nodeA || !nodeB) { return -1; } if (nodeA == nodeB) { return 0; } //從根節(jié)點到節(jié)點A的路徑 NSArray *pathA = [self pathOfTreeNode:nodeA inTree:rootNode]; //從根節(jié)點到節(jié)點B的路徑 NSArray *pathB = [self pathOfTreeNode:nodeB inTree:rootNode]; //其中一個節(jié)點不在樹中，則沒有路徑 if (pathA.count == 0 || pathB == 0) { return -1; } //從后往前推，查找第一個出現(xiàn)的公共節(jié)點 for (NSInteger i = pathA.count-1; i>=0; i--) { for (NSInteger j = pathB.count - 1; j>=0; j--) { //找到公共父節(jié)點 if ([pathA objectAtIndex:i] == [pathB objectAtIndex:j]) { //距離=路徑節(jié)點數(shù)-1 （這里要-2，因為公共父節(jié)點重復(fù)了一次） return (pathA.count - i) + (pathB.count - j) - 2; } } } return -1;}
你會翻轉(zhuǎn)二叉樹嗎？如果不會，那對不起，我們不會錄用你！
翻轉(zhuǎn)二叉樹，又叫求二叉樹的鏡像，就是把二叉樹的左右子樹對調(diào)（當(dāng)然是遞歸的）
/** * 翻轉(zhuǎn)二叉樹（又叫：二叉樹的鏡像） * * @param rootNode 根節(jié)點 * * @return 翻轉(zhuǎn)后的樹根節(jié)點（其實就是原二叉樹的根節(jié)點） */+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return nil; } if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; } [self invertBinaryTree:rootNode.leftNode]; [self invertBinaryTree:rootNode.rightNode]; BinaryTreeNode *tempNode = rootNode.leftNode; rootNode.leftNode = rootNode.rightNode; rootNode.rightNode = tempNode; return rootNode;}
完全二叉樹定義為：若設(shè)二叉樹的高度為h，除第h層外，其它各層的結(jié)點數(shù)都達到最大個數(shù)，第h層有葉子結(jié)點，并且葉子結(jié)點都是從左到右依次排布。
完全二叉樹必須滿足2個條件：
1）如果某個節(jié)點的右子樹不為空，則它的左子樹必須不為空
2）如果某個節(jié)點的右子樹為空，則排在它后面的節(jié)點必須沒有孩子節(jié)點
這里還需要理解“排在它后面的節(jié)點”，回頭看看層次遍歷算法，我們就能知道在層次遍歷時，是從上到下從左到右遍歷的，先將根節(jié)點彈出隊列，再壓入孩子節(jié)點，因此“排在它后面的節(jié)點”有2種情況：
1）同層次的后面的節(jié)點
2）同層次的前面的節(jié)點的孩子節(jié)點（因為遍歷前面的節(jié)點時，會彈出節(jié)點，同時將孩子節(jié)點壓入隊列）
通過上面的分析，我們可以設(shè)置一個標(biāo)志位flag，當(dāng)子樹滿足完全二叉樹時，設(shè)置flag=YES。當(dāng)flag=YES而節(jié)點又破壞了完全二叉樹的條件，那么它就不是完全二叉樹。
/** * 是否完全二叉樹 * 完全二叉樹：若設(shè)二叉樹的高度為h，除第h層外，其它各層的結(jié)點數(shù)都達到最大個數(shù)，第h層有葉子結(jié)點，并且葉子結(jié)點都是從左到右依次排布 * * @param rootNode 根節(jié)點 * * @return YES：是完全二叉樹，NO：不是完全二叉樹 */+ (BOOL)isCompleteBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return NO; } //左子樹和右子樹都是空，則是完全二叉樹 if (!rootNode.leftNode && !rootNode.rightNode) { return YES; } //左子樹是空，右子樹不是空，則不是完全二叉樹 if (!rootNode.leftNode && rootNode.rightNode) { return NO; } //按層次遍歷節(jié)點，找到滿足完全二叉樹的條件： //條件1：如果某個節(jié)點的右子樹不為空，則它的左子樹必須不為空 //條件2：如果某個節(jié)點的右子樹為空，則排在它后面的節(jié)點必須沒有孩子節(jié)點 //排在該節(jié)點后面的節(jié)點有2種：1）同層次的后面的節(jié)點 2）同層次的前面的節(jié)點的孩子節(jié)點（因為遍歷前面的節(jié)點的時候，會將節(jié)點從隊列里pop，同時把它的孩子節(jié)點push到隊列里） NSMutableArray *queue = [NSMutableArray array]; [queue addObject:rootNode]; BOOL isComplete = NO; //是否已經(jīng)滿足完全二叉樹 while (queue.count > 0) { BinaryTreeNode *node = [queue firstObject]; [queue removeObjectAtIndex:0]; //左子樹為空且右子樹不為空，則不是完全二叉樹 if (!node.leftNode && node.rightNode) { return NO; } if (isComplete && (node.leftNode || node.rightNode)) { //前面的節(jié)點已滿足完全二叉樹,如果還有孩子節(jié)點，則不是完全二叉樹 return NO; } //右子樹為空，則已經(jīng)滿足完全二叉樹 if (!node.rightNode) { isComplete = YES; } //壓入 if (node.leftNode) { [queue addObject:node.leftNode]; } if (node.rightNode) { [queue addObject:node.rightNode]; } } return isComplete;}
滿二叉樹定義為：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹
滿二叉樹的一個特性是：葉子數(shù)=2^(深度-1)，因此我們可以根據(jù)這個特性來判斷二叉樹是否是滿二叉樹。
/** * 是否滿二叉樹 * 滿二叉樹：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹 * * @param rootNode 根節(jié)點 * * @return YES：滿二叉樹，NO：非滿二叉樹 */+ (BOOL)isFullBinaryTree:(BinaryTreeNode *)rootNode { if (!rootNode) { return NO; } //二叉樹深度 NSInteger depth = [self depthOfTree:rootNode]; //二叉樹葉子節(jié)點數(shù) NSInteger leafNum = [self numberOfLeafsInTree:rootNode]; //滿二叉樹特性：葉子數(shù)=2^(深度-1) if (leafNum == pow(2, (depth - 1))) { return YES; } return NO;}
平衡二叉樹定義為：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹又叫AVL樹。
/** * 是否平衡二叉樹 * 平衡二叉樹：即AVL樹，它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹 * * @param rootNode 根節(jié)點 * * @return YES：平衡二叉樹，NO：非平衡二叉樹 */+ (BOOL)isAVLBinaryTree:(BinaryTreeNode *)rootNode { static NSInteger height; if (!rootNode) { height = 0; return YES; } if (!rootNode.leftNode && !rootNode.rightNode) { height = 1; return YES; } BOOL isAVLLeft = [self isAVLBinaryTree:rootNode.leftNode]; NSInteger heightLeft = height; BOOL isAVLRight = [self isAVLBinaryTree:rootNode.rightNode]; NSInteger heightRight = height; height = MAX(heightLeft, heightRight)+1; if (isAVLLeft && isAVLRight && ABS(heightLeft-heightRight) <= 1) { return YES; } return NO;}
以上就是我目前整理的一些二叉樹相關(guān)的算法，算法資料和思想都來源于網(wǎng)絡(luò)，如有錯誤，歡迎指正！后續(xù)如果有新的算法，我也會更新進去。
新聞熱點
疑難解答
