# 查找题解

续更，考虑第一版没有分题干，这次开始做就分题干，另外加入一些题目的衍生题目和知识点，顺便是造福自己和读者吧。

写的太差，可能也没人看，😭😭😭😭，自己看

# 1. 找最小值

行高亮

/*
描述
给出 n 和 n 个整数 ai，求这 n 个整数中最小值是什么。
输入
第一行输入一个正整数 n，表示数字个数。
第二行输入 n 个非负整数，表示 a1,a2…an，以空格隔开。
*/
//简单的查找，时间复杂度是n，一边输入一边比较
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int input = 0;
	int tmp = 0;
	int ans = 0;

	cin >> ans;

	while (ans > 0) {
		cin >> input;
		if (input < tmp)tmp = input;
		ans--;
	}
	cout << tmp << endl;
	return 0;
}

# 2. 查找（折半查找）

C 算法 —— 折半查找_c 折半查找 - CSDN 博客

可以学一下这篇帖子，讲的还行，本题一开始采用循环的折半查找，读者也可以尝试递归。

但本题数据特殊，考虑存在相同数字的情况，作者设计了一个很妙的算法。（有点投机）

行高亮

/*
2: 查找
描述
输入 n(n≤106) 个不超过 109的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an ，然后进行 m(m≤105
) 次询问。对于每次询问，给出一个整数 q(q≤109)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

输入
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出
m 个整数表示答案。

样例
输入

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出

1 2 -1
*/
/*
1.既然是做题目，暴力查找就不考虑了。
2.题目条件，单调递增，考虑折半查找，顺带复习一下喽
3.，每个查找时间是log2n
*/
#include <iostream>
#include <vector>
using namespace std;

int BinarySearch(vector<int> a, int lenth, int target)//折半查找
{
    int low = 0;
    int high = lenth - 1;
    while (low <= high)
    {
        int mid = low + (high - low);
        if (a[mid] > target)
            high = mid - 1;
        else if (a[mid] < target)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

int main_1() {
    int n,m;
    cin >> n>>m;
    vector<int> input;

    while (n-- > 0) {
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }

    while (m-- > 0) {
        int Ask;
        cin >> Ask;
        cout << BinarySearch(input, input.size(), Ask) << ' ';
    }
    cout << endl;
	return 0;
}

//出现了一些问题，考虑到可能存在相同，因此上述这个只适合完全递增
//考虑题目，输入 n(n≤106) 个不超过 109的单调不减的（就是后面的数字不小于前面的数字）非负整数
//开一个Bool数组，记录1到109的数字是否出现过，没出现就是-1，出现过的置为它第一次出现的位置
int main() {
    int output[109];
    for (int i = 0; i < 109; i++) {
        output[i] = -1;
    }
    int n, m;
    cin >> n >> m;

    int ans = 0;
    while (ans++ < n) {
        int input;
        cin >> input;
        if (output[input] == -1) output[input] = ans;
    }
    while (m-- > 0) {
        int input;
        cin >> input;
        cout << output[input] << " ";
    }
    cout << endl;
    return 0;	
}

# 3.A-B 数对（map 库的引入）

开始写了一个暴力查找的优化，但室友提到用 map 库，很爽，花了一点时间学了一下

map 优势如下：

1.map 类似于数组，比如数组 s [1], 但 map 可以让这里的数字 1 为任何索引，比如 s ['a'],s [10000],s [-1], 等等

2.map 函数本质是二叉树，红黑树，查找效率为 log2n，很方便

3. 因此，在建立好索引后，我们可以采用第 2 题的思想来做

行高亮

/*
3: A-B数对
描述
给出一串单调不下降的数以及一个数字 C，要求计算出所有A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入
输入共两行。
第一行，两个整数 N,C。
第二行，N个整数，作为要求处理的那串数。
输出
一行，表示该串数中包含的满足A−B=C 的数对的个数。
样例
输入
4 1
1 1 2 3
输出
3
*/
/*
注意题目：单调不下降
简单想法，暴力查找
细想：
取A为最大，遍历B从最小，那么当A下降的时候，此时的B只能从小于B的里面找，可以将时间复杂度大大降低
*/
#include <iostream>
#include <vector>
using namespace std;

//暴力算法的稍微优化版本
int numA_B(vector<int>input, int C)
{
	int num = 0;
	int B_max = input.size() - 1;
	for (int i = input.size() - 1; i > -1; i--) {
		int A = input[i];
		//cout<<"A的值：" << A << endl;//调试
		if (A - input[0] < 0) {
			break;
		}
		for (int j = B_max; j > -1; j--) {
			int B = input[j];
			//cout << "B的值：" << B << " j的值：" << j<<  endl;//调试
			if (A - B == C) {
				num++;
				if (j != input.size() - 1 && B != input[j + 1]) {
					B_max = j;//点睛之笔，每次去优化它的B_max
				}
			}   
		}
	}
	return num;
}

int main_1() {
	int n, C;
	cin >> n >> C;
	vector<int>input;
	while (n-- > 0) {
		int a;
		cin >> a;
		input.push_back(a);
	} 
	int result = numA_B(input, C);
	cout << result << endl;
	return 0;
}

//引入map包的优化，nlog2n
//思想类似于第二题

//map<frist(键)，second（映射）>
//map内部是红黑树，自动排序
//map根据键去找映射
#include <iostream>
#include <map>

typedef struct ref {
	int num;//出现次数
	//int fp;
} reflect;//定义映射

int main() {
	int n = 0, C = 0;
	int Num = 0;
	std::cin >> n >> C;
	std::map<int, reflect> maps;
	int seq[3000] = { 0 };                //seq命名，代表seq是间距的

	
	for (int i = 0; i < n; ++i) {
		std::cin >> seq[i];//输入键Key的值，键之间可以重复输值进去
		++maps[seq[i]].num;//一旦有这个数输入，我就将它的map容器中对应的元素的num值加1
		//maps[seq[i]].fp = i;//更新该元素的fp为当前位置
	}

	for (int i = 0; i < n; ++i) {//查找，这里外面是n，里面是log2n，故总共是nlog2n
		Num += maps[seq[i] + C].num;//获取maps容器中键值为(seq[i] + C)的元素的num值
	}

	std::cout << Num << std::endl;
	return 0;
}

# 4. 平衡二叉树

鄙人不才，看着别人的板子做了一个平衡二叉树的库，会慢慢去读，当然本题也有另外的思路。

# 4.1 平衡二叉树封装库

行高亮

/*食用示例：
#include "BalanceBiTree.h"

template<class ElementType>;
void main(){
	Node<int> * root;
	BalanceBiTree<int> T(root);
	...
}
*/
#ifndef _BALANCEBITREE_H_//头文件保护机制
#define _BALANCEBITREE_H_
#include <iostream>
#include <cmath>
using namespace std;
 
template< class ElementType>
/*
int main() {
    // 使用 Node<int> 实例化模板，其中 ElementType 被替换为 int 类型
    Node<int> intNode;
    intNode.data = 42;

    // 使用 Node<double> 实例化模板，其中 ElementType 被替换为 double 类型
    Node<double> doubleNode;
    doubleNode.data = 3.14;

    // 使用 Node<std::string> 实例化模板，其中 ElementType 被替换为 std::string 类型
    Node<std::string> stringNode;
    stringNode.data = "Hello, world!";
    return 0;
}
*/
struct Node{
    ElementType data;
    struct Node *lChild;
    struct Node *rChild;
    int balanceFctor;           //平衡因子
};
template< class ElementType>
class BalanceBiTree{//平衡二叉树的所有操作
public :
    BalanceBiTree(Node<ElementType> *& T);                       //初始化
    static void menu();                                          //菜单
    void destory(Node<ElementType> *& T);                        //销毁二叉树
    void insert(Node<ElementType> *& T,Node<ElementType> * S);   //将指针S所指节点插入二叉排序中
    int BiTreeDepth(Node <ElementType> * T);                     //求树的高度
    int getNodeFactor(Node<ElementType> *T);                     //求树中节点的平衡因子
    void factorForTree(Node<ElementType> *&T);                   //求树中的每个节点的平衡因子
    void nodeFctorIsTwo(Node<ElementType> *&T,Node<ElementType> *&p);        //获得平衡因子为2或-2的节点
    void nodeFctorIsTwoFather(Node<ElementType> *&T,Node<ElementType> *&f);  //获得平衡因子为2或-2的节点的父节点
    void LLAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f);                        //LL调整
    void LRAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f);                        //LR调整
    void RLAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f);                        //RL调整
    void RRAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f);                        //RR调整
    void AllAdjust(Node<ElementType> *&T);                       //集成四种调整，并实时更新平衡因子
    void preOrderTraverse(Node<ElementType> *T,int level);       //先序遍历输出
    void inOrderTraverse(Node <ElementType> *T,int level);       //中序遍历输出
    void BiTreeToArray(Node <ElementType> *T,ElementType A[],int i,int &count); //二叉树转数组
    void LevelTraverse(Node <ElementType> *T,ElementType B[],int num);          //对二叉链表表示的二叉树，按从上到下，从左到右打印结点值，即按层次打印
    void createSubBalanceBiTree(Node<ElementType> *&T);          //交互创建二叉平衡树
    void createBalanceBiTreeFromArray(Node<ElementType> *&T,ElementType A[],int n);//从数组中创建平衡二叉树
    void search(Node <ElementType> *&T,Node <ElementType> *&p,ElementType x);          //查找元素x
    Node <ElementType> * getElementFatherPointer(Node <ElementType> *&T,Node <ElementType> *&f,ElementType x); //获取某个元素的父亲指针，不存在返回NULL
    void getPriorElement(Node <ElementType> *&T,ElementType &min,ElementType &max);                 //获取前驱元素
    Node <ElementType> * getElementPriorPointer(Node <ElementType> *&T);  //获取某个元素的前驱指针
    void getNextElement(Node <ElementType> *&T,ElementType &min,ElementType &max);                  //获取后继元素
    Node <ElementType> * getElementNextPointer(Node <ElementType> *&T);   //获取某个元素的后继指针
    void deleteLeafNode(Node <ElementType> *&T,Node <ElementType> *&p,Node <ElementType> *&f);        //删除叶子节点
    void deleteOneBranchNode(Node <ElementType> *&T,Node <ElementType> *&p,Node <ElementType> *&f);   //删除仅有左子树或只有右子树的节点
    void deleteTwoBranchNode(Node <ElementType> *&T,Node <ElementType> *&p);   //删除既有左子树又有右子树的节点
    void deleteOperate(Node <ElementType> *&T,ElementType x);         //集成删除的三种情况的操作
