iOS_算法之二叉树
什么是二叉树？
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次序不能任意颠倒。二叉树是递归定义的，所以一般二叉树的相关题目也都可以使用递归的思想来解决，当然也有一些可以使用非递归的思想解决，我下面列出的一些算法有些采用了递归，有些是非递归的。
什么是二叉排序树？
二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：
1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
3）左、右子树也分别为二叉排序树
概念就介绍这么多，都是来自网上，下面主要看算法和具体实现代码。
二叉树节点定义：采用单项链表的形式，只从根节点指向孩子节点，不保存父节点。
* 二叉树节点
*/@interfaceBinaryTreeNode : NSObject/**
* 值
*/@property(nonatomic, assign) NSInteger value;/**
* 左节点
*/@property(nonatomic, strong) BinaryTreeNode *leftNode;/**
* 右节点
*/@property(nonatomic, strong) BinaryTreeNode *rightNode;
@end
创建二叉排序树
二叉树中左右节点值本身没有大小之分，所以如果要创建二叉树，就需要考虑如何处理某个节点是左节点还是右节点，如何终止某个子树而切换到另一个子树。 因此我选择了二叉排序树，二叉排序树中对于左右节点有明确的要求，程序可以自动根据键值大小自动选择是左节点还是右节点。
/** * 创建二叉排序树 * 二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值 * *@paramvalues 数组 * *@return二叉树根节点 */
+ (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;
}
/** * 向二叉排序树节点添加一个节点 *
*@paramtreeNode 根节点
*@paramvalue值 *
*@return根节点 */
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {//根节点不存在，创建节点
if(!treeNode) {
treeNode = [BinaryTreeNodenew];
treeNode.value = value;
NSLog(@"node:%@", @(value));
}elseif(value <= treeNode.value) {
NSLog(@"to left");//值小于根节点，则插入到左子树
treeNode.leftNode = [BinaryTree addTreeNode:treeNode.leftNode value:value];
}else{
NSLog(@"to right");//值大于根节点，则插入到右子树
treeNode.rightNode = [BinaryTree addTreeNode:treeNode.rightNode value:value];
}
returntreeNode;
}
二叉树中某个位置的节点
类似索引操作，按层次遍历，位置从0开始算。
/** * 二叉树中某个位置的节点（按层次遍历） *
*@paramindex按层次遍历树时的位置(从0开始算)
*@paramrootNode 树根节点 *
*@return节点 */
+ (BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode {//按层次遍历if(!rootNode || index <0) {
returnnil;
}
NSMutableArray *queueArray = [NSMutableArray array];
//数组当成队列[queueArray addObject:rootNode];
//压入根节点
while(queueArray.count >0) {
BinaryTreeNode *node = [queueArray firstObject];
if(index ==0) {
return node;
}
[queueArray removeObjectAtIndex:0];
//弹出最前面的节点，仿照队列先进先出原则index--;
//移除节点，index减少
if(node.leftNode) {
[queueArray addObject:node.leftNode];//压入左节点
}if(node.rightNode) {
[queueArray addObject:node.rightNode];//压入右节点
}
}//层次遍历完，仍然没有找到位置，返回nil
return nil;
}
先序遍历
先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
/** * 先序遍历 * 先访问根，再遍历左子树，再遍历右子树 *
*@paramrootNode 根节点
*@paramhandler 访问节点处理函数 */
+ (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(@"先序遍历结果：%@", [orderArray componentsJoinedByString:@","]);
中序遍历
先遍历左子树，再访问根，再遍历右子树。
对于二叉排序树来说，中序遍历得到的序列是一个从小到大排序好的序列。
/** * 中序遍历 * 先遍历左子树，再访问根，再遍历右子树 *
*@paramrootNode 根节点
*@paramhandler 访问节点处理函数 */
+ (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 根节点
*@paramhandler 访问节点处理函数 */
+ (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);
}
}}
层次遍历
按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层，因此又叫广度优先遍历。需要用到队列，在OC里可以用可变数组来实现。
/** * 层次遍历（广度优先） *
*@paramrootNode 二叉树根节点
*@paramhandler 访问节点处理函数 */
+ (void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
if(!rootNode) {
return;}
NSMutableArray *queueArray = [NSMutableArray array];//数组当成队列
[queueArray addObject:rootNode];//压入根节点
while(queueArray.count >0) {
BinaryTreeNode *node = [queueArray firstObject];
if(handler) {
handler(node);}
[queueArray removeObjectAtIndex:0];//弹出最前面的节点，仿照队列先进先出原则
if(node.leftNode) {
[queueArray addObject:node.leftNode];//压入左节点
}
if(node.rightNode) {
[queueArray addObject:node.rightNode];//压入右节点
}
}}
二叉树的深度
二叉树的深度定义为：从根节点到叶子结点依次经过的结点形成树的一条路径,最长路径的长度为树的深度
1）如果根节点为空，则深度为0；
2）如果左右节点都是空，则深度为1；
3）递归思想：二叉树的深度=max（左子树的深度，右子树的深度）+ 1
/** * 二叉树的深度 *
*@paramrootNode 二叉树根节点 *
*@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;}
二叉树的宽度
二叉树的宽度定义为各层节点数的最大值。
/** * 二叉树的宽度 *
*@paramrootNode 二叉树根节点 *
*@return二叉树宽度 */
+ (NSInteger)widthOfTree:(BinaryTreeNode *)rootNode {
if(!rootNode) {
return 0;
}
NSMutableArray *queueArray = [NSMutableArray array];
//数组当成队列
[queueArray addObject:rootNode];
//压入根节点NSInteger maxWidth =1;
//最大的宽度，初始化为1（因为已经有根节点）
NSInteger curWidth =0;
//当前层的宽度
while(queueArray.count >0) {
curWidth = queueArray.count;
//依次弹出当前层的节点
for(NSInteger i=0; i<curWidth;i++){
BinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0];
//弹出最前面的节点，仿照队列先进先出原则
//压入子节点
if(node.leftNode) {
[queueArray addObject:node.leftNode];
}
if(node.rightNode) {
[queueArray addObject:node.rightNode];
}
}
//宽度 = 当前层节点数
maxWidth = MAX(maxWidth, queueArray.count);
}returnmaxWidth;
