什么是二叉树这里就不介绍了，直接看代码，有value和左右子树共三个属性
@interfaceOCBinaryTree :NSObject
@property (nonatomic, assign) NSInteger value;
@property (nonatomic, strong) OCBinaryTree * leftTree;
@property (nonatomic, strong) OCBinaryTree * rightTree;
这里是用OC和swift实现一些二叉树的基本功能：
- (NSInteger)depth; //深度
- (NSInteger)length; //所有节点的个数
- (NSInteger)maxLength;//满二叉树所有节点数
- (void)print; //打印基本信息
- (void)BFSPrint; //广度优先遍历:Breadth First Search
- (void)prePrint; //先序遍历
- (void)midPrint; //中序遍历
- (void)sufPrint; //后序遍历
- (void)prePrintWithoutRecursion; //非递归先序遍历
- (void)midPrintWithoutRecursion; //非递归中序遍历
- (void)sufPrintWithoutRecursion; //非递归后序遍历
- (void)sufPrintWithoutRecursionAndParam; //非递归后序遍历不带isFirst参数
- (void)reverse; //反转二叉树
+ (instancetype)createWithArray:(NSArray*)array;
首先是创建二叉树，这里就简单使用一个无序随机数组,来创建二叉排序树。
什么是二叉排序树？
意思就是左子树只要不为空，它的值及其所有子树的值都小于其根结点的值。右子树则相反。(直接上图片了，代码地址在末尾)
从二叉树的特性，很容易看出，二叉树很适合用递归算法，上方代码也就是用递归来实现创建二叉树
递归是二叉树里很常用的算法，比如二叉树的一些定义:深度，宽度，所有节点数等都可以用地归来很简单地实现
还有就是三种深度优先遍历方式：先序遍历，中序遍历，后序遍历
先序遍历：以根->左->右的顺序来遍历二叉树
中序遍历：以左->根->右的顺序来遍历二叉树
后序遍历：以左->右->根的顺序来遍历二叉树
用递归算法很简单就能实现
那么不用递归该如何实现呢？底层的实现方法是利用栈的先进后出的特性来实现的。对应的在ios里，可以用可变数组来实现。
中序遍历和先序遍历类似。比较麻烦的是后序遍历，须引入一个preTree参数来记录上次遍历的树，还有一种方法是给二叉树添加一个isFirst属性来记录是否是第一次访问，这种方法更麻烦，这里就不介绍了
其次还有广度优先遍历方式，也就是层次遍历：从根结点开始沿着树的宽度一层一层依次遍历,这里用非递归方式很简单就可以实现
以上对遍历的处理只是简单的打印，如果要做其他的处理，函数传入处理的block，将打印换成block即可。
反转二叉树:即将二叉树的左右子树交换一下，用递归可以很简单地实现
上边说的深度，宽度包括这里的反转二叉树同样也可以用和遍历一样，用非递归的方式实现，这里就不再说了。
创建好二叉树之后，就可以将其绘制到屏幕上
因绘制需要，给二叉树对象扩展了两个属性:number,height
number就是编号的意思，以最上层结点为参照在满二叉树下从左到右的编号
height就是以最上层结点为参照该结点的层级
然后就是统一为其设置值，因为要参照根节点，所以这里就不能使用递归了
func setValues() {
let treeArray = NSMutableArray()
self.number= (self.maxLength() +1)/2
self.height = self.depth()
var tree: BinaryTree? = self
while(tree !=nil || treeArray.count > 0) {
while tree != nil {
treeArray.add(tree!)
if tree!.leftTree != nil {
tree!.leftTree!.height = tree!.height -1
tree!.leftTree!.number = tree!.number-Int(pow(2.0,CGFloat(tree!.height-2)))
}
tree = tree!.leftTree
}
if treeArray.count > 0{
tree = (treeArray.lastObject as! BinaryTree)
if tree!.rightTree != nil {
tree!.rightTree!.height= tree!.height-1
tree!.rightTree!.number= tree!.number+Int(pow(2.0,CGFloat(tree!.height-2)))
}
tree = tree!.rightTree
treeArray.removeLastObject()
}
}
}
绘制也是使用递归的方式依次绘制每个节点并连线。
首先根据上方扩展的属性来计算每个节点在屏幕上的位置
func getPoint(tree: BinaryTree) -> CGPoint {
let pointY =CGFloat(tree.number)*eachWidth!
let pointX =CGFloat(tree.height)*eachHeight!
return CGPoint(x: pointX, y: pointY)
}
这里的eachWidth和eachHeight是根据树的满二叉树的总结点数和深度计算的，radius则是结点半径，这里是统一为10
eachWidth = (viewHeight! - radius*2)/CGFloat(tree.maxLength())
eachHeight= (Screen_width() -radius*2)/CGFloat(tree.depth())
然后遍历整棵树用递归的方法来连线，这里连线顺序同样分为前序、中序、后序三种方式。并加上动画，来演示遍历顺序
连线用的是UIBezierPath类
动画用的是CABasicAnimation，演示5秒
然后就是加上每个节点，同样用递归的方式，这里直接用的是UILabel，来显示每个值
效果如下：
网友评论