private :
    Node<ElementType> *root;   //树根
};
//初始化
template< class ElementType>
BalanceBiTree<ElementType>::BalanceBiTree(Node<ElementType> *& T)
{
    T=NULL;
}
//菜单
template< class ElementType>
void BalanceBiTree<ElementType>::menu()
{
    cout<<"*************************************************"<<endl;
    cout<<"0退出并销毁平衡二叉树"<<endl;
    cout<<"1二分查找算法实现查找元素"<<endl;
    cout<<"2插入结点构建二叉排序树（二叉平衡树）"<<endl;
    cout<<"3二叉排序树中查找指定值的结点"<<endl;
    cout<<"4二叉排序树中删除特定值的结点"<<endl;
    cout<<"5数组A[1..26]递增有序，设计算法以构造一棵平衡的二叉排序树"<<endl;
    cout<<"6树形输出"<<endl;
    cout<<"*************************************************"<<endl;
}
//销毁二叉树
template< class ElementType>
void BalanceBiTree<ElementType>::destory(Node<ElementType> *& T)
{
    if(T)
    {
        destory(T->lChild);
        destory(T->rChild);
        delete T;
    }
}
//将指针S所指节点插入二叉排序中
template< class ElementType>
void BalanceBiTree<ElementType>::insert(Node<ElementType> *& T,Node<ElementType> * S)
{
    if(T==NULL)
        T=S;
    else if(S->data<T->data)
        insert(T->lChild,S);
    else
        insert(T->rChild,S);
}
//求树的高度
template< class ElementType>
int BalanceBiTree<ElementType>::BiTreeDepth(Node <ElementType> * T)
{
    int m,n;
    if(T==NULL)
        return 0;           //空树，高度为0
    else{
        m=BiTreeDepth(T->lChild);   //求左子树高度（递归）
        n=BiTreeDepth(T->rChild);   //求右子树高度（递归）
        if(m>n)
        {
            return m+1;
        }
        else{
            return n+1;
        }
    }
}
//求树中节点的平衡因子
template< class ElementType>
int BalanceBiTree<ElementType>::getNodeFactor(Node<ElementType> *T)
{
    int m=0,n=0;
    if(T)
    {
        m=BiTreeDepth(T->lChild);
        n=BiTreeDepth(T->rChild);
    }
    return m-n;
}
//求树中的每个节点的平衡因子
template< class ElementType>
void BalanceBiTree<ElementType>::factorForTree(Node<ElementType> *&T)
{
    if(T)
    {
        T->balanceFctor=getNodeFactor(T);
        factorForTree(T->lChild);
        factorForTree(T->rChild);
    }
}
//获得平衡因子为2或-2的节点
template< class ElementType>
void BalanceBiTree<ElementType>::nodeFctorIsTwo(Node<ElementType> *&T,Node<ElementType> *&p)
{
    if(T)
    {
        if(T->balanceFctor==2||T->balanceFctor==-2)
        {
             p=T;
        }
       nodeFctorIsTwo(T->lChild,p);
       nodeFctorIsTwo(T->rChild,p);
    }
}
//获得平衡因子为2或-2的节点的父节点
template< class ElementType>
void BalanceBiTree<ElementType>::nodeFctorIsTwoFather(Node<ElementType> *&T,Node<ElementType> *&f)
{
    if(T)
    {
        if(T->lChild!=NULL)
        {
            if(T->lChild->balanceFctor==2||T->lChild->balanceFctor==-2)
            {
                f=T;
            }
        }
        if(T->rChild!=NULL)
        {
            if(T->rChild->balanceFctor==2||T->rChild->balanceFctor==-2)
            {
                f=T;
            }
        }
        nodeFctorIsTwoFather(T->lChild,f);
        nodeFctorIsTwoFather(T->rChild,f);
    }
}
//LL调整
template< class ElementType>
void BalanceBiTree<ElementType>::LLAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f)
{
    Node<ElementType> *r;
    if(T==p)           //->balanceFctor==2&&T->lChild->balanceFctor!=2
    {
        cout<<"LL调整"<<endl;
        T=p->lChild;        //将P的左孩子提升为新的根节点
        r=T->rChild;
        T->rChild=p;        //将p降为其左孩子的右孩子
        p->lChild=r;        //将p原来的左孩子的右孩子连接其p的左孩子
 
    }
    else{
        if(f->lChild==p)     //f的左孩子是p
        {
            cout<<"LL调整"<<endl;
            f->lChild=p->lChild;        //将P的左孩子提升为新的根节点
            r=f->lChild->rChild;
            f->lChild->rChild=p;        //将p降为其左孩子的右孩子
            p->lChild=r;        //将p原来的左孩子的右孩子连接其p的左孩子
        }
        if(f->rChild==p)     //f的左孩子是p
        {
            cout<<"LL调整"<<endl;
            f->rChild=p->lChild;        //将P的左孩子提升为新的根节点
            r=f->rChild->rChild;
            f->rChild->rChild=p;        //将p降为其左孩子的右孩子
            p->lChild=r;        //将p原来的左孩子的右孩子连接其p的左孩子
        }
    }
}
//LR调整
template< class ElementType>
void BalanceBiTree<ElementType>::LRAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f)
{
    Node<ElementType> *l,*r;
    if(T==p)           //->balanceFctor==2&&T->lChild->balanceFctor!=2
    {
        cout<<"LR调整"<<endl;
        T=p->lChild->rChild;    //将P的左孩子的右孩子提升为新的根节点
        r=T->rChild;
        l=T->lChild;
        T->rChild=p;
        T->lChild=p->lChild;
        T->lChild->rChild=l;
        T->rChild->lChild=r;
    }
    else{
        if(f->rChild==p)     //f的左孩子是p
        {
            cout<<"LR调整"<<endl;
            f->rChild=p->lChild->rChild;    //将P的左孩子的右孩子提升为新的根节点
            r=f->rChild->rChild;
            l=f->rChild->lChild;
            f->rChild->rChild=p;
            f->rChild->lChild=p->lChild;
            f->rChild->lChild->rChild=l;
            f->rChild->rChild->lChild=r;
        }
        if(f->lChild==p)     //f的左孩子是p
        {
            cout<<"LR调整"<<endl;
            f->lChild=p->lChild->rChild;    //将P的左孩子的右孩子提升为新的根节点
            r=f->lChild->rChild;
            l=f->lChild->lChild;
            f->lChild->rChild=p;
            f->lChild->lChild=p->lChild;
            f->lChild->lChild->rChild=l;
            f->lChild->rChild->lChild=r;
        }
    }
}
//RL调整
template< class ElementType>
void BalanceBiTree<ElementType>::RLAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f)
{
    Node<ElementType> *l,*r;
    if(T==p)           //->balanceFctor==-2&&T->rChild->balanceFctor!=-2
    {
            cout<<"RL调整"<<endl;
            T=p->rChild->lChild;
            r=T->rChild;
            l=T->lChild;
            T->lChild=p;
            T->rChild=p->rChild;
            T->lChild->rChild=l;
            T->rChild->lChild=r;
    }
    else{
            if(f->rChild==p)     //f的左孩子是p
            {
                cout<<"RL调整"<<endl;
                f->rChild=p->rChild->lChild;
                r=f->rChild->rChild;
                l=f->rChild->lChild;
                f->rChild->lChild=p;
                f->rChild->rChild=p->rChild;
                f->rChild->lChild->rChild=l;
                f->rChild->rChild->lChild=r;
            }
            if(f->lChild==p)     //f的左孩子是p
            {
                cout<<"RL调整"<<endl;
                f->lChild=p->rChild->lChild;
                r=f->lChild->rChild;
                l=f->lChild->lChild;
                f->lChild->lChild=p;
                f->lChild->rChild=p->rChild;
                f->lChild->lChild->rChild=l;
                f->lChild->rChild->lChild=r;
            }
    }
}
//RR调整
template< class ElementType>
void BalanceBiTree<ElementType>::RRAdjust(Node<ElementType> *&T,Node<ElementType> *&p,Node<ElementType> *&f)
{
    Node<ElementType> *l;
    if(T==p)                   //->balanceFctor==-2&&T->rChild->balanceFctor!=-2
    {
            cout<<"RR调整"<<endl;
            T=p->rChild;        //将P的右孩子提升为新的根节点
            l=T->lChild;
            T->lChild=p;        //将p降为其右孩子的左孩子
            p->rChild=l;        //将p原来的右孩子的左孩子连接其p的右孩子
        //注意：p->rChild->balanceFctor==0插入节点时用不上，删除节点时可用
    }
    else{
            if(f->rChild==p)     //f的右孩子是p
            {
                cout<<"RR调整"<<endl;
                f->rChild=p->rChild;        //将P的右孩子提升为新的根节点
                l=f->rChild->lChild;
                f->rChild->lChild=p;        //将p降为其右孩子的左孩子
                p->rChild=l;        //将p原来的右孩子的左孩子连接其p的右孩子
            }
            if(f->lChild==p)     //f的左孩子是p
            {
                cout<<"RR调整"<<endl;
                f->lChild=p->rChild;        //将P的左孩子提升为新的根节点
                l=f->lChild->lChild;
                f->lChild->lChild=p;        //将p降为其左孩子的左孩子
                p->rChild=l;        //将p原来的右孩子的左孩子连接其p的右孩子
            }
    }
}
//集成四种调整，并实时更新平衡因子
template< class ElementType>
void BalanceBiTree<ElementType>::AllAdjust(Node<ElementType> *&T)
{
    Node<ElementType> *f=NULL,*p=NULL;
    factorForTree(T);
    nodeFctorIsTwoFather(T,f);
    nodeFctorIsTwo(T,p);
    while(p)
    {
        factorForTree(T);
        if(p->balanceFctor==2&&(p->lChild->balanceFctor==1||p->lChild->balanceFctor==0))
        {
            LLAdjust(T,p,f);
            factorForTree(T);
        }
        else if(p->balanceFctor==2&&p->lChild->balanceFctor==-1)
        {
            LRAdjust(T,p,f);
            factorForTree(T);
        }
        else if(p->balanceFctor==-2&&p->rChild->balanceFctor==1)
        {
            RLAdjust(T,p,f);
            factorForTree(T);
        }
        else if(p->balanceFctor==-2&&(p->rChild->balanceFctor==-1||p->rChild->balanceFctor==0))  //||p->rChild->balanceFctor==0
        {
            RRAdjust(T,p,f);
        }
        f=NULL;
        p=NULL;
        nodeFctorIsTwoFather(T,f);
        nodeFctorIsTwo(T,p);
    }
}
//先序遍历输出
template< class ElementType>
void BalanceBiTree<ElementType>::preOrderTraverse(Node<ElementType> *T,int level)
{
    if(T)
    {
        cout<<"先序"<<"("<<T->data<<","<<level<<")"<<" ";
        preOrderTraverse(T->lChild,level+1);
        preOrderTraverse(T->rChild,level+1);
    }
}
//中序遍历算法
template<class ElementType>
void BalanceBiTree<ElementType>::inOrderTraverse(Node <ElementType> * T,int level)
{
    if(T)
    {
        inOrderTraverse(T->lChild,level+1);  //递归调用先序遍历左子树
        cout<<"中序"<<"("<<T->data<<","<<level<<")"<<" ";           //访问根节点
        inOrderTraverse(T->rChild,level+1);  //递归调用先序遍历右子树
    }
}
//二叉树转数组
template<class ElementType>
void BalanceBiTree<ElementType>::BiTreeToArray(Node <ElementType> *T,ElementType A[],int i,int &count)
{
    if(T!=NULL)
    {
        A[i]=T->data;
        if(i>count)
            count=i;
        BiTreeToArray(T->lChild,A,2*i,count);
        BiTreeToArray(T->rChild,A,2*i+1,count);
    }
}
//对二叉链表表示的二叉树，按从上到下，从左到右打印结点值，即按层次打印
template<class ElementType>
void BalanceBiTree<ElementType>::LevelTraverse(Node <ElementType> *T,ElementType B[],int num)
{
    int n,i,j,t,q,s,p,m=0,k=0;
    n=(int)((log(num)/log(2))+1);
    p=n;
    for(i=0;i<n;i++)
    {
        k=pow(2,m)+k;
        t=pow(2,m);
        j=pow(2,p-1)-1;
        q=pow(2,p)-1;
        s=q;
        for(j;j>0;j--)
        {
            cout<<" ";
        }
        for(t;t<=k;t++)
        {
            if(B[t]==0)
            {
                cout<<"*";
                for(q;q>0;q--)
                cout<<" ";
                q=s;
            }
            else{
                cout<<B[t];
                for(q;q>0;q--)
                cout<<" ";
                q=s;
            }
        }
        m++;
        p--;
        j=n-i-1;
        cout<<endl;
    }
}
//交互创建二叉平衡树
template< class ElementType>
void BalanceBiTree<ElementType>::createSubBalanceBiTree(Node<ElementType> *&T)
{
    int level=1;
    int i=1,j=0;
    int A[100]={0};
    int length=0;
    ElementType x;
    Node<ElementType> * S,*p;
    T=new Node<ElementType>;
    T->balanceFctor=0;
    T->lChild=NULL;
    T->rChild=NULL;
    p=T;
    cout<<"请输入元素(-9999退出)：";
    cin>>x;
    T->data=x;
    while(x!=-9999)
    {
        cout<<"请输入元素：";
        cin>>x;
        if(x==-9999)
            return;
        S=new Node<ElementType>;
        S->data=x;
        S->balanceFctor=0;
        S->lChild=NULL;
        S->rChild=NULL;
        insert(p,S);
        AllAdjust(T);
        p=T;
        inOrderTraverse(T,level);
        cout<<endl;
        BiTreeToArray(T,A,i,length);
        cout<<"其树状图为："<<endl;
        LevelTraverse(T,A,length);
        j=0;
        for(j;j<100;j++)
        A[j]=0;
        level=1;
        i=1;
    }
}
//从数组中创建平衡二叉树
template< class ElementType>
void BalanceBiTree<ElementType>::createBalanceBiTreeFromArray(Node<ElementType> *&T,ElementType A[],int n)
{
    Node<ElementType> * S,*p;
    int i=1;
    T=new Node<ElementType>;
    T->balanceFctor=0;
    T->lChild=NULL;
    T->rChild=NULL;
    p=T;
    T->data=A[0];
    n=n-1;
    while(n)
    {
        S=new Node<ElementType>;
        S->data=A[i];
        S->balanceFctor=0;
        S->lChild=NULL;
        S->rChild=NULL;
        insert(p,S);
        AllAdjust(T);
        p=T;
        i++;
        n--;
    }
}
//查找元素x
template<class ElementType>
void BalanceBiTree<ElementType>::search(Node <ElementType> *&T,Node <ElementType> *&p,ElementType x)
{
   if(T)
   {
       if(T->data==x)
        p=T;
       search(T->lChild,p,x);
       search(T->rChild,p,x);
   }
}
 //获取某个元素的父亲指针，不存在返回NULL
