美文网首页技术
iOS之二叉树

iOS之二叉树

作者: NahuelK | 来源:发表于2017-03-17 11:18 被阅读624次

一.  二叉树的定义

二叉树(Binary Tree)是 n ( n >= 0) 个节点的有限集,这个集合可以为空,即是等于 0 的时候,也被称为空树。当然也有一个根结点和一个左子树以及二叉树组成的二叉树。每个根结点可以有 0 ,1,2 个孩子

二叉树

二. 创建二叉排序树

二叉树的左子树和右子树本来没有大小之分,就需要处理好左子树和右子树,如何做到终止左子树切换到右子树,所以二叉树是一个不错的选择,二叉排序树的左右子树有明确的要求,程序能够根据节点的大小进行自动排序

二叉树节点对象

采用单链表的形式,只从副节点指向子节点,不保存副节点。

@interfaceBinaryTreeNode :NSObject

/**

*值

*/

@property(nonatomic,assign)NSIntegervalue;

/**

*左节点

*/

@property(nonatomic,strong)BinaryTreeNode*leftNode;

/**

*右节点

*/

@property(nonatomic,strong)BinaryTreeNode*rightNode;

@end

创建二叉排序树

/**

*生成二叉树

*

* @param values数组

*

* @return二叉树

*/

+ (BinaryTreeNode*)createTreeWithValues:(NSArray*)values {

BinaryTreeNode*root =nil;

for(NSIntegeri=0; i

NSInteger value = [(NSNumber*)[values objectAtIndex: i ] integerValue ] ;

root = [[self class] addTreeNode : root value : value ];

}

NSLog(@"rootValue:%ld",root.value);

return root;

}

+ (BinaryTreeNode*)addTreeNode:(BinaryTreeNode*)treeNode value:(NSInteger)value {

//根节点不存在,创建节点

if ( ! treeNode ) {

treeNode = [ BinaryTreeNode new ];

treeNode.value= value;

NSLog(@"node:%@",@(value));

}

elseif(value <= treeNode.value) {

NSLog(@"to left");

//值小于根节点,则插入到左子树

treeNode.leftNode= [[selfclass]addTreeNode:treeNode.leftNodevalue:value];

} else {

NSLog(@"to right");

//值大于根节点,则插入到右子树

treeNode.rightNode= [[selfclass]addTreeNode:treeNode.rightNodevalue:value];

}

return treeNode;

}

计算二叉排序树的深度

///二叉树深度

+ (NSInteger)depathOfTree:(BinaryTreeNode *)rootNode{

if( ! rootNode ) return 0;

if( !rootNode.leftNode && !rootNode.rightNode ) return 1;

// 左子树的节点深度

NSInteger leftDepth = [self  depathOfTree: rootNode.leftNode];

//右子树的节点深度

NSInteger rightDepth = [self depathOfTree: rootNode.rightNode];

NSLog(@"%ld----%ld",leftDepth,rightDepth);

//取左子树和右子树的深度最大值计算二叉树的节点深度

return MAX ( leftDepth ,  rightDepth ) +1;

}

翻转二叉树

所谓翻转二叉树其实就是二叉树的镜像,也就是左子树和右子树的调换

/**

*翻转二叉树(非递归)

*

* @param rootNode根节点

*

* @return翻转后的树根节点(其实就是原二叉树的根节点)

*/

+ (BinaryTreeNode*)invertBinaryTreeWithoutRecursion:(BinaryTreeNode*)rootNode {

if ( ! rootNode ) { return  nil ;  }

if(!rootNode.leftNode &&  !rootNode.rightNode) {

return rootNode;

}

NSMutableArray* queueArray = [ NSMutableArray array ];//数组当成队列

[ queueArray addObject: rootNode ];//压入根节点

while( queueArray.count > 0) {

BinaryTreeNode* node = [queueArray firstObject];

[queueArray removeObjectAtIndex: 0];//弹出最前面的节点,仿照队列先进先出原则

BinaryTreeNode* pLeft = node.leftNode;

node.leftNode= node.rightNode;

node.rightNode= pLeft;

if ( node.leftNode ) {

[queueArray addObject: node.leftNode];

}

if(node.rightNode) {

[queueArray addObject:  node.rightNode];

}

}

return rootNode;

}

相关文章

网友评论

    本文标题:iOS之二叉树

    本文链接:https://www.haomeiwen.com/subject/hchenttx.html