数据结构算法题总结

题目一：判断一棵二叉树是否是完全二叉树

题目分析

层序遍历

将所有的结点加入队列（包括空结点）。当遇到空结点时，查看其后面是否有空结点。若有，则二叉树不是完全二叉树。如果是满二叉树或者完全二叉树，这些空结点应该是在广度优先遍历的末尾，所以，当我们遍历到空洞的时候，整个二叉树就遍历完了。但如果是非完全二叉树，当遍历到空结点时，空结点后面还有非空结点。

C++代码

bool IsComplete(TreeNode* root){
	queue<int> q;
	q.push(root);
	if(!root)
		return 1;
	while(!q.isempty()){
  		auto p=q.front();
  		q.pop();
  		if(p){
  			q.push(p->left);
  			q.push(p->right);
		}
		else{
  			while(!q.isempty()){
  				auto m=q.front();
  				if(m!=NULL)
  					return 0;
			}
		}
	}
	return 1;
}

题目二：计算二叉树双分支结点个数

题目分析

计算一棵二叉树中的所有双分支结点个数的递归模型$f(b)$如下：

$f(b)=0$ 若b=NULL

$f(b)=f(b->left)+f(b->right)+1$ 若*b为双分支结点

$f(b)=f(b->left)+f(b->right$) 其他情况（*b为单分支结点或者为叶子结点）

C++代码

int double(TreeNode* root){
  	if(root==NULL)
  		return 0;
  	if(root->left&&root->right)
  		return double(root->left)+double(root->right)+1;
  	else
  		return double(root->left)+double(root->right);
}

题目三：访问先序遍历第k个节点

题目分析

递归

C++代码

TreeNode* dfs(TreeNode* root,int &k){
  	if(k==1)
  		return root;
  	dfs(root->left,k--);
  	dfs(root->right,k--);
}

题目四：打印某个结点的所有祖先

题目分析

递归

C++代码

bool printAncestor(TreeNode* root,int target){
  	if(!root) return false;
  	if(root->val==target)
  		return true;
  	if(printAncestor(root->left,target)||printAncestor(root->right,target)){
  		count<<root->val<<endl;
  		return true;
	}
	return false;
}

题目五：求二叉树的宽度

题目分析

层序遍历

C++代码

int TreeWidth(TreeNode* root){
  	queue<int> q;
  	q.push(root);
  	auto last=root;
  	int level=0;
  	int max=0;
  	int width=0;
  	while(!q.empty()){
  		auto t=q.front();
  		width++;
  		if(t->left)
  			q.push(t->left);
  		if(t->right)
  			q.push(t->right);
  		if(t=last){
  			last=q.back();
  			level++;
  			if(width>max)
  				max=width;
  			width=0;
		}
	}
	return max;
}

题目六：KMP算法

求next数组

next[j]表示当模式串匹配到T[j]遇到失败时，在模式串中需要重新和主串匹配的位置。换言之，next数组的求解实际是对每个位置找到最长的公共前缀下面按照递推的思想总结一下求解next[]数组：

• 根据定义next[1]=0，假设next[j]=k, 即P[1…k-1]==P[j-k,j-1]

• 若P[j]==P[k]，则有P[1..k]==P[j-k,j]，很显然，如果next[j]=k; 则next[j+1]=next[j]+1=k+1;否则next[j+1]=k+1!=next[j]+1;
• 若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]。

void get_next(char T[],int next[]){   
	int n=T.size();
    next[0]=-1;
    int k=-1;
    for(int i=1;i<n;i++){
    	while(j>-1&&s[j]!=s[k+1]) k=next[k];   //寻找到k的合适位置
        if(s[j]==s[k+1]) k++;
        next[j]=k;
	}
}
/*
next[j]=k表示当P[j] != T[i]时，j指针的下一步移动位置。
*/

KMP算法

时间复杂度O(m+n)

public static int KMP(String ts, String ps) {
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
    int[] next = getNext(ps);
    while (i < t.length && j < p.length) {
       if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
           i++;
           j++;
       } else {
           // i不需要回溯了
           // i = i - j + 1;
           j = next[j]; // j回到指定位置
       }
    }
    if (j == p.length) {
       return i - j;
    } else {
       return -1;
    }
}

题目七：排序算法

插入排序

基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成

直接插入排序

void InsertSort(int A[],int n){
  	int i,j;
  	for(i=2;i<=n;i++){
  		if(A[i]<A[i-1]){
  			A[0]=A[i];   //复制为哨兵，A[0]不存放元素
  			for(j=i-1;A[0]<A[j];j--)
  				A[j+1]=A[j];   //向后挪位
  			A[j+1]=A[0];   //复制到插入位置
		}
	}
}