template<class ElementType>
Node <ElementType> * BalanceBiTree<ElementType>::getElementFatherPointer(Node <ElementType> *&T,Node <ElementType> *&f,ElementType x)
{
    if(T)
    {
        if(T->lChild!=NULL)
        {
            if(T->lChild->data==x)
                f=T;
        }
        if(T->rChild!=NULL)
        {
            if(T->rChild->data==x)
                f=T;
        }
        getElementFatherPointer(T->lChild,f,x);
        getElementFatherPointer(T->rChild,f,x);
    }
}
//获取前驱元素
template<class ElementType>
void BalanceBiTree<ElementType>::getPriorElement(Node <ElementType> *&T,ElementType &min,ElementType &max)
{
    if(T)
    {
        min=T->data;
        if(min>max)
            max=min;
        getPriorElement(T->lChild,min,max);
        getPriorElement(T->rChild,min,max);
    }
}
//获取某个元素的前驱指针
template<class ElementType>
Node <ElementType> * BalanceBiTree<ElementType>::getElementPriorPointer(Node <ElementType> *&T)
{
    Node <ElementType> *p;
    ElementType min=0,max=-9999;
    getPriorElement(T,min,max);
    search(T,p,max);
    return p;
}
//获取后继元素
 template<class ElementType>
void BalanceBiTree<ElementType>::getNextElement(Node <ElementType> *&T,ElementType &min,ElementType &max)
{
    if(T)
    {
        max=T->data;
        if(min>max)
            min=max;
        getNextElement(T->lChild,min,max);
        getNextElement(T->rChild,min,max);
    }
}
//获取某个元素的后继指针
template<class ElementType>
Node <ElementType> * BalanceBiTree<ElementType>::getElementNextPointer(Node <ElementType> *&T)
{
    Node <ElementType> *p;
    ElementType min=9999,max=0;
    getNextElement(T,min,max);
    search(T,p,min);
    return p;
}
//删除叶子节点操作
template<class ElementType>
void BalanceBiTree<ElementType>::deleteLeafNode(Node <ElementType> *&T,Node <ElementType> *&p,Node <ElementType> *&f)
{
    if(p==NULL)
    {
        cout<<"此节点不存在，不能删除"<<endl;
        return;
    }
    if(T==p)        //根节点即为叶子节点
    {
        delete p;
        T=NULL;
    }
    else{           //删除节点为非根节点的叶子节点
        if(f->lChild==p)
        {
            delete p;
            f->lChild=NULL;
        }
        if(f->rChild==p)
        {
            delete p;
            f->rChild=NULL;
        }
    }
}
//删除仅有左子树或只有右子树的节点
template<class ElementType>
void BalanceBiTree<ElementType>::deleteOneBranchNode(Node <ElementType> *&T,Node <ElementType> *&p,Node <ElementType> *&f)
{
    if(p==NULL)
    {
        cout<<"此节点不存在，不能删除"<<endl;
        return;
    }
    if(T==p)
    {
        if(T->lChild==NULL&&T->rChild!=NULL)
        {
            T=p->rChild;
            delete p;
        }
        if(T->rChild==NULL&&T->lChild!=NULL)
        {
            T=p->lChild;
            delete p;
        }
    }
    else{
        if(p->lChild!=NULL)
        {
            if(f->lChild==p)
                f->lChild=p->lChild;
            else
                f->rChild=p->lChild;
        }
        if(p->rChild!=NULL)
        {
            if(f->lChild==p)
                f->lChild=p->rChild;
            else
                f->rChild=p->rChild;
        }
    }
}
//删除既有左子树又有右子树的节点
template<class ElementType>
void BalanceBiTree<ElementType>::deleteTwoBranchNode(Node <ElementType> *&T,Node <ElementType> *&p)
{
    Node <ElementType> *f,*next,*prior;
    if(p==NULL)
    {
        cout<<"此节点不存在，不能删除"<<endl;
        return;
    }
    if(p->balanceFctor==1)                             //p的平衡因子为1时，用p的前驱节点代替p
    {
        prior=getElementPriorPointer(p->lChild);             //获得x的前驱指针
        if(prior->lChild!=NULL&&prior->rChild==NULL)   //情况一前驱节点只有左孩子
        {
           p->data=prior->data;
           prior->data=prior->lChild->data;
           delete prior->lChild;
           prior->lChild=NULL;
        }
        if(prior->lChild==NULL&&prior->rChild==NULL)    //情况二前驱节点为叶子节点
        {
            getElementFatherPointer(T,f,prior->data); //得到前驱节点的父节点
            p->data=prior->data;
            delete prior;
            f->rChild=NULL;
        }
    }
   else if(p->balanceFctor==-1)                             //p的平衡因子为-1时，用p的后继节点代替p
    {
        next=getElementNextPointer(p->rChild);                //获得x的后继指针
        cout<<next->data;
        int level=1;
        if(next->rChild!=NULL&&next->lChild==NULL)      //情况一后继节点只有右孩子
        {
           p->data=next->data;
           next->data=next->rChild->data;
           delete next->rChild;
           next->rChild=NULL;
        }
        else if(next->rChild==NULL&&next->lChild==NULL)       //情况二后继节点为叶子节点
        {
            getElementFatherPointer(T,f,next->data);     //得到后继节点的父节点
            p->data=next->data;
            delete next;
            f->lChild=NULL;
        }
    }
    else if(p->balanceFctor==0)     //p的平衡因子为0时，用p的前驱或后继节点代替p，这里用前驱
    {
        prior=getElementPriorPointer(p->lChild);               //获得x的前驱指针
        if(prior->lChild!=NULL&&prior->rChild==NULL)     //情况一前驱节点只有左孩子
        {
           p->data=prior->data;
           prior->data=prior->lChild->data;
           delete prior->lChild;
           prior->lChild=NULL;
        }
        if(prior->lChild==NULL&&prior->rChild==NULL)      //情况二前驱节点为叶子节点
        {
            getElementFatherPointer(T,f,prior->data);     //得到前驱节点的父节点
            p->data=prior->data;
            delete prior;
            if(p==f)                                      //这块需要特殊记忆，唯独p->balanceFctor==0需要考虑***
                f->lChild=NULL;
            else
                f->rChild=NULL;
 
        }
    }
}
//集成删除的三种情况的操作
template<class ElementType>
void BalanceBiTree<ElementType>::deleteOperate(Node <ElementType> *&T,ElementType x)
{
    Node <ElementType> *f,*p=NULL;
    search(T,p,x);
    getElementFatherPointer(T,f,x);
    if(p==NULL)
    {
        cout<<"不存在此节点，删除失败！"<<endl;
        return;
    }
    if(p->lChild==NULL&&p->rChild==NULL)  //情况一删除节点为叶子节点
    {
        deleteLeafNode(T,p,f);
        if(T!=NULL)
           AllAdjust(T);
    }
    else if((p->lChild==NULL&&p->rChild!=NULL)||(p->lChild!=NULL&&p->rChild==NULL))
    {
        deleteOneBranchNode(T,p,f);
        if(T!=NULL)
           AllAdjust(T);
    }
    else                           //if(p->lChild!=NULL&&p->rChild!=NULL)
    {
        deleteTwoBranchNode(T,p);
        if(T!=NULL)
           AllAdjust(T);
    }
}
#endif // _BALANCEBITREE_H_

