二叉搜索树算法
① 数据结构与算法-二叉树(Binary Tree)
名词解释
节点: 每个元素
父子关系: 用来连线相邻节点之间的关系
父节点: A节点就是B节点的父节点
子节点: B节点就是A节点的子节点
兄弟节点: B、C、D这三个节点的父节点是同一个节点
根结点: 没有父节点的节点
叶子结点: 没有子节点的节点
节点的高度: 节点到叶子结点到最长路径(边数) (计数起点为0, 从下往上)
节点的深度: 根节点到这个节点经历过的边个数 (计数起点为0, 从上往下)
节点的层数: 节点到深度 + 1 (计数起点为1)
树的高度: 根节点的高度
特点
最常用的树数据结构
每个节点最多有两个子节点(左子节点、右子节点)
满二叉树: 叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
完全二叉树: 叶子节点都在最底下两层，最后一层的叶子节点都 靠左排列 ，并且除了最后一层，其他层的节点个数都要达到最大
二叉树存储方式
数组顺序存储法
通过数组下标来顺序存储数据 (i表示当前节点深度,从0开始)
根节点: i = 1，左节点:2 * i，右节点: 2 * i + 1，父节点: i / 2
完全二叉树采用此方式节省内存空间
链式存储法
每个节点需要存储三分数据:当前节点数据、左节点指针、右节点指针,比较占用空间
遍历
常用方式
前序遍历: 树任意节点，先打印当前节点，再打印它的左子树，最后打印它的右子树
中序遍历: 树任意节点，先打印它的左子树，再打印当前节点，最后打印它的右子树
后序遍历: 树任意节点，先打印它的左子树，再打印它的右子树，最后打印当前节点
二叉树的前、中、后序遍历就是一个递归的过程
时间复杂度是O(n)
每个节点最多被访问两次，遍历操作的时间复杂度跟节点的个数n成正比
特点
二叉查找树为实现快速查找而生，支持快速查找一个数据、快速插入、快速删除一个数据
特殊结构: 其左子树每个节点的值 < 树的任意一个节点的值 < 其右子树每个节点的值
先取根节点，如果它等于要查找的数据，那就返回。
如果要查找的数据比根节点的值小，那就在左子树中递归查找；
如果要查找的数据比根节点的值大，那就在右子树中递归查找
一般插入的数据在叶子节点上，从根节点开始依次比较要插入的数据和节点的大小关系
如果插入数据比节点的数值大，并且节点的右子树为空，将新数据插到右子节点位置；
如果不为空，就再递归遍历右子树，查找插入位置。
如果插入数据比节点的数值小，并且节点的左子树为空，将新数据插到左子节点位置；
如果不为空，就再递归遍历左子树，查找插入位置。
针对要删除节点的子节点个数的不同，需分三种情况来处理
1.如果要删除的节点没有子节点，步骤如下: (如图中的删除节点55)
只需将父节点中指向要删除节点的指针置为null
2.如果要删除的节点只有一个子节点，步骤如下: (如图中删除节点13)
只需将父节点中指向要删除节点的指针，让它指向要删除节点的子节点即可
3.如果要删除的节点有两个子节点，步骤如下: (如图中的删除节点18)
首先，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上；
然后，再删除掉这个最小节点，因为最小节点肯定没有左子节点
删除操作，有个优化方案: 就是单纯将要删除的节点标记为“已删除”，
这种方案删除操作就变简单很多，但是比较浪费内存空间
支持快速地查找最大节点和最小节点、前驱节点和后继节点
另外一种重要特性:
中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)
因此，二叉查找树也叫作二叉排序树
以上几种操作都默认树中节点存储的都是数字，而且都是不存在键值相同的情况
实际应用场景中采用对象的某个字段作为键值来构建二叉查找树，其他字段称为卫星数据
如果存储的两个对象键值相同，两种解决方案
1.把值相同的数据都存储在同一个节点(采用链表或支持动态扩容的数组等数据结构)
2.每个节点只存储一个数据，把这个新插入的数据当作大于这个节点的值来处理，如下图:
查找操作
当查找数据时遇到值相同的节点，继续在右子树中查找，直到遇到叶子节点才停止。
这样就把键值等于要查找值的所有节点都查找出来
删除操作
先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除
对于同一组数据可构造不同二叉查找树。查找、插入、删除操作的执行效率都不一样
图最左边树，根节点的左右子树极度不平衡，退化成链表，查找时间复杂度为O(n)
最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）
时间复杂度都跟树的高度成正比，也就是O(height)
树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示
满二叉树: 下一层节点个数是上一层的2倍，第K层包含节点个数就是2^(K-1)
完全二叉树: 假设最大层数是L，总的节点个数n，它包含的节点个数在1个到2^(L-1)个之间
L的范围是[ , +1]，完全二叉树的高度小于等于
极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求
平衡二叉查找树: 树的高度接近logn，时间复杂度较稳定为O(logn)
1.排序对比
散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序
二叉查找树只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列
2.性能稳定性对比
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定
最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)
3.时间复杂度对比
散列表查找等操作时间复杂度是常量级，因存在哈希冲突，这个常量不一定比logn小
另外加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高
4.结构设计对比
散列表构造比较复杂，需要考虑:散列函数设计、冲突解决办法、扩容、缩容等
平衡二叉查找树只需要考虑平衡性，而且目前这个的解决方案较成熟、固定
5.空间复杂度
散列表: 避免过多散列冲突，装载因子不能太大，特别基于开放寻址法，否则浪费太多空间
② 求个二叉排序树查找的递归算法
#include<iostream> #include<string> #include<cstring> using namespace std; class BinaryTreeNode {public: string data; int w; BinaryTreeNode *leftchild; BinaryTreeNode *rightchild; BinaryTreeNode *parent; int pos[50]; BinaryTreeNode(string a,int postion) { data=a; w=1; leftchild=NULL; rightchild=NULL; parent=NULL; pos[0]=postion; } }; class BSTree {public: BinaryTreeNode *root; BSTree(){root=NULL;} void Insert(string a,int postion); void Delete(string key); BinaryTreeNode *Search(string key,BinaryTreeNode*& pr,BinaryTreeNode *&parent); void InOrder(BinaryTreeNode *&root); void PreOrder(BinaryTreeNode *&root); }; void BSTree::InOrder(BinaryTreeNode *&root) { if(root) { InOrder(root->leftchild); cout<<root->data; cout<<" "<<root->w<<endl; InOrder(root->rightchild); } } void BSTree::PreOrder(BinaryTreeNode*& root) { if(root) { cout<<root->data; cout<<" "<<root->w<<endl; PreOrder(root->leftchild); PreOrder(root->rightchild); } } BinaryTreeNode *BSTree::Search(string key,BinaryTreeNode*& pr,BinaryTreeNode*& parents) { BinaryTreeNode *p=root; pr=root; while(p) { parents=p; if(key<p->data) { pr=p; p=p->leftchild; } else if(key>p->data) { pr=p; p=p->rightchild; } else return p; } return NULL; } void BSTree::Insert(string a,int postion) { BinaryTreeNode *pr,*p,*pp=NULL; p=Search(a,pr,pp); if(p!=NULL) { p->w++; p->pos[p->w-1]=postion; return; } BinaryTreeNode *r=new BinaryTreeNode(a,postion); if(!root) root=r; else if(a<pp->data) pp->leftchild=r; else pp->rightchild=r; } void BSTree::Delete(string key) { BinaryTreeNode *p,*pr,*pp; p=Search(key,pp,pr); if(p==NULL) return; if(p->leftchild&&p->rightchild) { BinaryTreeNode *s=p->rightchild,*ps=p; while(s->leftchild) { ps=s; s=s->leftchild; } p->data=s->data; p->w=s->w; for(int i=0;i<s->w;i++) { p->pos[i]=s->pos[i]; } pp=ps; p=s; } if(p->leftchild) { if(pp->leftchild==p) { pp->leftchild=p->leftchild; p->leftchild->parent=pp; } else { pp->rightchild=p->leftchild; p->leftchild->parent=pp; } } else if(p->rightchild) { if(pp->leftchild
③ 题目3． 平衡二叉树算法查找树中某节点的时间复杂度是多少
平均查找的时间复杂度为O(log n)。
平衡树的查找过程和排序树的相同。在查找过程中和给定值进行比较关键字个数不超过树的深度。
如果二叉树的元素个数为n，那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。
是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。
(3)二叉搜索树算法扩展阅读：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：
(1)空二叉树——(a)
(2)只有一个根结点的二叉树——(b);
(3)右子树为空的二叉树——(c);
(4)左子树为空的二叉树——(d);
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
④ 二叉树的深度算法怎么算啊
二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}