王道数据结构课后算法题

2018-10-05

顺序表

P18

例1

bool del_Min(SqList &L,ElemType &value){
	if(L.length==0){  //顺序表为空
		return false;
	}
	int pos=0;
	ElemType min=L.data[pos]; //最小值

	for(int i=1;i<L.length;i++){ //查找最小值
		if(min>L.data[i]){
			min=L.data[i];
			pos=i;
		}
	}
	value=min;  //输出最小值
	L.length--;  //更新长度
	L.data[pos]=L.data[L.lenght-1]; //空出位置由最后一个元素填补
	return true;
}

例2

void reverse(SqList &L){
	ElemType tmp;
	for(int i=0;i<L.length/2;i++){
		tmp=L.data[i];
		L.data[i]=L.data[L.length-1-i];
		L.data[L.lenght-1-i]=tmp;
	}
}

例3

void del_allX(SqList &L, ElemType x){
	int pos=0;		//计数
	for(int i=0;i<L.length;i++){
		if(L.data[i]!=x){
			L.data[pos++]=L.data[i];
		}
	}
	L.length=k;		//更新长度
}

例4

bool del_sTot(SqList &L, ElemType s,ElemType t){
	if(s>=t||L.lenght==0){
		return false;
	}
	int pos=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i]<s||L.data[i]>t){
			L.data[pos++]=L.data[i];
		}
	}
	L.lenght=pos;    //更新长度
	return true;
}

例5

 bool del_sTot(SqList &L, ElemType s,ElemType t){
	if(s>=t||L.lenght==0){
		return false;
	}
	int pos=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i]<=s||L.data[i]>=t){
			L.data[pos++]=L.data[i];
		}
	}
	L.lenght=pos;    //更新长度
	return true;
}

例6

bool delSame(SqList &L){
	if(L.length==0){
		return false;
	}
	int pos=0;
	ElemType tmp=L.data[pos++];
	for(int i=1;i<L.lenght;i++){
		if(L.data[i]!=tmp){
			L.data[pos++]=L.data[i];
		}
	}
	L.length=pos;
	return true;
}

例7

bool combinedAB(SqList A,SqList B,SqList &C){
	if(A.length+B.length>C.MaxSize){
		return false;
	}
	int i=0;
	int j=0;
	int k=0;
	while(i<A.length&&j<B.length){
		if(A.data[i]<B.data[j]){
			C.data[k++]=A.data[i++]
		}else{
			C.data[k++]=B.data[j++];
		}
	}
	while(i<A.length){
		C.data[k++]=A.data[i++];
	}
	while(j<B.length){
		C.data[k++]=B.data[j++];
	}
	C.length=k;
	return true;
}

例8

typedef int DataType;
bool reverse(DataType args[],int s,int e,int length){

	if(s>e||e>length){
		return false;
	}
	DataType tmp;
	int num=(e-s+1)/2;
	for(int i=0;i<num;i++){
		tmp=args[s-1+i];
		args[s-1+i]=args[e-1-i];
		args[e-1-i]=tmp;
	}
	return true;
}
void exchange(DataType args[],int m,int n,int length){
	reverse(args,1,m+n,length);
	reverse(args,1,n,n);
	reverse(args,n+1,m+n,length);
}

例9

typedef int DataType;
void searchExchangeInsert(DataType[] args,int x,int length){

	int left=0;
	int right=length-1;
	int mid;
	while(left<=right){
		mid=(left+right)/2;
		if(x==args[mid]){
			break;
		}else if(x>args[mid]){
			left=mid+1;
		}else{
			right=mid-1;
		}
	}
	DataType tmp;
	if(args[mid]==x&&mid<length-1){
		tmp=args[mid];
		args[mid]=args[mid+1];
		args[mid+1]=tmp;
	}else{
		for(int i=0;i<lenght;i++){
			if(args[i]>x){
				tmp=args[i];
				args[i]=x;
				x=tmp;
			}
		}
		args[length]=x;
	}
}