# 4.2 食用实例

行高亮

#include <iostream>
#include <Cstdlib>
#include "BalanceBiTree.h"
 
using namespace std;
 
//数组、顺序表的二分查找
template<class ElementType>
int BinarySearch(ElementType A[],int n,ElementType x)
{
    int mid,low=0,high=n-1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(x==A[mid])
        {
            return mid;
        }
        else if(x<A[mid])
        {
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    return -1;
}
//初始化数组
void initArray(int A[])
{
    int i=0;
    for(i;i<100;i++)
        A[i]=0;
}
int main()
{
    int x,y;
    int i=1;
    int level=1;
    int A[100]={0};
    int B[100]={0};
    int length=0;       //存储数组A的有效元素个数
    Node<int> * root;
    Node<int> * p;
    BalanceBiTree<int> T(root);
    BalanceBiTree<int>::menu();
    cout<<"请输入执行序号：";
    cin>>x;
    while(x!=0)
    {
        switch(x)
        {
            case 1:
                if(root!=NULL)
                    T.destory(root);
                length=0;
                cout<<"请输入数组元素的值：";
                cin>>y;
                while(y!=-9999)
                {
                    A[length]=y;
                    length++;
                    cout<<"请输入数组元素的值：";
                    cin>>y;
                }
                cout<<"请输入要查询元素的值：";
                cin>>x;
                if(BinarySearch(A,length+1,x)==-1)
                    cout<<"不存i=1;在！"<<endl;
                else{
                    cout<<"存在，其下标为："<<BinarySearch(A,length+1,x)<<endl;
                }
            break;
            case 2:
                T.createSubBalanceBiTree(root);
            break;
            case 3:
                cout<<"请输入要查询元素的值：";
                cin>>x;
                T. search(root,p,x);
                if(p!=NULL)
                {
                    if(p->data==x)
                        cout<<"元素存在！"<<endl;
                    else
                        cout<<"元素不存在！"<<endl;
                }
                else{
                    cout<<"元素不存在！"<<endl;
                }
            break;
            case 4:
                i=1;
                initArray(A);
                level=1;
                cout<<"请输入要删除元素的值：";
                cin>>x;
                T.deleteOperate(root,x);
                T.inOrderTraverse(root,level);
                T.BiTreeToArray(root,A,i,length);
                cout<<"其树状图为："<<endl;
                T.LevelTraverse(root,A,length);
            break;
            case 5:
                initArray(A);
                if(root!=NULL)
                    T.destory(root);
                length=0;
                y=1;
                for(y;y<=26;y++)
                {
                    A[length]=y;
                    length++;
                }
                T.createBalanceBiTreeFromArray(root, A,length);
                level=1;
                i=1;
                T.inOrderTraverse(root,level);
                cout<<endl;
                initArray(A);
                T.BiTreeToArray(root,A,i,length);
                cout<<"其树状图为："<<endl;
                T.LevelTraverse(root,A,length);
            break;
             case 6:
                i=1;
                initArray(A);
                T.AllAdjust(root);
                T.BiTreeToArray(root,A,i,length);
                cout<<"其树状图为："<<endl;
                T.LevelTraverse(root,A,length);
            break;
        }
        system("PAUSE");
        system("CLS");
        BalanceBiTree<int>::menu();
        cout<<"请输入执行序号：";
        cin>>x;
    }
    if(root!=NULL)
    T.destory(root);
    return 0;
}

# 4.3 本题题解

这道题，搓了一个小时，服了

行高亮

/*
4: 普通二叉树
描述
您需要写一种数据结构，来维护一些数（都是 1e9 以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，
操作次数 q 不超过 104：

1.查询值为x的数的排名（排名定义为比当前数小的数的个数 +1。若有多个相同的数，应输出最小的排名）。
2.查询排名为 x 的数。
3.求 x 的前驱（前驱定义为小于 x，且最大的数）。若未找到则输出−2147483647。
4.求 x 的后继（后继定义为大于 x，且最小的数）。若未找到则输出 2147483647。
5.插入一个数 x。
输入
第一行是一个整数 q，表示操作次数。

接下来 q 行，每行两个整数 op,x，分别表示操作序号以及操作的参数 x。

输出
输出有若干行。对于操作 1,2,3,4输出一个整数，表示该操作的结果。

样例
输入

7
5 1
5 3
5 5
1 3
2 2
3 3
4 3
输出

2
3
1
5
*/
/*常规思路
观察题目，题目的想法是想让我们写一颗可以插入和查询的平衡二叉树
*/

#include <iostream>
#include <vector>
using namespace std;

//typedef int ElementType;

template<class ElementType>
struct Node {
    ElementType data;
    struct Node* lChild;
    struct Node* rChild;
    int balanceFactor;           //平衡因子
};
template<class ElementType>
class BalanceBiTree {//平衡二叉树的所有操作
public:
    BalanceBiTree(Node<ElementType>*& T);                       //初始化
    void destory(Node<ElementType>*& T);                        //销毁二叉树
    void insert(Node<ElementType>*& T, Node<ElementType>* S);   //将指针S所指节点插入二叉排序中
    int BiTreeDepth(Node <ElementType>* T);                     //求树的高度
    int getNodeFactor(Node<ElementType>* T);                     //求树中节点的平衡因子
    void factorForTree(Node<ElementType>*& T);                   //求树中的每个节点的平衡因子
    void nodeFctorIsTwo(Node<ElementType>*& T, Node<ElementType>*& p);        //获得平衡因子为2或-2的节点
    void nodeFctorIsTwoFather(Node<ElementType>*& T, Node<ElementType>*& f);  //获得平衡因子为2或-2的节点的父节点
    void LLAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f);                        //LL调整
    void LRAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f);                        //LR调整
    void RLAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f);                        //RL调整
    void RRAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f);                        //RR调整
    void AllAdjust(Node<ElementType>*& T);                       //集成四种调整，并实时更新平衡因子

    
    //1查x的排名
    int searchXRank(Node<ElementType>* T, int x);
    //1中序遍历辅助函数
    void inorderTraversal(Node<ElementType>* T, ElementType x, int& rank, bool& found);
    //2查找排名为 x 的值
    ElementType searchRankValue(Node<ElementType>* T, int x);
    // 中序遍历辅助函数，
    void inorderTraversalForRank(Node<ElementType>* T, int x, int& currentRank, ElementType& result);
    //3.前驱
    ElementType findPredecessor(Node<ElementType>* T, ElementType x);
    //4后继
    ElementType findSuccessor(Node<ElementType>* T, ElementType x);
    //5 交互创建二叉平衡树
    void createSubBalanceBiTree(Node<ElementType>*& T, ElementType x);         
    
