什么是二叉樹這里就不介紹了脖卖，直接看代碼融柬，有value和左右子樹共三個屬性????
@interfaceOCBinaryTree :NSObject?
@property (nonatomic, assign) NSInteger value;
@property (nonatomic, strong) OCBinaryTree * leftTree;
@property (nonatomic, strong) OCBinaryTree * rightTree;
這里是用OC和swift實現(xiàn)一些二叉樹的基本功能：
- (NSInteger)depth;? ? //深度
- (NSInteger)length;? //所有節(jié)點的個數(shù)
- (NSInteger)maxLength;//滿二叉樹所有節(jié)點數(shù)
- (void)print;? ? ? //打印基本信息
- (void)BFSPrint;? ? //廣度優(yōu)先遍歷:Breadth First Search
- (void)prePrint;? ? //先序遍歷
- (void)midPrint;? ? //中序遍歷
- (void)sufPrint;? ? //后序遍歷
- (void)prePrintWithoutRecursion;? ? ? ? ? //非遞歸先序遍歷
- (void)midPrintWithoutRecursion;? ? ? ? ? //非遞歸中序遍歷
- (void)sufPrintWithoutRecursion;? ? ? ? ? //非遞歸后序遍歷
- (void)sufPrintWithoutRecursionAndParam;? //非遞歸后序遍歷不帶isFirst參數(shù)
- (void)reverse;? ? //反轉(zhuǎn)二叉樹
+ (instancetype)createWithArray:(NSArray*)array;
首先是創(chuàng)建二叉樹，這里就簡單使用一個無序隨機數(shù)組,來創(chuàng)建二叉排序樹难捌。
什么是二叉排序樹？
意思就是左子樹只要不為空，它的值及其所有子樹的值都小于其根結(jié)點的值驻债。右子樹則相反。(直接上圖片了形葬，代碼地址在末尾)
從二叉樹的特性合呐，很容易看出，二叉樹很適合用遞歸算法荷并，上方代碼也就是用遞歸來實現(xiàn)創(chuàng)建二叉樹
遞歸是二叉樹里很常用的算法合砂，比如二叉樹的一些定義:深度，寬度源织，所有節(jié)點數(shù)等都可以用地歸來很簡單地實現(xiàn)
還有就是三種深度優(yōu)先遍歷方式：先序遍歷翩伪，中序遍歷，后序遍歷
先序遍歷：以根->左->右的順序來遍歷二叉樹
中序遍歷：以左->根->右的順序來遍歷二叉樹
后序遍歷：以左->右->根的順序來遍歷二叉樹
用遞歸算法很簡單就能實現(xiàn)
那么不用遞歸該如何實現(xiàn)呢谈息？底層的實現(xiàn)方法是利用棧的先進(jìn)后出的特性來實現(xiàn)的缘屹。對應(yīng)的在ios里，可以用可變數(shù)組來實現(xiàn)侠仇。
中序遍歷和先序遍歷類似轻姿。比較麻煩的是后序遍歷，須引入一個preTree參數(shù)來記錄上次遍歷的樹逻炊，還有一種方法是給二叉樹添加一個isFirst屬性來記錄是否是第一次訪問互亮，這種方法更麻煩，這里就不介紹了
其次還有廣度優(yōu)先遍歷方式余素，也就是層次遍歷：從根結(jié)點開始沿著樹的寬度一層一層依次遍歷,這里用非遞歸方式很簡單就可以實現(xiàn)
以上對遍歷的處理只是簡單的打印豹休，如果要做其他的處理，函數(shù)傳入處理的block桨吊，將打印換成block即可威根。
反轉(zhuǎn)二叉樹:即將二叉樹的左右子樹交換一下，用遞歸可以很簡單地實現(xiàn)
上邊說的深度视乐，寬度包括這里的反轉(zhuǎn)二叉樹同樣也可以用和遍歷一樣洛搀，用非遞歸的方式實現(xiàn)，這里就不再說了佑淀。
創(chuàng)建好二叉樹之后留美，就可以將其繪制到屏幕上
因繪制需要，給二叉樹對象擴展了兩個屬性:number,height
number就是編號的意思，以最上層結(jié)點為參照在滿二叉樹下從左到右的編號
height就是以最上層結(jié)點為參照該結(jié)點的層級? ??
然后就是統(tǒng)一為其設(shè)置值独榴，因為要參照根節(jié)點僧叉，所以這里就不能使用遞歸了
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()
? ? ? ? ? ? }
? ? ? ? }
? }
繪制也是使用遞歸的方式依次繪制每個節(jié)點并連線。
首先根據(jù)上方擴展的屬性來計算每個節(jié)點在屏幕上的位置
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是根據(jù)樹的滿二叉樹的總結(jié)點數(shù)和深度計算的棺榔，radius則是結(jié)點半徑瓶堕，這里是統(tǒng)一為10
????????eachWidth = (viewHeight! - radius*2)/CGFloat(tree.maxLength())
? ? ? ? eachHeight= (Screen_width() -radius*2)/CGFloat(tree.depth())
然后遍歷整棵樹用遞歸的方法來連線，這里連線順序同樣分為前序症歇、中序郎笆、后序三種方式。并加上動畫忘晤，來演示遍歷順序
連線用的是UIBezierPath類
動畫用的是CABasicAnimation宛蚓，演示5秒
然后就是加上每個節(jié)點，同樣用遞歸的方式设塔，這里直接用的是UILabel凄吏，來顯示每個值
效果如下：