例10

typedef int DataType;
bool reverse(DataType args[],int s,int e,int length){

	if(s>e||e>length){
		return false;
	}
	DataType tmp;
	int num=(e-s+1)/2;
	for(int i=0;i<num;i++){
		tmp=args[s-1+i];
		args[s-1+i]=args[e-1-i];
		args[e-1-i]=tmp;
	}
	return true;
}
void exchange(DataType args[],int m,int n,int length){
	reverse(args,1,m+n,length);
	reverse(args,1,n,n);
	reverse(args,n+1,m+n,length);
}

例11

1 2	typedef int DataType; DataType getMedium(DataType args)

链表

P37

typedef int ElemType;
typedef struct LNode{
	ElemType data;
	LNode *next;
}LNode,*LinkList;

例1

void delX_no_head(LinkList &L,ElemType x){
	if(L==NULL){
		return; //表空或表尾，递归结束
 }
 if(L->data!=x){
 	L=L->next;
 	delX_no_head(L,x);
 }else{
 	LinkList p=L;
 	L=L->next;
 	free(p);
 	delX_no_head(L,x);
 }
}

例2

void delX_head(LinkList &L, ElemType x){  //引用加不加无所谓，加的话免得深度拷贝

LinkList prior=L;
LinkList now=L->next;
while(now){
	if(now->data==x){
		prior->next=now->next;
		free(now);
		now=prior->next;
	}
	else{
		prior=now;
		now=now->next;
	}
}
}

例3

void printReverse(LinkList L){
	/*if(L->next==NULL){
		return;
 }else{
 	printReverse(L->next);
 	cout<<L->data; //头结点也输出？？
 }*/
 vector<ElemType> v;
 while(L->next){
 	v.push(L->next->data);
 	L=L->next;
 }

 //逆序输出
 /*reverse(v.begin(),v.end());
 vector<ElemType>::iterator it;
 for(it=v.begin();it!=v.end();it++){
 	cout<<*it;
 }*/

 vector<ElemType>::reverse_iterator rit;
 for(rit=v.rbegin();rit!=v.rend();rit++){
 	cout<<*rit;
 }

}

例4

void delMin(LinkList &L){  //引用无所谓
	LinkList min_prior=L;	//最小值的前一个
	LinkList prior=L;		//当前指针
	while(prior->next){
		if(prior->next->data<min_prior->next->data){
			min_prior=prior;  //更新指针
	 }
	 prior=prior->next;
 }
 LinkList tmp=min_prior->next;  //最小值指针
 min_prior->next=tmp->next;
 free(tmp);
}

例5

void reverse(LinkList &L){  //引用无所谓
	LinkList prior; //前一个节点
LinkList now; //当前节点
while(L->next){
	now=L->next;
	L->next=now->next;
	now->next=prior;
	prior=now;
}
L->next=now;
}

例6

//使用辅助空间
void sort_LinkList(LinkList &L){
	LinkList now=L->next;
	vector<ElemType> v;
 while(now){
		v.push_back(now->data);
		now=now->next;
 }
 sort(v.begin(),v.end());
 now=L->next;
 int i=0;
 while(now){
 	now->data=v[i++];
 	now=now->next;
 }

}

//不使用辅助空间
//已排序链则成L链
//未排序链则成p链
//分开遍历
void sort_LinkList(LinkList &L){
	LinkList pre=L;  //第一个比当前指针大的前一个节点指针
	LinkList p=L->next; //工作指针
	pre->next=NULL;   
LinkList r=p->next;
while(p){
	r=p->next;
	for(pre=L;pre->next&&pre->next->data<p->data;pre=pre->next);
	p->next=pre->next;
	pre->next=p;
	p=r;
}
}

栈