private:
    Node<ElementType>* root;   //树根
};

//初始化
template<class ElementType>
BalanceBiTree<ElementType>::BalanceBiTree(Node<ElementType>*& T)
{
    T = NULL;
}

//销毁二叉树
template<class ElementType>
void BalanceBiTree<ElementType>::destory(Node<ElementType>*& T)
{
    if (T)
    {
        destory(T->lChild);
        destory(T->rChild);
        delete T;
    }
}
//将指针S所指节点插入二叉排序中
template<class ElementType>
void BalanceBiTree<ElementType>::insert(Node<ElementType>*& T, Node<ElementType>* S)
{
    if (T == NULL)
        T = S;
    else if (S->data < T->data)
        insert(T->lChild, S);
    else
        insert(T->rChild, S);
}
//求树的高度
template<class ElementType>
int BalanceBiTree<ElementType>::BiTreeDepth(Node <ElementType>* T)
{
    int m, n;
    if (T == NULL)
        return 0;           //空树，高度为0
    else {
        m = BiTreeDepth(T->lChild);   //求左子树高度（递归）
        n = BiTreeDepth(T->rChild);   //求右子树高度（递归）
        if (m > n)
        {
            return m + 1;
        }
        else {
            return n + 1;
        }
    }
}
//求树中节点的平衡因子
template<class ElementType>
int BalanceBiTree<ElementType>::getNodeFactor(Node<ElementType>* T)
{
    int m = 0, n = 0;
    if (T)
    {
        m = BiTreeDepth(T->lChild);
        n = BiTreeDepth(T->rChild);
    }
    return m - n;
}
//求树中的每个节点的平衡因子
template<class ElementType>
void BalanceBiTree<ElementType>::factorForTree(Node<ElementType>*& T)
{
    if (T)
    {
        T->balanceFactor = getNodeFactor(T);
        factorForTree(T->lChild);
        factorForTree(T->rChild);
    }
}
//获得平衡因子为2或-2的节点
template< class ElementType>
void BalanceBiTree<ElementType>::nodeFctorIsTwo(Node<ElementType>*& T, Node<ElementType>*& p)
{
    if (T)
    {
        if (T->balanceFactor == 2 || T->balanceFactor == -2)
        {
            p = T;
        }
        nodeFctorIsTwo(T->lChild, p);
        nodeFctorIsTwo(T->rChild, p);
    }
}
//获得平衡因子为2或-2的节点的父节点
template<class ElementType>
void BalanceBiTree<ElementType>::nodeFctorIsTwoFather(Node<ElementType>*& T, Node<ElementType>*& f)
{
    if (T)
    {
        if (T->lChild != NULL)
        {
            if (T->lChild->balanceFactor == 2 || T->lChild->balanceFactor == -2)
            {
                f = T;
            }
        }
        if (T->rChild != NULL)
        {
            if (T->rChild->balanceFactor == 2 || T->rChild->balanceFactor == -2)
            {
                f = T;
            }
        }
        nodeFctorIsTwoFather(T->lChild, f);
        nodeFctorIsTwoFather(T->rChild, f);
    }
}
//LL调整
template< class ElementType>
void BalanceBiTree<ElementType>::LLAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f)
{
    Node<ElementType>* r;
    if (T == p)           //->balanceFctor==2&&T->lChild->balanceFctor!=2
    {
        //cout << "LL调整" << endl;
        T = p->lChild;        //将P的左孩子提升为新的根节点
        r = T->rChild;
        T->rChild = p;        //将p降为其左孩子的右孩子
        p->lChild = r;        //将p原来的左孩子的右孩子连接其p的左孩子

    }
    else {
        if (f->lChild == p)     //f的左孩子是p
        {
            // cout << "LL调整" << endl;
            f->lChild = p->lChild;        //将P的左孩子提升为新的根节点
            r = f->lChild->rChild;
            f->lChild->rChild = p;        //将p降为其左孩子的右孩子
            p->lChild = r;        //将p原来的左孩子的右孩子连接其p的左孩子
        }
        if (f->rChild == p)     //f的左孩子是p
        {
            // cout << "LL调整" << endl;
            f->rChild = p->lChild;        //将P的左孩子提升为新的根节点
            r = f->rChild->rChild;
            f->rChild->rChild = p;        //将p降为其左孩子的右孩子
            p->lChild = r;        //将p原来的左孩子的右孩子连接其p的左孩子
        }
    }
}
//LR调整
template< class ElementType>
void BalanceBiTree<ElementType>::LRAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f)
{
    Node<ElementType>* l, * r;
    if (T == p)           //->balanceFctor==2&&T->lChild->balanceFctor!=2
    {
        //cout << "LR调整" << endl;
        T = p->lChild->rChild;    //将P的左孩子的右孩子提升为新的根节点
        r = T->rChild;
        l = T->lChild;
        T->rChild = p;
        T->lChild = p->lChild;
        T->lChild->rChild = l;
        T->rChild->lChild = r;
    }
    else {
        if (f->rChild == p)     //f的左孩子是p
        {
            //  cout << "LR调整" << endl;
            f->rChild = p->lChild->rChild;    //将P的左孩子的右孩子提升为新的根节点
            r = f->rChild->rChild;
            l = f->rChild->lChild;
            f->rChild->rChild = p;
            f->rChild->lChild = p->lChild;
            f->rChild->lChild->rChild = l;
            f->rChild->rChild->lChild = r;
        }
        if (f->lChild == p)     //f的左孩子是p
        {
            //  cout << "LR调整" << endl;
            f->lChild = p->lChild->rChild;    //将P的左孩子的右孩子提升为新的根节点
            r = f->lChild->rChild;
            l = f->lChild->lChild;
            f->lChild->rChild = p;
            f->lChild->lChild = p->lChild;
            f->lChild->lChild->rChild = l;
            f->lChild->rChild->lChild = r;
        }
    }
}
//RL调整
template< class ElementType>
void BalanceBiTree<ElementType>::RLAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f)
{
    Node<ElementType>* l, * r;
    if (T == p)           //->balanceFctor==-2&&T->rChild->balanceFctor!=-2
    {
        // cout << "RL调整" << endl;
        T = p->rChild->lChild;
        r = T->rChild;
        l = T->lChild;
        T->lChild = p;
        T->rChild = p->rChild;
        T->lChild->rChild = l;
        T->rChild->lChild = r;
    }
    else {
        if (f->rChild == p)     //f的左孩子是p
        {
            //cout << "RL调整" << endl;
            f->rChild = p->rChild->lChild;
            r = f->rChild->rChild;
            l = f->rChild->lChild;
            f->rChild->lChild = p;
            f->rChild->rChild = p->rChild;
            f->rChild->lChild->rChild = l;
            f->rChild->rChild->lChild = r;
        }
        if (f->lChild == p)     //f的左孩子是p
        {
            // cout << "RL调整" << endl;
            f->lChild = p->rChild->lChild;
            r = f->lChild->rChild;
            l = f->lChild->lChild;
            f->lChild->lChild = p;
            f->lChild->rChild = p->rChild;
            f->lChild->lChild->rChild = l;
            f->lChild->rChild->lChild = r;
        }
    }
}
//RR调整
template< class ElementType>
void BalanceBiTree<ElementType>::RRAdjust(Node<ElementType>*& T, Node<ElementType>*& p, Node<ElementType>*& f)
{
    Node<ElementType>* l;
    if (T == p)                   //->balanceFctor==-2&&T->rChild->balanceFctor!=-2
    {
        //cout << "RR调整" << endl;
        T = p->rChild;        //将P的右孩子提升为新的根节点
        l = T->lChild;
        T->lChild = p;        //将p降为其右孩子的左孩子
        p->rChild = l;        //将p原来的右孩子的左孩子连接其p的右孩子
        //注意：p->rChild->balanceFctor==0插入节点时用不上，删除节点时可用
    }
    else {
        if (f->rChild == p)     //f的右孩子是p
        {
            //  cout << "RR调整" << endl;
            f->rChild = p->rChild;        //将P的右孩子提升为新的根节点
            l = f->rChild->lChild;
            f->rChild->lChild = p;        //将p降为其右孩子的左孩子
            p->rChild = l;        //将p原来的右孩子的左孩子连接其p的右孩子
        }
        if (f->lChild == p)     //f的左孩子是p
        {
            //  cout << "RR调整" << endl;
            f->lChild = p->rChild;        //将P的左孩子提升为新的根节点
            l = f->lChild->lChild;
            f->lChild->lChild = p;        //将p降为其左孩子的左孩子
            p->rChild = l;        //将p原来的右孩子的左孩子连接其p的右孩子
        }
    }
}
//集成四种调整，并实时更新平衡因子
template< class ElementType>
void BalanceBiTree<ElementType>::AllAdjust(Node<ElementType>*& T)
{
    Node<ElementType>* f = NULL, * p = NULL;
    factorForTree(T);
    nodeFctorIsTwoFather(T, f);
    nodeFctorIsTwo(T, p);
    while (p)
    {
        factorForTree(T);
        if (p->balanceFactor == 2 && (p->lChild->balanceFactor == 1 || p->lChild->balanceFactor == 0))
        {
            LLAdjust(T, p, f);
            factorForTree(T);
        }
        else if (p->balanceFactor == 2 && p->lChild->balanceFactor == -1)
        {
            LRAdjust(T, p, f);
            factorForTree(T);
        }
        else if (p->balanceFactor == -2 && p->rChild->balanceFactor == 1)
        {
            RLAdjust(T, p, f);
            factorForTree(T);
        }
        else if (p->balanceFactor == -2 && (p->rChild->balanceFactor == -1 || p->rChild->balanceFactor == 0))  //||p->rChild->balanceFctor==0
        {
            RRAdjust(T, p, f);
        }
        f = NULL;
        p = NULL;
        nodeFctorIsTwoFather(T, f);
        nodeFctorIsTwo(T, p);
    }
}
//5
//交互创建二叉平衡树
//传入树，和这个x
template< class ElementType>
void BalanceBiTree<ElementType>::createSubBalanceBiTree(Node<ElementType>*& T, ElementType x) {
    Node<ElementType>* S = new Node<ElementType>;
    S->data = x;
    S->balanceFactor = 0;
    S->lChild = nullptr;
    S->rChild = nullptr;
    insert(T, S);
    AllAdjust(T);  // 修正此处，传递当前树的根节点 T
}

