二叉树是一种每个节点最好有左右两个子节点的树结构。概念的东西就不倒腾了。意思意思就好。
算法之中，对于二叉树类的问题 一般使用递归的思想去解它。
二叉排序树／二叉查找树／二叉搜索树 这三者都是一个东西，是一种特殊的二叉树，它满足下面几个条件：
1.若左子树不为空 那么左子树的所有节点都小于根节点
2.若右子树不为空 那么右子树的所有节点都大于根节点
3.左右子树分别又是二叉搜索树
4.整个树结构中 没有键值相等的两个节点
二叉树类的定义（oc 版）
@interface BTNode : NSObject
@Property (nonatomic, assign) NSInteger value; //值
@property (nonatomic, strong) BTNode *left; //左子节点
@property (nonatomic, strong) BTNode *right; //右子节点
@end
二叉树的创建
/**
- 创建二叉排序树
- 二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
- @param values 数组
- @return 二叉树根节点
*/
-
(BinaryTreeNode *)createTreeWithValues:(NSArray *)values {
BinaryTreeNode *root = nil;
for (NSInteger i=0; i<values.count; i++) {
NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
root = [BinaryTree addTreeNode:root value:value];
}
return root;
}
/**
- 向二叉排序树节点添加一个节点
- @param treeNode 根节点
- @param value 值
- @return 根节点
*/
-
(BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {
//根节点不存在，创建节点
if (!treeNode) {
treeNode = [BinaryTreeNode new];
treeNode.value = value;
NSLog(@"node:%@", @(value));
}
else if (value <= treeNode.value) {
NSLog(@"to left");
//值小于根节点，则插入到左子树
treeNode.leftNode = [BinaryTree addTreeNode:treeNode.leftNode value:value];
}
else {
NSLog(@"to right");
//值大于根节点，则插入到右子树
treeNode.rightNode = [BinaryTree addTreeNode:treeNode.rightNode value:value];
}return treeNode;
}
