二叉排序树
/*
二叉排序树的查找：
函数返回指向关键字为key结点的指针，如果没有，返回NULL
p指向被查找结点的双亲，方便用来进行插入和删除操作
*/
理解：
1.p为什么可以用来方便插入操作？
原因：如果想插入关键值为key的结点，
在调用这个函数之后，若函数返回值不为NULL，不需要进行插入操作（这个值已存在）；
若函数返回值为NULL，那么这个值应该插入在结点*p的下面
（左右子树根据key和p->data进行判断）
2.为什么可以方便进行删除操作？
原因：已找到待删除结点的父节点
BSTNode* BST_Search(BiTree T, ElemType key, BSTNode *&p)
{
BSTNode *p = NULL;
while (T != NULL && T->data != key) {
p = T;
if (T->data < key)
T = T->rchild;
else
T = T->lchild;
}
return T;
}
/*
二叉排序树的插入
*/
算法思想：
1.若原二叉排序树为NULL,则直接插入结点
2.若关键字小余根节点关键词，那么插入左子树
3.若关键字小余根节点关键字，那么插入右子树
eg.新插入的节点一个是一个叶子节点
bool BST_Insert(BiTree &T, KeyType key)
{
if (T == NULL) {
T = (BSTNode*)malloc(sizeof(BSTNode));
T->key = key;
T->lchild = T->rchild = NULL;
return true;
}
else if (T->key == key)
return false;
else if (key < T->key)
return BST_Insert(T->lchild);
else
return BST_Insert(T->rchild);
}
eg.这里自己理解的时候有一个误区，就是如果传入一个NULL，
那么T=(BiTree)malloc(sizeof(BSTNode))是不是没有用呢？
注意：这里是使用引用传参数，就是传入的是地址，这里的赋值操作相当于是
把对一个结点的引用写入到这个地址当中，是计算机系统基础里面的知识
（因此调用此函数的时候，传入的参数一定是变量，不应该是常量！！）
/*二叉树的构造*/
算法思想：依次输入数据元素，并将它们插入到二叉树适当位置上的过程
void Creat_BST(BiTree &T, KeyType A[], int n)
{
T = NULL;
int i = 0;
for (int i = 0; i < n; i++)
BST_Insert(T,A[i]);
}
eg.调用Create_BST时候，第一个参数一定要是变量！！
/*二叉排序树的删除*/
1.若被删除的结点是叶子结点，直接删除
2.若被删除的结点*p只有左子树或者只有右子树，则让*p的子树成为*p双亲结点的子树
3.若被删除的结点*p有左右子树，则可以让*p的“直接前驱”或者“直接后继”代替*p,并且删除*p,
之后就可以转换成1或者2的情况。
那么为什么可以转换成1，2的情况呢？因为直接前驱和直接后继一定都不是双分支节点，呃呃呃呃
这里寻找一个满足中序遍历有序的BST的前驱和后继非常的方便
补充知识
补充知识
二叉排序树的效率分析：
1.高度为H的BST，插入和删除的时间复杂度是O（H）
2.BST的平均查找长度，主要取决于二叉树的形态
3.若BST是一个只有左孩子和右孩子的单分支树，平均查找长度为O(n);
若BST是左右子树高度差不超过1，平均查找长度O(logn)
4.二分查找的判定树唯一，而二叉排序树不唯一，相同的关键词插入顺序不同，树的形态不同
5.对于一个正常的二叉排序树，插入，删除不需要移动节点，时间复杂度O（logn）
对于二分查找，因为是使用顺序表存储，插入删除需要移动节点，时间复杂度为O（n）
6.有序表是静态查找表：使用顺序表
有序表是动态查找表：使用BST
那么啥是红黑树呢？
红黑树简介
平衡二叉树
四个方法，只要熟悉了中序线索二叉树的前驱后继，看懂没有问题：LL,RR,LR,RL
1.每次调整最小不平衡子树
2.这里要有一种观点，就是把一个二叉排序树的子树当成一个结点理解，这里是可以的。
image.png
image.png
image.png
image.png
/*平衡二叉树的查找*/
Nh表示深度为h的平衡二叉树的最少结点数:
Nh=N（h-1）+N(h-2)+1
N0=0,N1=1,N2=2
eg.计算给定结点数的平衡二叉树的最多比较次数！！！
哈夫曼树
wpl最小的二叉树
特点：
1.n个初始结点都成为了叶子结点，权值小的结点到根结点的路径最长
2.新建n-1个结点，共计2n-1个结点
3.不存在度为1的结点