//
template<class ElementType>
int BalanceBiTree<ElementType>::searchXRank(Node<ElementType>* T, int x)
{
    int rank = 0;  // 记录排名
    bool found = false;  // 是否找到元素 x

    inorderTraversal(T, x, rank, found);  // 调用中序遍历函数

    if (found)
        return rank;  // 返回排名（比当前数小的数的个数 + 1）
    else
        return -1;  // 如果未找到元素 x，返回 -1 或其他合适的值
}

// 辅助函数
template<class ElementType>
void BalanceBiTree<ElementType>::inorderTraversal(Node<ElementType>* T, ElementType x, int& rank, bool& found)
{
    if (T == nullptr || found)  // 如果已经找到元素 x，停止遍历
        return;

    inorderTraversal(T->lChild, x, rank, found);

    rank++;  // 遍历过程中，遇到比当前数小的数，排名加一

    if (T->data == x) {
        found = true;
        return;
    }

    inorderTraversal(T->rChild, x, rank, found);
}

//2
// 查找排名为 x 的值
template<class ElementType>
ElementType BalanceBiTree<ElementType>::searchRankValue(Node<ElementType>* T, int x)
{
    int currentRank = 0;  // 当前的排名
    ElementType result;   // 存储查询结果

    inorderTraversalForRank(T, x, currentRank, result);  // 调用中序遍历函数

    return result;  // 返回查询结果
}