已知入栈顺序，计算出栈可能性
动规：f(n,m)表示n个待入栈，m个已入栈
f(n,m)=f(n-1,m+1)+f(n,m-1)表示当前状态只会出现两种情况：
①一个进栈
②一个出栈
二者取其一
结束条件：
n=0,f=1;
m=0,f(n,m)=f(n-1,1); //只能入栈，不能出栈

int popStackResult(int n,int m){
    if(n==0){
      return 1;
    }
    if(m=0){
      return f(n-1,1);
    }
    return f(n-1,m+1)+f(n,m-1);
}

P67

例3

#include<string>
bool isLegal(char str[]){
	int i=0;
	int sum=0;
	int len=strlen(str);
	while(sum>=0&&i<len){
		if(str[i]=='I'){
			sum++;
		}else{
			sum--;
		}
		i++;
	}
	if(i==len&&sum==0){
		return true;
	}else{
		return false;
	}
}

例4

#include<vector>
bool isSymmetric(LinkList L, int n){
	int mid=n/2;
	bool isEven=(n%2==0);
	vector<char> v;
	int i=0,j=0;
	while(L->next&&i<mid){   //记录中心节点前所有元素
		L=L->next;
		v.push_back(L->data);
		i++;
	}
	if(!isEven){ //表长不为偶数
		L=L->next;  //跳过中心节点
	}
	while(L->next){     //比较中心节点后所有元素是否与之前的元素对称
		L=L->next;
		if(v[--i]!=L->data){
			return false;
		}
	}
	return true;
}

例5

const int MaxSize=20;
typdef int ElemType;
typedef struct ComStack{
	ElemType stack[MaxSize];
	int top[2];
}ComStack;

bool push(ComStack s,int i, ElemType x){
	//左栈栈顶top0，右栈栈顶top1
	//top0初始-1，top1初始MaxSize
	if(s.top[1]-s.top[0]==1){
		return false; //栈满返回
	}
	if(i!=0||i!=1){
		return false;  //栈号错误
	}
	switch(i){
		case 0:
			s.stack[++top[0]]=x;
			break;
		case 1:
			s.stack[--top[1]]=x;
			break;
		default:break;
	}
	return true;
}

bool pop(ComStack s,int i, ElemType &e){
	if(i!=0||i!=1){
		return false;  //栈号错误
	}
	if(s.top[i]==-1||s.top[i]==MaxSize){
		return false;  //栈空，无法pop
	}
	switch(i){
		case 0:
			e=s.stack[s.top[0]--];
			break;
		case 1:
			e=s.stack[s.top[0]++];
			break;
	}
	return true;
}

队列

P78

例1

typedef int ElemType;
const int MaxSize=20;
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
	bool tag;
}ReQueue;
bool push(ReQueue &Q,ElemType e){
	if(Q.front==Q.rear&&tag==1){
		return false; //队满
	}
	Q.data[Q.rear]=e;
	Q.rear=(Q.rear+1)%MaxSize;
	if(Q.rear==Q.front){
		tag=1;    //队满
	}
	return true;
}
bool pop(ReQueue &Q, ElemType &e){
	if(Q.front==Q.rear&&tag==0){
		return false; //队空
	}
	e=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	if(Q.front==Q.rear){
		tag=0;  //队空
	}
	return true;
}

例2

#include<queue>
#include<stack>
typedef int ElemType;
void reverseQ(queue<ElemType> &Q,stack<ElemType> S){
	while(!Q.empty()){
		S.push(Q.front());
		Q.pop();
	}
	while(!S.empty()){
		Q.push(S.top());
		S.pop();
	}
}

例3