设置哨兵的作用：避免数组下标出界

直接插入排序是边查找边移动

折半插入排序

void InsertSort(int A[],int n){
  	int i,j,low,high;
  	for(i=2;i<=n;i++){
  		low=1;
  		high=i-1;
  		A[0]=A[i];
  		while(low<high){
  			middle=low+high>>1;
  			if(A[middle]<A[0]) low=middle+1;
  			else r=middle;
		}
		for(j=i-1;j>=low;j--){
  			A[j+1]=A[j];
		}
		A[low]=A[0];
	}
}

折半插入排序是先查找再移动

希尔排序

void shellsort1(int a[], int n)
{
	int i, j, gap;
 
	for (gap = n / 2; gap > 0; gap /= 2) //步长
		for (i = 0; i < gap; i++)        //直接插入排序
		{
			for (j = i + gap; j < n; j += gap) 
				if (a[j] < a[j - gap])
				{
					int temp = a[j];
					int k = j - gap;
					while (k >= 0 && a[k] > temp)
					{
						a[k + gap] = a[k];
						k -= gap;
					}
					a[k + gap] = temp;
				}
		}
}

交换排序

冒泡排序

void BubbleSort(int A[],int n){
  	for(int i=0;i<n-1;i++){   //共要进行n-1趟排序
  		flag=false;     //表示本趟冒泡是否发生交换的标志
  		for(j=n-1;j>i;j--){     //一趟冒泡排序
  			if(A[j-1]>A[j]){    //若为逆序
  				swap(A[j-1],A[j]);   //发生交换
  				false=true;   
			}
		}
		if(flag==false)   //若本趟便利后没有发生交换，说明已经有序
			return;
	}
}

快速排序

int Partition(int A[],int low,int high){
  	int pivot=A[low];   //将当前表中的第一个元素设置为枢纽值，对表进行划分
  	while(low<high){
  		while(low<high&&A[high]>=pivot) high--;
  		A[low]=A[high];   //将比枢纽值小的值移动到左端
  		while(low<high&&A[low]<=pivot) low++;
  		A[high]=A[low];   //将比枢纽值大的值移动到右端
	}
	A[low]=pivot;    //将枢纽元素放到最终的位置
	return low;   //返回枢纽最终的位置
}
//递归形式
void QuickSort1(int A[],int low,int high){
  	if(low<high){
  		int pivotpos=Partition(A,low,high);    //划分
      	QuickSort(A,low,pivotpos-1);   //依次对两个子表进行排序
      	QuickSort(A,pivotpos+1,high);
	}
}
void QuickSort(int A[],int low,int high){
    stack<int> s;    
    if(low<high){
        int mid=Partition(A,low,high);
        if(low<mid-1){
            s.push_back(low);
            s.push_back(mid-1);
        }
        if(high>mid+1){
            s.push_back(mid+1);
            s.push_back(high);
        }
//其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行partition操作
        while(!s.empty()){
            int p=s.top();
            s.pop();
            int q=s.top();
            s.pop();
            mid=Partition(A,p,q);
            if(p<mid-1){
                s.push_back(p);
                s.push_back(mid-1);
            }
            if(q>mid+1){
                s.push_back(mid+1);
                s.push_back(q);
            }
        }
    }
}

空间效率：由于快速排序是递归的，需要借助一个递归栈来保存每一层递归调用的必要信息，其容量与递归调用的最大深度一致。最好的情况下为$log_2(n+1)$；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为$O(n)$；平均情况下，栈的深度为$O(log_2n)$

应用

双向冒泡排序

奇数趟的时候，从前往后比较相邻元素的关键字，遇到逆序即交换，直到把序列中关键字最大的元素移动到序列尾部。偶数趟时，从后往前比较相邻元素的关键字，遇到逆序即交换，直到把序列中关键字最小的元素移动到序列前端。

void BubbleSort(int A[],int n){
  	int low=0;
  	int high=n-1;
  	bool flag=true;
  	while(low<high&&flag){
  		flag=false;   //每一趟初始的时候将flag置为false
  		for(int i=low;i<high;i++){   //从前往后遍历
  			if(A[i]>A[i+1]){
  				swap(A[i],A[i+1]);
  				flag=false;
			}
		}
		high--;   //更新上界
		for(int j=high;j>low;j--){    //从后往前遍历
  			if(A[j]<A[j-1]){
  				swap(A[j],A[j-1]);
  				flag=false;
			}
		}
		low++;   //更新下界
	}
}