// 中序遍历辅助函数，用于查找排名为 x 的值
template<class ElementType>
void BalanceBiTree<ElementType>::inorderTraversalForRank(Node<ElementType>* T, int x, int& currentRank, ElementType& result)
{
    if (T == nullptr || currentRank >= x)
        return;

    inorderTraversalForRank(T->lChild, x, currentRank, result);

    currentRank++;  // 遍历过程中，遇到一个节点，排名加一

    if (currentRank == x) {
        result = T->data;  // 当前节点的值是排名为 x 的值
        return;
    }

    inorderTraversalForRank(T->rChild, x, currentRank, result);
}
//3前驱
template<class ElementType>
ElementType BalanceBiTree<ElementType>::findPredecessor(Node<ElementType>* T, ElementType x)
{
    ElementType predecessor = -2147483647;  // 默认前驱为 -2147483647

    while (T != nullptr) {
        if (T->data >= x) {
            T = T->lChild;  // 前驱在左子树中
        }
        else {
            predecessor = T->data;  // 更新前驱
            T = T->rChild;  // 继续在右子树中寻找
        }
    }

    return predecessor;
}

//4后继
template<class ElementType>
ElementType BalanceBiTree<ElementType>::findSuccessor(Node<ElementType>* T, ElementType x)
{
    ElementType successor = 2147483647;  // 默认后继为 2147483647

    while (T != nullptr) {
        if (T->data <= x) {
            T = T->rChild;  // 后继在右子树中
        }
        else {
            successor = T->data;  // 更新后继
            T = T->lChild;  // 继续在左子树中寻找
        }
    }

    return successor;
}
/*
  //1查x的排名
    int searchXRank(Node<ElementType>* T, int x);
    //1中序遍历辅助函数
    void inorderTraversal(Node<ElementType>* T, ElementType x, int& rank, bool& found);
    //2查找排名为 x 的值
    ElementType searchRankValue(Node<ElementType>* T, int x);
    // 中序遍历辅助函数，
    void inorderTraversalForRank(Node<ElementType>* T, int x, int& currentRank, ElementType& result);
    //3.前驱
    ElementType findPredecessor(Node<ElementType>* T, ElementType x);
    //4后继
    ElementType findSuccessor(Node<ElementType>* T, ElementType x);
    //5 交互创建二叉平衡树
    void createSubBalanceBiTree(Node<ElementType>*& T, ElementType x);   
*/
int main() {
    int q;
    cin >> q;
    Node<int>* root = nullptr;  // 初始化根节点为空
    BalanceBiTree<int> T(root);

    while (q-- > 0) {
        int op;
        int input;
        cin >> op >> input;

        if (op == 1) {
            // 查询元素 input 的排名
            int rank = T.searchXRank(root, input);
            cout << rank << endl;                
        }
        else if (op == 2) {
            //查询排名为 input 的元素
            int result = T.searchRankValue(root, input);
            cout << result << endl;
        }
        else if (op == 3) {
            // 查询元素 input 的前驱
            int predecessor = T.findPredecessor(root, input);
            cout<< predecessor << endl;
        }
        else if (op == 4) {
            // 查询元素 input 的后继
             int successor = T.findSuccessor(root, input);
            cout  << successor << endl;
        }
        else if (op == 5) {
            // 交互式创建二叉平衡树
            T.createSubBalanceBiTree(root, input);
        }
    }

    return 0;
}

# 5. 队列安排（数组模拟链表）

发现一个宝藏博主，刷题佬，由于笨人太笨了，没读懂题干。搜了一下

我们非常容易得出，这道题的大意就是在一个数列里进行大量的随机插入和随机删除操作，是一道数据结构的题目。

那么用什么数据结构呢？队列？可队列不支持随机插入和删除。

我们找遍所有容器，发现根本没有支持随机插入和删除的。

链表是一种支持随机插入和随机删除的数据结构。

知识传送门：数据结构 — 链表详解 - Seaway-Fu - 博客园 (cnblogs.com)

因此，套用 **“数组模拟链表”** 板子，这道题按照要求写就好了

行高亮

/*
5: 队列安排
描述
一个学校里老师要将班上 N 个同学排成一列，同学被编号为1∼N，他采取如下的方法：
先将 1 号同学安排进队列，这时队列中只有他一个人；
2-N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；
最后，从队列中去掉 M(M<N） 个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
输入
第 1 行为一个正整数 N，表示了有 N 个整数。
第 2∼N行，第 i 行包含两个整数 k,p，其中 k 为小于i 的正整数，p 为 0 或者 1。若 p 为0，
则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边。
第 N+1 行为一个正整数 M，表示去掉的同学数目。
接下来 M行，每行一个正整数 x，表示将 x 号同学从队列中移去，如果 x 号同学已经不在队列中则忽略这一条指令。
输出
1 行，包含最多 N 个空格隔开的正整数，表示了队列从左到右所有同学的编号，行末换行且无空格。
样例
输入
4
1 0
2 1
1 0
2
3
3
输出
2 4 1
*/
#include <iostream>
using namespace std;

int n, m;

struct Node {
    int prev, next;
} nodes[100010];

void init() {
    for (int i = 1; i <= n; i++)
        nodes[i].prev = nodes[i].next = -1;
    nodes[1].next = -1;
    nodes[1].prev = 0;
    nodes[0].next = 1;
}

void insertLeft(int pos, int k) {
    nodes[nodes[pos].prev].next = k;
    nodes[k].prev = nodes[pos].prev;
    nodes[pos].prev = k;
    nodes[k].next = pos;
}

void insertRight(int pos, int k) {
    nodes[nodes[pos].next].prev = k;
    nodes[k].next = nodes[pos].next;
    nodes[pos].next = k;
    nodes[k].prev = pos;
}

void removeNode(int x) {
    if (nodes[x].prev == -1)
        return;
    nodes[nodes[x].prev].next = nodes[x].next;
    nodes[nodes[x].next].prev = nodes[x].prev;
    nodes[x].prev = -1;
    nodes[x].next = -1;
}

void print() {
    int start = nodes[0].next;
    while (start != -1) {
        cout << start << " ";
        start = nodes[start].next;
    }
    cout << endl;
}

int main() {
    cin >> n;
    init();
    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p;
        if (p == 1)
            insertRight(k, i);
        else
            insertLeft(k, i);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        removeNode(x);
    }
    print();
    return 0;
}

# 6. 明明的随机数

描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（N<=100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成 “去重” 与 “排序” 的工作。

输入

输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。
第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。

输出

输出也是两行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。
第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例

输入

测试数据

1 2	10 20 40 32 67 40 20 89 300 400 15

输出

结果

1 2	8 15 20 32 40 67 89 300 400

题解

行高亮

/*6: 明明的随机数
描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N个 1到 1000 之间的随机整数 （N <= 100），
对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。
请你协助明明完成“去重”与“排序”的工作。
*/
//map的应用，只从大到小输出关键字
//或者说，只用链表，大大缩短空间效率，不过还要排序
//再次，可以直接用数组当索引
#include <iostream>
using namespace std;
int map[1000] = {0};
int n;

