什么是二叉樹急侥?
在計算機(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;