二叉树的应用 | 幂集递归算法，汉诺塔递归算法，垂直输出二叉树，快速排序递归算法

幂集递归算法

求幂集元素递归法_递归求幂集_ZFW_FOR_LJY的博客-CSDN博客

Q: typename vector > ：前面为什么要加typename

在 C++ 中，当一个嵌套的类型依赖于模板参数时，需要使用 `typename` 关键字来告诉编译器这是一个类型而不是一个变量或函数。在这个例子中，`vector>` 是一个嵌套类型，其中的 `vector` 依赖于模板参数 `T`，因此需要使用 `typename` 来指示这是一个类型。 

//sumset是幂集信息，curset是幂集的一个子集的信息，res是存放幂集各个子集的信息

template<class T>
void Power(vector>& res,vector& sumset,vector& curset,int pos)//初始状态:res为空 curset为空 pos=0
{
    if(sumset.size()==0){return;}
 
    //递归条件
    if(pos==sumset.size())
    {
        res.push_back(curset);
        return;
    }
 
    //开始递归
    //左子树递归==>取当前pos对应于sumset中的元素
    curset.push_back(sumset[pos]);
    Power(res,sumset,curset,pos+1);
 
    //右子树递归==>不取当前pos对应于sumset中的元素
    curset.pop_back();//上面插入过所以这时需要尾部删除
    Power(res,sumset,curset,pos+1);
}

---

 快速排序

思路：
1、选出一个key，一般是最左边或是最右边的。
2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
4.此时key的左边都是小于key的数，key的右边都是大于key的数
5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

代码 

//快速排序   hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end)
{
	//只有一个数或区间不存在
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	//选左边为key
	int keyi = begin;
	while (begin < end)
	{
		//右边选小   等号防止和key值相等    防止顺序begin和end越界
		while (arr[end] >= arr[keyi] && begin < end)
		{
			--end;
		}
		//左边选大
		while (arr[begin] <= arr[keyi] && begin < end)
		{
			++begin;
		}
		//小的换到右边，大的换到左边
		swap(&arr[begin], &arr[end]);
	}
	swap(&arr[keyi], &arr[end]);
	keyi = end;
	//[left,keyi-1]keyi[keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr,keyi + 1,right);
}

图解 

快速排序法（详解）-CSDN博客

---

汉诺塔算法 （递归）

思路图

void Hanio_Step(int n, char A, char B, char C)
{
    if (1 == n)
        printf("%c->%c\n", A, C);  //如果只有一个盘，就把它从A移到C
    else
    {
        Hanio_Step(n-1, A, C, B); //把n-1个环从 A—>移到B
        printf("%c->%c", A, C);//剩下一个盘，就把它从A移到C
        Hanio_Step(n-1, B, A, C);//把n-1个环从 B—>移到C
    }
} 

代码

#define _CRT_SECURE_NO_WARNINGS
#include
void Hanio_Step(int n, char A, char B, char C)
{
	if (1 == n)
		printf("%c->%c\n", A, C);
	else
	{
		Hanio_Step(n-1, A, C, B);
		printf("%c->%c", A, C);
		Hanio_Step(n-1, B, A, C);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	Hanio_Step(n, 'A', 'B', 'C');
	return 0;
}

【精选】C语言 - 汉诺塔详解(超详细)_塔 c语言-CSDN博客

---