int main() {
	cin >> n;
	while (n-- > 0) {
		int input = 0;
		cin >> input;
		map[input]++;
	}
	int num = 0;
	for (int i = 0; i < 1000; i++) {
		if (map[i] != 0) {
			num++;
		}
	}
	cout <<num<< endl;
	for (int i = 0; i < 1000; i++) {
		if (map[i] != 0) {
			cout << i << " ";
		}
	}
	cout << endl;
	return 0;
}

# 7. 奖学金 (冒泡排序)

描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。

例如，在某个正确答案中，如果前两行的输出数据 (每行输出两个数：学号、总分) 是:
7 279
5 279
这两行数据的含义是：总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理，不能得分。

输入

共 n+1 行。
第 1 行为一个正整数 n（n≤300)，表示该校参加评选的学生人数。
第 2 到 n+1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1~n（恰好是输入数据的行号减 1）。

输出

共 5 行，每行是两个用空格隔开的正整数，依次表示前 5 名学生的学号和总分。

样例

输入 1

输出 1

输入 2

输出 2

行高亮

/*
7: 奖学金
*/
#include<iostream>

using namespace std;
struct Node{
	int Chinese;
	int Num;
	int Number;
}Node[301],temp;
void init() {
	for (int i = 0; i < 301; i++) {
		Node[i].Chinese = 0;
		Node[i].Num = 0;
	}
}
int n;

int main() {
	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		int Math, English;
		cin >> Node[i].Chinese >> Math >> English;
		Node[i].Num = Node[i].Chinese + Math + English;
		Node[i].Number = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (Node[i].Num > Node[j].Num) {
				temp = Node[j];
				Node[j] = Node[i];
				Node[i] = temp;
			}
			if (Node[i].Num == Node[j].Num && Node[i].Chinese>Node[j].Chinese) {
				temp = Node[j];
				Node[j] = Node[i];
				Node[i] = temp;
			}
			if (Node[i].Num == Node[j].Num && Node[i].Chinese == Node[j].Chinese && Node[i].Number<Node[j].Number) {
				temp = Node[j];
				Node[j] = Node[i];
				Node[i] = temp;
			}
		}
	}
	for (int i = 1; i <= 5; i++) {
		cout << Node[i].Number <<" "<< Node[i].Num<<endl;
	}
	return 0;
}

# 8. 纪念品分组（sort 函数）

传送门：

C++ sort () 排序详解 - CSDN 博客

本题其实是想让我们自己实现一个排序算法，鄙人考虑的是二叉平衡树，因为刚写了嘛，然后简单利用贪心思想，将最大的和最小的捆绑，如果超出了 num，最大的就变小点，直到最后分完。

但接触到了 sort 快排函数，也是 nlog2n，因此这里偷下懒了，用函数了，但笔者要回来补充快排手动实现。

行高亮

/*
8: 纪念品分组
描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，
他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。
为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入
共 n+2行：
第一行包括一个整数 w，为每组纪念品价格之和的上限。
第二行为一个整数 n，表示购来的纪念品的总件数 G。
第 3 ∼n+2 行每行包含一个正整数 Pi 表示所对应纪念品的价格。

输出
一个整数，即最少的分组数目。

样例
输入
100
9
90
20
20
30
50
60
70
80
90
输出
6
*/
//
#include<iostream>
#include<algorithm>
using namespace std;
int num[30010];
int main()
{
    int Num, G, ans = 0;
    cin >> Num >> G;
    for (int i = 1; i <= G; i++)
        cin >> num[i];
    sort(num + 1, num + G + 1);
    int i = 1, j = G;
    //要有等于，，i=j的时候，就是只剩一个，归到else里ans++
    while (i <= j)
    {
        //最大的和最小的一组
        if (num[j] + num[i] <= Num)
        {
            ans++;
            j--;
            i++;
        }
        //大的各成一组
        else
        {
            ans++;
            j--;
        }
    }
    cout << ans;
    return 0;
}

# 9. 统计数字

行高亮

/*9: 统计数字
描述
某次科研调查时得到了n个自然数，每个数均不超过1500000000(1.5×109)。
已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入
共n + 1行。

第一行是整数n，表示自然数的个数；

第2至n + 1每行一个自然数。

输出
共m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出2个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例
输入

8
2
4
2
4
5
100
2
100
输出

2 3
4 2
5 1
100 2
*/
//一眼map，mapyyds
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

typedef struct ref {
	int num;//出现次数
	//int fp;
}reflect;//定义映射

int N;
int main() {
	map<int, reflect> maps;
	cin >> N;
	
	int input[1000] = { 0 };//最多N个输入，记录输入
	for (int i = 0; i < N; ++i) {
		cin >> input[i];//输入键Key的值，键之间可以重复输值进去
		++maps[input[i]].num;//一旦有这个数输入，我就将它的map容器中对应的元素的num值加1
	}
	sort(input, input + N);
	for (int i = 0; i < N; i++) {
		if (input[i] != input[i - 1]) {
			cout << input[i] << " " << maps[input[i]].num << endl;
		}
	}
	return 0;
}

# 10. 分数线划定

行高亮

/*
11: 合并果子
描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过 n-1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，
并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。
输入
共两行。
第一行是一个整数 n(1≤n≤10000) ，表示果子的种类数。
第二行包含 n 个整数，用空格分隔，第 i 个整数ai(1≤ai≤20000) 是第 i 种果子的数目。
输出
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2e31
样例
输入
3
1 2 9
输出
15
*/
#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
    int num;
    int n;
} Get[5000];

int n, m;
//初始化
void init() {
    for (int i = 0; i < 5000; i++) {
        Get[i].num = 0;
        Get[i].n = 0;
    }
}

bool compareByN(const Node& a, const Node& b) {
    if (a.n == b.n) { // 如果n相同
        return a.num < b.num; // 按照num进行排序
    }
    return a.n > b.n; // 否则按照n进行排序
}

int main() {
    init();
    cin >> n >> m; // (5≤n≤5000,3≤m≤n)
    int fnl = m * 15 / 10;

    for (int i = 0; i < n; i++) { 
        int input, temp;
        cin >> input >> temp;
        Get[i].num = input; 
        Get[i].n = temp;
    }

    sort(Get, Get + n, compareByN);
    cout << Get[fnl-1].n;

    int Max=0;
    for (int i = 0; i < n; i++) {
        if (Get[i].n < Get[fnl - 1].n) {
            cout << " " << i<< endl;
            Max = i;
            break;
        }
    }
    if (Max == 0) {
        cout << " " << n << endl;
        Max = n;
    }
	for (int i = 0; i < Max; i++) {
		cout << Get[i].num <<" "<< Get[i].n << endl;
	}
    
	return 0;
}

# 11. 合并果子 (优先队列的 Hufuman 树)

https://blog.csdn.net/c20182030/article/details/70757660

行高亮

/*
11: 合并果子
描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过 n-1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，
你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 3 种果子，数目依次为 1,2,9。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。
输入
共两行。
第一行是一个整数 n(1≤n≤10000) ，表示果子的种类数。
第二行包含 n 个整数，用空格分隔，第 i 个整数ai(1≤ai≤20000) 是第 i 种果子的数目。
输出
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2e31
样例
输入
3
1 2 9
输出
15
*/
//哈夫曼树
//优先队列的引入
//https://blog.csdn.net/c20182030/article/details/70757660
/*
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
*/
#include <iostream>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int>> Huafman; // 小根堆

int main() {
    int n;
    cin >> n;
    int result[1000] = { 0 }; // n-1次的每次体力，注意数组大小为n-1
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        Huafman.push(input);
    }

    int ans = 0;
    while (!Huafman.empty()) {
        int min1 = Huafman.top();
       // cout << min1 << endl;
        Huafman.pop();
        int min2 = Huafman.top();
        //cout << min2 << endl;
        Huafman.pop();
        result[ans] = min1 + min2;
        if (Huafman.empty())
            break;
        Huafman.push(result[ans]);
        ans++;
    }

    int Result = 0;
    for (int i = 0; i < n-1 ; i++) {//只操作n-1次
        Result += result[i];
    }
    cout << Result << endl;
    return 0;
}

数据结构与算法