什么是二叉樹急侥？
在計算機(jī)科學(xué)中执赡，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”和“右子樹”歇父，左子樹和右子樹同時也是二叉樹蒂培。二叉樹的子樹有左右之分，并且次序不能任意顛倒榜苫。二叉樹是遞歸定義的护戳，所以一般二叉樹的相關(guān)題目也都可以使用遞歸的思想來解決，當(dāng)然也有一些可以使用非遞歸的思想解決单刁，我下面列出的一些算法有些采用了遞歸灸异，有些是非遞歸的。
什么是二叉排序樹羔飞？
二叉排序樹又叫二叉查找樹或者二叉搜索樹肺樟，它首先是一個二叉樹，而且必須滿足下面的條件：
1）若左子樹不空逻淌，則左子樹上所有結(jié)點的值均小于它的根節(jié)點的值么伯；
2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
3）左卡儒、右子樹也分別為二叉排序樹
概念就介紹這么多田柔，都是來自網(wǎng)上，下面主要看算法和具體實現(xiàn)代碼骨望。
二叉樹節(jié)點定義：采用單項鏈表的形式硬爆，只從根節(jié)點指向孩子節(jié)點，不保存父節(jié)點擎鸠。
*? 二叉樹節(jié)點
*/@interfaceBinaryTreeNode : NSObject/**
*? 值
*/@property(nonatomic, assign) NSInteger value;/**
*? 左節(jié)點
*/@property(nonatomic, strong) BinaryTreeNode *leftNode;/**
*? 右節(jié)點
*/@property(nonatomic, strong) BinaryTreeNode *rightNode;
@end
創(chuàng)建二叉排序樹
二叉樹中左右節(jié)點值本身沒有大小之分缀磕，所以如果要創(chuàng)建二叉樹，就需要考慮如何處理某個節(jié)點是左節(jié)點還是右節(jié)點，如何終止某個子樹而切換到另一個子樹袜蚕。 因此我選擇了二叉排序樹糟把，二叉排序樹中對于左右節(jié)點有明確的要求，程序可以自動根據(jù)鍵值大小自動選擇是左節(jié)點還是右節(jié)點牲剃。
/** *? 創(chuàng)建二叉排序樹 *? 二叉排序樹：左節(jié)點值全部小于根節(jié)點值遣疯，右節(jié)點值全部大于根節(jié)點值 * *@paramvalues 數(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é)點 *
?*@paramtreeNode 根節(jié)點
?*@paramvalue值 *
?*@return根節(jié)點 */
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {//根節(jié)點不存在，創(chuàng)建節(jié)點
if(!treeNode) {
treeNode = [BinaryTreeNodenew];
treeNode.value = value;
NSLog(@"node:%@", @(value));
}elseif(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];
}
returntreeNode;
}
二叉樹中某個位置的節(jié)點
類似索引操作，按層次遍歷聪舒，位置從0開始算夭坪。
/** *? 二叉樹中某個位置的節(jié)點（按層次遍歷） *?
*@paramindex按層次遍歷樹時的位置(從0開始算)?
*@paramrootNode 樹根節(jié)點 *
?*@return節(jié)點 */
+ (BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode {//按層次遍歷if(!rootNode || index <0) {
returnnil;
}
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é)點，仿照隊列先進(jìn)先出原則index--;
//移除節(jié)點过椎，index減少
if(node.leftNode) {
[queueArray addObject:node.leftNode];//壓入左節(jié)點
}if(node.rightNode) {
[queueArray addObject:node.rightNode];//壓入右節(jié)點
}
}//層次遍歷完，仍然沒有找到位置戏仓，返回nil
return nil;
}
先序遍歷
先訪問根疚宇，再遍歷左子樹，再遍歷右子樹赏殃。典型的遞歸思想敷待。
/** *? 先序遍歷 *? 先訪問根，再遍歷左子樹仁热，再遍歷右子樹 *?
*@paramrootNode 根節(jié)點?
*@paramhandler? 訪問節(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];
}
}
NSMutableArray*orderArray= [NSMutableArray array];
[BinaryTree preOrderTraverseTree:root handler:^(BinaryTreeNode*treeNode) {??
? [orderArray addObject:@(treeNode.value)];
}];
NSLog(@"先序遍歷結(jié)果：%@", [orderArray componentsJoinedByString:@","]);
中序遍歷
先遍歷左子樹榜揖，再訪問根，再遍歷右子樹抗蠢。
對于二叉排序樹來說举哟，中序遍歷得到的序列是一個從小到大排序好的序列。
/** *? 中序遍歷 *? 先遍歷左子樹迅矛，再訪問根，再遍歷右子樹 *?
*@paramrootNode 根節(jié)點?
*@paramhandler? 訪問節(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];
}
}
后序遍歷
先遍歷左子樹，再遍歷右子樹咬腕，再訪問根
/** *? 后序遍歷 *? 先遍歷左子樹徒探，再遍歷右子樹，再訪問根 *
?*@paramrootNode 根節(jié)點?
*@paramhandler? 訪問節(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);
}
}}
層次遍歷
按照從上到下销斟、從左到右的次序進(jìn)行遍歷庐椒。先遍歷完一層，再遍歷下一層蚂踊，因此又叫廣度優(yōu)先遍歷约谈。需要用到隊列，在OC里可以用可變數(shù)組來實現(xiàn)。
/** *? 層次遍歷（廣度優(yōu)先） *
?*@paramrootNode 二叉樹根節(jié)點?
*@paramhandler? 訪問節(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é)點窗宇，仿照隊列先進(jìn)先出原則
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
/** *? 二叉樹的深度 *
?*@paramrootNode 二叉樹根節(jié)點 *?
*@return二叉樹的深度 */
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode {
if(!rootNode) {
return0;}
if(!rootNode.leftNode && !rootNode.rightNode) {
return1;}//左子樹深度
NSInteger leftDepth = [self depthOfTree:rootNode.leftNode];
//右子樹深度
NSInteger rightDepth = [self depthOfTree:rootNode.rightNode];
returnMAX(leftDepth, rightDepth) +1;}
二叉樹的寬度
二叉樹的寬度定義為各層節(jié)點數(shù)的最大值粪躬。
/** *? 二叉樹的寬度 *?
*@paramrootNode 二叉樹根節(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é)點，仿照隊列先進(jìn)先出原則
//壓入子節(jié)點
if(node.leftNode) {
[queueArray addObject:node.leftNode];
}
if(node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
//寬度 = 當(dāng)前層節(jié)點數(shù)
maxWidth = MAX(maxWidth, queueArray.count);
}returnmaxWidth;
