一、二叉搜索树-Binary Search Tree
它是二叉树中的一种，是使用最广泛的一种，英文缩写为BST
又称之为：二叉查找树、二叉排序树
二、特点
1.任意一个节点的值都大于其左子树所有节点的值
2.任意一个节点的值都小于其右子树所有节点的值
3.它的左右子树也是一棵二叉搜索树
二叉搜索树存储的元素 必须具备可比较性
如：int 、double等
自定义类型需 指定比较方式
不允许为null
三、二叉树的遍历
1.前序遍历 ： 先访问根结点
2.中序遍历 ： 中间访问根结点
3.后序遍历 ： 最后访问根结点
4.层序遍历 ：
前序遍历 Preorder Traversal
首先访问根结点，再访问左子树，然后再访问右子树。子树将以同样的规则访问。
前序遍历顺序.png
通过递归的方式实现
// 前序遍历
-(void)preorderTraversal{
[self preorderTraversal:self.root];
}
-(void)preorderTraversal:(Node *)node{
// 1.node 为空的时候，退出
if (node == nil) return;
// 2.前序遍历，首先访问根结点
NSLog(@"%@",node.element);
// 3.再访问左结点
[self preorderTraversal:node.left];// 递归，进入步骤1，遍历子结点
// 4.在访问右结点
[self preorderTraversal:node.right];// 同样进入步骤1，遍历子结点
}
中序遍历
首先遍历左子树，然后访问根结点，最后遍历右子树
中序遍历.png
中序遍历
如果先访问左子树，在访问根结点，最后访问右子树的顺序，进行遍历，那么遍历的结果是升序。
如果先访问右子树，再访问根结点，最后访问左子树的顺序，进行遍历，那么遍历的结果过升序。
-(void)inorderTraversal{
[self inorderTraversal:self.root];
}
-(void)inorderTraversal:(Node *)node{
if (node == nil) return;
[self inorderTraversal:node.left];
NSLog(@"%@",node.element);
[self inorderTraversal:node.right];
}
后序遍历
首先访问左子树，然后访问右子树，最后访问根结点
后序遍历.png
-(void)postorderTraversal:(Node *)node{
if (node == nil) return;
[self postorderTraversal:node.left];
[self postorderTraversal:node.right];
NSLog(@"%@",node.element);
}
层序遍历
从上到下，从左到右依次访问每一个结点
层序遍历.png
1.利用队列
首先访问根结点，将根结点入队
然后依次判断是否具有左右子结点，如果具有，将子结点入队
将根结点出队
循环以上步骤，直到队列为空
2.利用数组
首先访问根结点，将根结点插入数组中
然后依次判断是否具有左右子结点，如果具有，插入子结点
然后移除根结点
循环以上步骤，直到数组为空
/// 层序遍历
-(void)levelOrderTraversal{
if(self.root == nil) return;
/// 1.先将根结点入队
NSMutableArray *mArray = [NSMutableArray array];
[mArray addObject:self.root];
while (mArray.count != 0) {
Node *node = mArray.firstObject;
[mArray removeObjectAtIndex:0];
// 2.访问结点
NSLog(@"%@",node.element);
// 3.查看是否具有左右子结点
if (node.left != nil) {
[mArray addObject:node.left];
}
if (node.right != nil) {
[mArray addObject:node.right];
}
}
}
练习-翻转二叉树
image.png
输入: [4,2,7,1,3,6,9]
输出 : [4,7,2,9,6,3,1]
前序遍历 翻转二叉树
-(Node *)inverTree:(Node*)root{
if (root == nil) {
return nil;
}
Node *tempNode = root.left;
root.left = root.right;
root.right = tempNode;
[self inverTree:root.left];
[self inverTree:root.right];
return root;
}
后序遍历翻转二叉树
-(Node *)inverTree2:(Node *)root{
if (root == nil) {
return nil;
}
[self inverTree2:root.left];
[self inverTree2:root.right];
Node *tempNode = root.left;
root.left = root.right;
root.right = tempNode;
return root;
}
中序遍历翻转二叉树
-(Node *)inverTree3:(Node *)root{
if (root == nil) {
return nil;
}
[self inverTree3:root.left];
Node *tempNode = root.left;
root.left = root.right;
root.right = tempNode;
[self inverTree3:root.left];
return root;
}
层序遍历翻转二叉树
-(Node *)inverTree4:(Node *)root{
if (root == nil) {
return nil;
}
NSMutableArray *queue = [NSMutableArray array];
[queue addObject:root];
while (queue.count != 0) {
Node *node = queue.firstObject;
Node *tempNode = node.left;
node.left = node.right;
node.right = tempNode;
[queue removeObjectAtIndex:0];
if (node.left != nil) {
[queue addObject:node.left];
}
if (node.right != nil) {
[queue addObject:node.right];
}
}
return root;
}
