一.? 二叉樹的定義
二叉樹(Binary Tree)是 n ( n >= 0) 個(gè)節(jié)點(diǎn)的有限集贱鼻，這個(gè)集合可以為空，即是等于 0 的時(shí)候，也被稱為空樹壤蚜。當(dāng)然也有一個(gè)根結(jié)點(diǎn)和一個(gè)左子樹以及二叉樹組成的二叉樹。每個(gè)根結(jié)點(diǎn)可以有 0 徊哑，1袜刷，2 個(gè)孩子
二. 創(chuàng)建二叉排序樹
二叉樹的左子樹和右子樹本來沒有大小之分，就需要處理好左子樹和右子樹莺丑，如何做到終止左子樹切換到右子樹著蟹，所以二叉樹是一個(gè)不錯(cuò)的選擇，二叉排序樹的左右子樹有明確的要求梢莽，程序能夠根據(jù)節(jié)點(diǎn)的大小進(jìn)行自動(dòng)排序
二叉樹節(jié)點(diǎn)對(duì)象
采用單鏈表的形式萧豆，只從副節(jié)點(diǎn)指向子節(jié)點(diǎn)，不保存副節(jié)點(diǎn)蟹漓。
@interfaceBinaryTreeNode :NSObject
/**
*值
*/
@property(nonatomic,assign)NSIntegervalue;
/**
*左節(jié)點(diǎn)
*/
@property(nonatomic,strong)BinaryTreeNode*leftNode;
/**
*右節(jié)點(diǎn)
*/
@property(nonatomic,strong)BinaryTreeNode*rightNode;
@end
創(chuàng)建二叉排序樹
/**
*生成二叉樹
*
* @param values數(shù)組
*
* @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 {
//根節(jié)點(diǎn)不存在炕横，創(chuàng)建節(jié)點(diǎn)
if ( ! treeNode ) {
treeNode = [ BinaryTreeNode new ];
treeNode.value= value;
NSLog(@"node:%@",@(value));
}
elseif(value <= treeNode.value) {
NSLog(@"to left");
//值小于根節(jié)點(diǎn)，則插入到左子樹
treeNode.leftNode= [[selfclass]addTreeNode:treeNode.leftNodevalue:value];
} else {
NSLog(@"to right");
//值大于根節(jié)點(diǎn)葡粒，則插入到右子樹
treeNode.rightNode= [[selfclass]addTreeNode:treeNode.rightNodevalue:value];
}
return treeNode;
}
計(jì)算二叉排序樹的深度
///二叉樹深度
+ (NSInteger)depathOfTree:(BinaryTreeNode *)rootNode{
if( ! rootNode ) return 0;
if( !rootNode.leftNode && !rootNode.rightNode ) return 1;
// 左子樹的節(jié)點(diǎn)深度
NSInteger leftDepth = [self ?depathOfTree: rootNode.leftNode];
//右子樹的節(jié)點(diǎn)深度
NSInteger rightDepth = [self depathOfTree: rootNode.rightNode];
NSLog(@"%ld----%ld",leftDepth,rightDepth);
//取左子樹和右子樹的深度最大值計(jì)算二叉樹的節(jié)點(diǎn)深度
return MAX ( leftDepth , ?rightDepth ) +1;
}
翻轉(zhuǎn)二叉樹
所謂翻轉(zhuǎn)二叉樹其實(shí)就是二叉樹的鏡像份殿，也就是左子樹和右子樹的調(diào)換
/**
*翻轉(zhuǎn)二叉樹（非遞歸）
*
* @param rootNode根節(jié)點(diǎn)
*
* @return翻轉(zhuǎn)后的樹根節(jié)點(diǎn)（其實(shí)就是原二叉樹的根節(jié)點(diǎn)）
*/
+ (BinaryTreeNode*)invertBinaryTreeWithoutRecursion:(BinaryTreeNode*)rootNode {
if ( ! rootNode ) { return ?nil ; ?}
if(!rootNode.leftNode && ?!rootNode.rightNode) {
return rootNode;
}
NSMutableArray* queueArray = [ NSMutableArray array ];//數(shù)組當(dāng)成隊(duì)列
[ queueArray addObject: rootNode ];//壓入根節(jié)點(diǎn)
while( queueArray.count > 0) {
BinaryTreeNode* node = [queueArray firstObject];
[queueArray removeObjectAtIndex: 0];//彈出最前面的節(jié)點(diǎn)，仿照隊(duì)列先進(jìn)先出原則
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;
}