//S1执行入队，S2执行出队
typedef int ElemType;
bool Enqueue(Stack &S1,Stack &S2, ElemType x){
	if(StackOverflow(S1)){
		if(!StackEmpty(S2)){
			return false; //队满
		}else{
			ElemType tmp;
			while(!StackEmpty(S1)){
				Pop(S1,tmp);
				Push(S2,tmp;
			}
		}
	}
	Push(S1,x);
	return true;
}
bool Dequeue(Stack &S1, Stack &S2, ElemType x){
	if(StackEmpty(S2)){
		if(StackEmpty(S1)){
			return false;//队空
		}else{
			ElemType tmp;
			while(!StackEmpty(S1)){
				Pop(S1,tmp);
				Push(S2,tmp);
			}
		}
	}
	Pop(S2,x);
	return true;
}
bool QueueEmpty(Stack S1,Stack S2){
	if(StackEmpty(S1)&&StackEmpty(S2)){
		return true;
	}
	return false;
}

栈和队列的应用

P87

例1

#include<stack>
bool isMatching(char *str){
	stack<char> s;
	int i=0;
	while(str[i]!='\0'){
		swith(str[i]){
			case '(': s.push(str[i]) break;
			case '[': s.push(str[i]) break;
			case '{': s.push(str[i]) break;
			case ']':
			{
				s.pop();
				if(s.top()！='['){
					return false;
				}
				break;
			}
			case ')':
			{
				s.pop();
				if(s.top()!='('){
					return false;
				}
			}
			case '}':
			{
				s.pop();
				if(s.top()!='{'){
					return false;
				}
			}
			default:
				i++;
				break;
		}
	}
	return true;
}

例2

#include<stack>
void adjustTrain(char *train){
	char *ch1,*ch2;
	ch1=ch2=train;
	stack<char> s;
	while(*ch1){
		if(*ch1=='H'){
			s.push(*ch1);
		}else{
			*(ch2++)=*ch1;
		}
		ch1++;
	}
	while(!s.empty()){
		*(ch2++)=s.top();
		s.pop();
	}
}

例3

#include<stack>
struct Node{
	int n;
	double val;
	Node(int nn,double xval){
		n=nn;
		val=xval;
	}
};
double P(int n,double x){
	if(n==0){
		return 1;
	}
	if(n==1){
		return 2*x;
	}
	//必须用栈
	//本来直接数组顺序走就行
	//但用栈就必须逆序进栈，才能顺序出栈
	stack<Node> s;
	for(int i=n;i>=2;i--){
		s.push(Node(i,0))
	}
	double f1=1,f2=2*x;
	while(!s.empty()){
		double tmp=2*x*f2-2*(s.top().n-1)*f1;
		f1=f2;
		f2=tmp;
		s.pop();
	}
	return f2;
}

例4

#include<queue>
typedef int ElemType;   //车辆
const int SUM=10;		//渡船容量
//q渡船
//coach客车
//truck货车
void manager(queue<ElemType> &q,queue<ElemType> &coach,queue<ElemType> &truck){
	int i=0;
	int flag=0; //客车上渡船单批次的数量
	while(i<10){
		if(!coach.empty()&&flag<4){
			q.push(coach.front());
			coach.pop();
			flag++;
		}
		if(!truck.empty()&&flag==4){
			q.push(truck.front());
			truck.pop();
			flag=0;
		}
		if(coach.empty()&&!truck.empty()){
			q.push(truck.front());
			truck.pop();
		}
		if(truck.empty()&&!coach.empty()){
			q.push(coach.front());
			coach.pop();
		}
		i++
	}

}

数组与广义表

稀疏矩阵

三元组表示的矩阵转置与乘积

#include<iostream>
using namespace std;

const int MAXSIZE=12501;
typedef int ElemType;
typedef struct{
	int i,j;
	ElemType val;
}Triple;

typedef struct{
	Triple data[MAXSIZE];
	int mu,nu,tu;
}TSMatrix;

typedef int Status;
const int OK=1;
const int ERROR=0;

Status TransporseSMatrix(TSMatrix M, TSMatrix &T){
	//将三元组M转置并以行为主序得到T
	//按列循环
	T.mu=M.nu;
	T.nu=M.mu;
	T.tu=M.tu;
	if(M.tu){

		int num=0;
		for(int col=1;col<=M.nu;col++){
			for(int pos=1;pos<=M.tu;pos++){
				if(M.data[pos].j==col){
					T.data[num].i=M.data[pos].j;
					T.data[num].j=M.data[pos].i;
					T.data[num].val=M.data[pos].val;
					num++;
				}
			}
		}
	}
	return OK;
}

/**
num[] 存储各列非零元个数
cpos[] 存储每列首非零元位置

*/
Status FastTransporseSMatrix(TSMatrix M, TSMatrix &T){
	//将三元组M转置并以行为主序得到T
	//辅助数组法O(mu*nu)
	T.mu=M.nu;
	T.nu=M.mu;
	T.tu=M.tu;
	if(M.tu){

		int num[MAXSIZE];
		int cpos[MAXSIZE];
		for(int col=1;col<=M.nu;col++) num[i]=0;
		for(int t=1;t<=M.tu;t++) ++num[M.data[t].j];

		cpos[1]=1;
		for(int col=2;col<=M.nu;col++) cpos[col]=cpos[col-1]+num[col-1];
		for(int t=1;t<M.tu;t++){
			int col=M.data[t].j;
			T.data[cpos[col]].i=M.data[t].j;
			T.data[cpos[col]].j=M.data[t].i;
			T.data[cpos[col].val=M.data[t].val;
			cpos[col]++;
		}

	}

	return OK;
}

typedef struct{
	Triple data[MAXSIZE];
	int rpos[MAXSIZE];
	int mu,nu,tu;
}RLSMatrix;

Status MultSMatrix(RLSMatrix M,RLSMatrix N, RLSMatrix &Q){
	if(M.nu!=N.mu) return ERROR;
	Q.mu=M.mu;
	Q.nu=N.nu;
	Q.tu=0;
	if(M.tu*N.tu!=0){
		for(int row=1;row<=M.mu;row++){
			int ctemp[N.nu];
			fill(ctemp,ctemp+M.nu,0);
			int rnum=0;

			if(row<M.mu) rnum=M.rpos[row+1];
			else	rnum=M.tu+1;

			for(int rp=M.rpos[row];rp<rnum;rp++){

				int brow=M.data[rp].j;
				int bnum=0;
				if(brow<N.tu) bnum=N.rpos[brow+1];
				else bnum=N.tu+1;

				for(int bp=N.rpos[brow];bp<bnum;bp++){
					int bcol=N.data[bp].j;
					ctemp[bcol]=M.data[rp].val*N.data[bp].val;
				}
			}

			bool first=false;

			for(int i=1;i<=Q.nu;i++){
				if(ctemp[i]!=0){
					Q.tu++;
					if(!first){
						first=true;
						Q.rpos[row]=Q.tu;
					}
					Q.data[Q.tu].i=row;
					Q.data[Q.tu].j=i;
					Q.data[Q.tu].val=ctemp[i];
				}
			}
		}
	}
}

二叉树

bool findCommonAncestor(SqBiTree T, int i,int j,ElemType &e){

	ifT[i]=='#'||T[j]=='#'){
		return false;
	}
	while(i!=j){
		if(i<j) j/=2;
		if(i>j) i/=2;
	}
	e=T[i];
	return true;
}

int tree_level(BiTree T){

	int front=-1,rear=-1;
	int last=0;
	BiTree Q[MaxSize];
	Q[++rear]=T;
	front++;
	int level=0;
	while(front<=rear){
		if(front->lchild)
			Q[++rear]=front->lchild;
		if(front->rchild)
			Q[++rear]=front->rchild;
		if(front==last){
			level++;
			last=rear;
		}
		front++;
	}
	return level;		
}

struct Node{
	int f; //父节点索引
	BiTree node;
};

void find_all_fathers(BiTree T){

	Node Q[MaxSize]; //队列
	int front=-1;
	int rear=-1;
	//根结点入队列
	Q[++rear].f=front++;
	Q[rear].node=T;

	int tmp_x; //值为x的索引
	while(front<=rear){
		if(Q[front].node->data==x){
			tmp_x=front;
			break;
		}
		if(Q[front].node->lchild){
			Q[++rear].f=front;
			Q[rear].node=Q[front].node->lchild;
		}
		if(Q[front].node->rchild){
			Q[++rear].f=front;
			Q[rear].node=Q[front].node->rchild;
		}
		front++;
	}
	while(tmp_x!=-1){
		cout<<Q[tmp_x].node->data;
		tmp_x=Q[tmp_x].f;
	}

}

bool find_all_fathers(BiTree T,int x){
	if(T){

		if(T->data==x){
			return true;
		}
		if(find_all_fathers(T->lchild,x)||find_all_fathers(T->rchild,x)){
			cout<<T->data;
			return true;
		}
		return false;

	} else{
		return false;
	}
}

bool similar(BiTree A, BiTree B){
	if(A==NULL&&B==NULL){
		return true;
	}else if((A!=NULL&&B==NULL)||(A==NULL&&B!=NULL)){
		return false;
	}else{
		/*if(similar(A->lchild,B->lchild)){
			return similar(A->rchild,B->rchild);
		}else{
			return false;
		}*/
		return similar(A->lchild,B->lchild)&&similar(A->rchild,B->rchild);
	}
}

struct Node{
	int f;
	BiTree node;
	int length;
};
void maxPath(BiTree T){

	Node Q[MaxSize];
	int front=-1;
	int rear=-1;
	Q[++rear].f=front++;
	Q[rear].node=T;
	Q[rear].length=1;
	int length=1;
	while(front<=rear){
		Node now=Q[front];
		if(now.node->lchild){
			Q[++rear].f=front;
			Q[rear].node=now.node->lchild;
			Q[rear].length=now.length+1;
			length++;
		}
		if(now.node->rchild){
			Q[++rear].f=front;
			Q[rear].node=now.node->lchild;
			Q[rear].length=now.length+1;
			length++;
		}
		front++;
	}
	int Max=0;
	int index;
	for(int i=0;i<length;i++){
		if(Max<Q[i].length){
			Max=Q[i].length;
			index=i;
		}
	}
	while(Q[index]!=-1){
		cout<<Q[index].node->data<<endl;
		index=Q[index].f;
	}

}

int balanceBinaryTree(BiTree T,bool &flag){
	if(!T){
		return 0;
	}else{
		int left=balanceBinaryTree(T->lchild,flag);
		int right=balanceBinaryTree(T->rchild,flag);
		if(flag&&abs(left-right)>1){
			flag=false;
		}
		return max(left,right)+1;
	}
}

bool balanceBinaryTree(BiTree T, int &h){
	if(!T){
		h=0;
		return true;
	}else{
		balanceBinaryTree(T->lchild,h);
		int left=h;
		balanceBinaryTree(T->rchild,h);
		int right=h;

		h=max(left,right)+1;
		if(abs(left-right)>1){
			return false;
		}else{
			return true;
		}
	}
}

bool find_node(BiTree T,BiTree x, int h){
	if(T){
		h++;
		if(T==x){
			print(h);
			return true;
		}

		return find_node(T->lchild,x,h)||find_node(T->rchild,x,h);
	}
	return false;
}

void code(BiTree T, int h, char str[],int H){
	if(T){
		h++;
		if(h==H){
			for(int i=1;i<h;i++){
				cout<<str[i];
			}
			return;
		}
		if(T->lchild){
			str[h]='0';
			code(T->lchild,h,str,H);
		}
		if(T->rchild){
			str[h]='1';
			code(T->rchild,h,str,H);
		}
	}
}

bool JudgeSort(BiTree T){
	if(T){
		if(T->lchild){
			if(T->lchild->data>T->data){
				return false;
			}
		}
		if(T->rchild){
			if(T->rchild->data<T->data){
				return false;
			}
		}
		return JudgeSort(T->lchild)&&JudgeSort(T->rchild);
	}
	return true;
}

void deleteSame(LinkList &L){

	if(L->next==NULL){
		return;
	}
	LinkList p=L->next->next; //工作指针
	LinkList pre=L->next; //前一个指针

	while(p!=NULL){
		if(p->data==pre->data){
			pre->next=p->next;
			LinkList tmp=p;
			p=p->next;
			free(tmp);
		}else{
			pre=p;
		}
		p=p->next;
	}
}

int findNode(BiTree T,BiTree x){
	if(T){
		if(T->data==x->data){
			return 1;
		}
		if(T->data>x->data){
			return findNode(T->lchild,x)+1;
		}
		if(T->data<x->data){
			return findNode(T->rchild,x)+1;
		}
	}
	return 0;
}

void findNode(BiTree T, BiTree x,int &h){
	if(T){
		h++;
		if(T->data==x->data){
			return;
		}
		if(T->data<x->data){
			findNode(T,x,h);
			return;
		}
		if(T->data>x->data){
			findNode(T,x,h);
			return;
		}
	}
	return;
}

void PreOrderTraverse(BiTree T){

	InitStack(s);
	BiTree p=T;
	whie(p||!StackEmpty(s)){
		if(p){
			visit(p);
			if(p->rchild){
				Push(s,p->rchild);
			}
			p=p->lchild;
		}else{
			Pop(s,p);
		}
	}
}

void InOrderTraverse(BiTree T){

	InitStack(s);
	BiTree p=T;
	while(p||!StackEmpty(s)){
		if(p){
			Push(s,p);
			p=p->lchild;
		}else{
			Pop(s,p);
			visit(p);
			p=p->rchild;
		}
	}
}

void PostOrderTraverse(BiTree T){

	InitStack(s);
	BiTree p=T;
	BiTree pre=NULL;
	Push(s,p);
	while(p||!StackEmpty(s)){
		GetTop(s,p);
		if((!p->lchild&&!p->rchild)||(pre!=NULL&&(pre==p->lchild||pre==p->rchild))){
			visit(p);
			pre=p;
			Pop(s,p);
		}else{
			if(p->rchild){
				Push(s,p->rchild);
			}
			if(p->lchild){
				Push(s,p->lchild);
			}
		}
	}
}

void buildTree(ElemType A[],ElemType B[],BiTree &T,int aLeft,int aRight,int bLeft,int bRight){
	T=(BiTree)malloc(sizeof(BNode));
	T->data=A[aLeft];
	//找对应B的位置
	int loc;
	for(loc=bLeft;loc<=bRight;loc++){
		if(A[aLeft]==B[loc]) break;
	}
	int lLen=loc-bLeft;
	int rLen=bRight-loc;
	if(lLen!=0){
		buildTree(A,B,T->lchild,aLeft+1,aLeft+lLen,bLeft,loc-1);
	}
	if(rLen!=0){
		buildTree(A,B,T->rchild,aLeft+lLen+1,aRight,loc+1,bRight);
	}
}

int count=0;
bool findK(BiTree T,int k,ElemType &result){
	if(T){
		count++;
		if(count==k){
			result=T->data;
			return true;
		}
		return findK(T->lchild,k result)||findK(T->rchild,k,result);
	}
	return false;
}

void deleteX(BiTree &T, ElemType x){
	if(T){
		if(T->data=x){
			InitQueue(Q);
			EnQueue(Q,T)
			while(!QueueEmpty(Q)){
				DeQueue(Q,T);
				if(T->lchild){
					EnQueue(T->lchild);
				}
				if(T->rchild){
					EnQueue(T->rchild);
				}
				free(T);
			}
		}else{
			deleteX(T->lchild,x);
			deleteX(T->rchild,x);
		}
	}
}

const int MAX_SIZE=100;
struct Node{
	int f;
	BiTree node;
};
void fathers(BiTree T,ElemType x){
	Node Q[MAX_SIZE];
	int front=-1;
	int rear=-1;
	Q[++rear].node=T;
	Q[rear].f=front++;
	BiTree tmp;
	while(front<=rear){
		tmp=Q[front].node;
		if(tmp->data==x){ //找到值为x的节点
			break;
		}
		if(tmp->lchild){
			Q[++rear].f=front;
			Q[rear].node=tmp->lchild;
		}
		if(tmp->rchild){
			Q[++rear].f=front;
			Q[rear].node=tmp->rchild;
		}
		front++;
	}
	front=Q[front].f;
	while(front>-1){
		visit(Q[front].node);
		front=Q[front].f;
	}

}

const int MAX_SIZE=100;
struct Node{
	int f;
	BiTree node;
};

BiTree findCommonFather(BiTree Root, BiTree p,BiTree q){

	Node Q[MAX_SIZE];
	int front=-1;
	int rear=-1;
	Q[++rear].f=front++;
	Q[rear].node=Root;
	BiTree tmp;
	int pIndex,qIndex;
	while(front<=rear){
		tmp=Q[front].node;
		if(tmp==p){
			pIndex=front;
		}
		if(tmp==q){
			qIndex=front;
		}
		if(tmp->LLINK){
			Q[++rear].f=front;
			Q[rear].node=tmp->LLINK;
		}
		if(tmp->RLINK){
			Q[++rear].f=front;
			Q[rear].node=tmp->RLINK;
		}
		front++;
	}
	while(pIndex!=qIndex){
		if(pIndex>qIndex){
			pIndex=Q[pIndex].f;
		}else{
			qIndex=Q[qIndex].f;
		}
	}
	return Q[pIndex].node;
}

struct Node{
	int h;
	BiTree node;
};
int treeWidth(BiTree T){
	Node Q[MAX_SIZE];
	int front=0;
	int rear=-1;
	Q[++rear]=T;
	Q[rear].h=1;
	BiTree tmp;

	int nowH=1;
	int Width=0;
	int count=0;
	while(front<=rear){
		tmp=Q[front].node;

		if(nowH==Q[front].h){  //计算宽度
			count++;
			if(count>Width){
				Width=count;
			}
		}else{
			count=1;
			nowH=Q[front].h;
		}

		if(tmp->lchild){
			Q[++rear].node=tmp->lchild;
			Q[rear].h=Q[front].h+1;
		}
		if(tmp->rchild){
			Q[++rear].node=tmp->rchild;
			Q[rear].h=Q[front].h+1;
		}
		front++;
	}
	/*front=0;
	int Width=0;
	int nowH=1;
	int count=0;
	while(front<=rear){
		if(Q[front].h==nowH){
			count++;
			if(count>Width){
				Width=count;
			}
		}else{

			nowH=Q[front].h;
			count=1;
		}
	}*/
	return Width;
}

bool judge(BiTree A, BiTree B){
	if(A==NULL&&B==NULL){
		return true;
	}else if(A!=NULL||B!=NULL){
		return false;
	}else{
		return judge(A->lchild,B->lchild)&&judge(A->rchild,B->rchild);
	}
}

void buildLink(BiTree T, BiTree &head, BiTree pre){
	if(T){
		if(T->lchild==NULL&&T->rchild==NULL){
			if(pre==NULL){
				head=T;
				pre=T;
			}else{
				pre->rchild=T;
				pre=T;
			}
		}
		buildLink(T->lchild,head,pre);
		buildLink(T->rchild,head,pre);
	}
}

void findKNode(BiTree T, int &x,int k){
	if(T){
		x++;
		if(x==k){
			visit(T->data);
		}
		if(x<k){
			findKNode(T->lchild,x,k);
		}
		if(x<k){
			findKNode(T->rchild,x,k);
		}
	}
}