考研算法题练习2022.11.13

1. 设计判断两个二叉树是否相同的算法。

	typedef struct BiTNode{
		int data;
		struct BiTNode *lchild,*rchild; 
	}BiTNode,*BiTree;
	bool EqualsTree(BiTree a,BiTree b){
		if(a==NULL&&b==NULL)return true;
		else if(a==NULL||b==NULL||a->data!=b->data)return false;
		//当左右子树不同时为空，或者data值不相等，则说明树不相同 
		else return EqualsTree(a->lchild,b->lchild)&&EqualsTree(a->rchild,b->rchild);
		//递归判断左右子树是否相同 
	}

1
2
3
4
5
6
7
8
9
10
11
12

2． 设计两个有序单链表的合并排序算法。

void merge(LinkList a,LinkList b,LinkList &c){
	LNode *p=a->next,*q=b->next;
	while(p&&q){
		if(p->data>q->data){//此处要根据所给序列是升序还是降序判断
			Insert(c,p->data);
			p = p->next;
		}else {
			Insert(c,q->data);
			q = q->next;
		}
	}
	while(p){Insert(c,p->data);p=p->next;}
	while(q){Insert(c,q->data);q=q->next;}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14