寻找数组中第k小的元素

从数组L[1…n]中选择枢纽pivot(随机地或者直接取第一个)进行和快速排序一样的划分操作后，表L[1…n]被划分为L[1…m-1]和L[m+1…n]，其中L[m]=pivot

讨论m与k的大小关系：

• 当m=k时，显然pivot就是要寻找到的元素，直接返回pivot就可以
• 当m<k时，则要寻找的元素一定是在L[m+1…n]中，从而可以对L[m+1…n]递归地查找第k-m小的元素
• 当m>k时，则要寻找的元素一定是在L[1…m-1]中，从而可以对L[1…m-1]递归地找第k小的元素

该算法的时间复杂度在平均的情况下可以达到O(n)

int kth_elem(int A[],int low,int high){
  	int pivot=A[low];
  	int low_temp=low;
  	int high_temp=high;
  	while(low<high){
  		while(low<high&&A[high]>=pivot) high--;
  		A[low]=A[high];
  		while(low<high&&A[low]<=pivot) low++;
  		A[high]=A[low];
	}
	A[low]=pivot;
	if(low==k)
	return pivot;
	else if(low>k)
		return kth_elem(A,low_temp,low-1,k);
	else
		return kth_elem(A,low+1,high_temp,k-m);
}

选择排序

每一趟（例如第i趟）在后面n-i+1(i=1,2,..,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素

简单选择排序

基本思想：假设排序表为L[1...n]，第i趟排序即从L[i...n]中选择关键字最小的元素与L[i]交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟就可以使得整个排序表有序

void Selectsort(int A[],int n){
	for(int i=0;i<n-1;i++){   //一共进行n-1趟
  		min=i;   //记录最小元素位置
  		for(int j=i+1;j<n;j++){       
  			if(A[j]<A[min])
  				min=j;
  			if(min!=i) swap(A[i],A[min]);
		}
	}  
}

堆排序

priority_queue<int> heap_max;     //定义大根堆
priority_queue<int,vector<int>,greater<int>> heap_min;    //定义小根堆
heap.push(x);   //入堆
heap.pop();    //出堆
heap.top();    //堆顶元素

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

vector<int> B;
void Merge(vector<int> A,int low,int mid,int high){   //A[low...mid]和A[mid+1...high]有序，将它们合并
  	for(int i=low;i<=high;i++)
  		B.push_back(A[i]);
  	for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
  		if(B[i]<=B[j])   //比较B的左右两端中的元素
  			A[k]=B[i++];  //将较小的复制到A中
  		else
  			A[k]=B[j++];
	}
	while(i<=mid) A[k++]=B[i++];
	while(j<=high) A[K++]=B[j++];
}

void MergeSort(vector<int> A,int low,int high){
  	while(low<high){
  		mid=low+high>>1;   //从中间划分两个子序列
      	MergeSort(A,low,mid);   //对左侧子序列进行递归排序
      	MergeSort(A,mid+1,high);   //对右侧子序列进行递归
      	Merge(A,low,mid,high);   //归并
	}
}

各种排序算法的性质

非递归访问数

首先要想到用到栈这个数据结构，其次要搞清楚递归的顺序

前序非递归遍历

void preOrder2(BinTree *root)     //非递归前序遍历 
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<"";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

中序非递归遍历

void InOrder(BiTree *T){
  	InitStack(S);
  	BiTree p=T;
  	while(p||!isEmpty(S)){
  		if(p){
  			push(S,p);
  			p=p->lchild;
		}
		else{
  			pop(S,p);
  			visit(p);
  			p=p->rchild;
		}
	}
}

后续非递归遍历

//strcut TreeNode {
//  ElemType data;
//  TreeNode *left, *right;
//  TreeNode() {
//      left = right = NULL;
//  }
//}
void PostOrder(TreeNode *root) {
    TreeNode *p = root, *r = NULL;    
    stack<TreeNode*> s;
    while (p || !s.empty()) {
        if (p) {//走到最左边
            s.push(p);
            p = p->left;
        }
        else {
            p = s.top();
            if (p->right && p->right != r){//右子树存在，未被访问
                p = p->right;   //转向右
              	s.push(p);      //压入栈
              	p=p->lchild;    //再走到最左
            }
            else {
                auto p=s.top();
                s.pop();
                visit(p->val);
                r = p;     //记录最近访问过的节点
                p = NULL;  //节点访问完后，重置p指针
            }
        }//else
    }//while
}
/*
因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。所以，使用辅助指针r，其指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被访问。
*/