一. 二叉树的定义
二叉树(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;
}
