本文共 15804 字，大约阅读时间需要 52 分钟。

记录自己下半年写题目的记录。题目来自书或者网站。

知识点整理

• 平衡二叉树插入结点时速度比较慢
• 平衡二叉树的各项操作的时间复杂度为o(logn)
• 有序数组的查找性能高但删除性能低，有序链表的查找性能低但删除性能高，AVL和哈希表的查找和删除性能都高

1.一棵二叉排序树，设计算法查找两个结点之和等于给定值x的结点

1.思路一 中序遍历产生中序序列（左子树所有结点的关键字均小于根节点关键字）

typedef struct node {
   	char data;	struct node* lchild;	struct node* rchild;}btnode;void InOrder(btnode* bt, vector
   
    & order) {
   	//order:中序遍历产生的序列	InOrder(bt->lchild, order);	order.push_back(bt);	InOrder(bt->rchild, order);}bool FindSum(vector
    
     order, int x, btnode* &p1, btnode* &p2)//p1 p2传入的是引用 这样能得到和为x的结点{
   	//查找两个结点值之和等于x的p1和p2	int i = 0, j = order.size()-1;	while (i < j)	{
   		if (order[i]->data + order[j]->data == x) {
   			p1 = order[i];			p2 = order[j];			return true;		}		else if (order[i]->data + order[j]->data > x)		{
   			j--;		}		else			i++;	}	return false;}bool TwoNodeSum(btnode* bt, int x, btnode*& p1, btnode*& p2){
   	vector
     
      order;	InOrder(bt, order);	if (FindSum(order,x, p1, p2)) return true;	else return false;}
     
    
   

思路二 采用两个栈分别记录bt的左下结点和右下结点（初始状态保存根结点的左下结点和右下结点）

bool TwoNodeSum(btnode* bt, int x, btnode*& p1, btnode*& p2){
   	stack
   
    left, right;	btnode* p = bt, * q;		while (p != NULL) {
   		if (p->lchild != nullptr) {
   			left.push(p->lchild); p = p->lchild;		}		p = bt;//注意这个步骤 此后根结点再次赋给p		if (p->rchild != nullptr) {
   			right.push(bt->rchild);			p = p->rchild;		}		while (!left.empty() && !right.empty())		{
   			p1 = left.top();			p2 = right.top();			if (p1->data + p2->data > x)//找次大结点 即p2左孩子的所有右下结点进栈			{
   				q = p2;				right.pop();				if (q->lchild != NULL)				{
   					p = q->lchild;					while (p) {
   						right.push(p);						p = p->rchild;					}				}			}			else if (p1->data + p2->data < x)			{
   //找次小结点				q = p1;				left.pop();				if (q->rchild != NULL)				{
   					p = q->rchild;					while (p)					{
   						left.push(p);						p = p->lchild;					}				}			}			else return true;		}	};	return false;}
   

2.树的层次遍历

按从上到下从左到右的顺序输出各个结点的值，如果从根到某个叶节点的路径上有的结点没有在输入中给出，或者给出超过一次，应该输出-1

#include
   
    struct Node {
   	int val;	bool ifHas;//是否被赋值过	Node* left, * right;	Node() :ifHas(false), left(NULL), right(NULL) {
   };};Node* root;char s[maxn];//保存读入结点void addNode(int v, char* s) {
   	int n = strlen(s);	for (int i = 0; i < n; i++)	{
   		if (s[i] == 'L') {
   			if (root->left == NULL)			{
   				root->left = new Node();//结点不存在，建立新节点				root = root->left;			}		}		else	if (s[i] == 'R') {
   			if (root->right == NULL)			{
   				root->right = new Node();				root = root->right;			}		}		if (root->ifHas == true) continue;		root->val = v;//赋值		root->ifHas = true;//置为已经访问	}}//插入结点的操作bool bfs(vector
    
     & ans){
   	Node* temp;	queue
     
      q;	q.push(root);	while (!q.empty())	{
   		temp = q.front();		if (temp->ifHas == false) return false;//注意这个验错。如果没有被赋值过，表明输入有误		ans.push_back(q.front()->val);		q.pop();		if (temp->left)q.push(temp->left);		if (temp->right)q.push(temp->right);		return true;	} }bool read_input(){
   		Node node;	int val;	while (1)	{
   		if (scanf("%s", s) != 1) return false;		if (!strcmp("()", s)) break;//读到结尾标志，退出循环		sscanf(&s[1],"%d",&val);//s[1]是字符 &s[1]是字符串“11，LL)”		addNode(val, strchr(s, ',') + 1);	}	return true;}
     
    
   

3.一二叉排序树中的关键字由整数构成，为了查找某关键字k,会得到一个查找序列，判断一个数组a中的序列是否为该二叉排序的查找序列

//假设序列a有n个关键字，如果查找成功则a[n-1]=k,用i扫描a数组，p用于在二叉树bt中查找（p的初值指向根节点） 注意：没查找一层都比较p->key与a[i]是否相等//如果不相等 返回falsebool FindSer(Node* bt, int k, int a[], int n){
   	if (bt == NULL) return false;	if (a[n - 1] != k) return false;//先提前判断这个	Node* p = bt;	int i = 0;	while (i < n && p != NULL)	{
   		if (p->val != a[i]) return false;		if (k > p->val) p = p->right;		else if (k < p->val) p = p->right;		i++;		}	if (p != NULL) return true;	return false;}

4.求关键字分别为x,y的结点的最近公共祖先

Node* LCA(Node*bt,int x,int y){
   	{
   		if (bt == nullptr) return NULL;		if (x < bt->left->val && y < bt->left->val) return LCA(bt->left, x, y);		else if (x > bt->right->val && y > bt->right->val) return LCA(bt->right, x, y);		else return bt;//注意 如果以上两种情况都不是，则bt为最近公共结点	}

5.设计算法将二叉排序树变为有序链表，要求不能创建新结点，只修改指针

方法一：

//1.递归的方法 将二叉树bt中所有结点的左指针lchild转化为指向前驱结点，右指针转化为指向后继结点//if bt->lchild==null first = bt,if bt->rchild==null last =bt//注意需要销毁双链表void convert(Node* bt, Node*& first, Node*& last){
   	if (bt == nullptr) {
   		//空树		first = nullptr;		last = nullptr;	}	Node* lfirst, * llast, * rfirst, * rlast;//递归调用时左子树和右子树的首位指针，一共四个	if (bt->left == nullptr) first = bt;	else if (bt->left != nullptr) {
   		convert(bt->left, lfirst, llast);		first = lfirst;		bt->left = llast;		llast->right = bt;	}	if (bt->right == nullptr)last = bt;	else {
   		convert(bt->right, rfirst, rlast);		last = rlast;		bt->right = rfirst;		rfirst->left = bt;	}}void Display(Node* first, Node* last){
   	if (first != NULL) {
   		//输出转化后的双链表		while (first != last)		{
   			cout << first->val << ",";			first = first->right;		}		cout << first->val;//最后一个结点的值	}	}void destroy(Node*& L){
   	//销毁双链表	Node* pre = L, *p = pre->right;	//一个首结点 一个首结点的后继结点	while (pre->right)	{
   		free(pre);		pre = p;		p = pre->right;	}	free(pre);//注意最后还有一个结点要释放}

方法二：

Node* pre = NULL;void InOrder(Node* bt){
   	if (bt == NULL) return;	if (bt->left) {
   		InOrder(bt->left);		bt->left = pre;		pre->right = bt;	}	if (pre != NULL)pre->right = bt;	bt->left = pre;		pre = bt;	InOrder(bt->right);//递归构造右子树}void convert(Node* bt, Node*& first){
   	//转化为首结点为first的双链表	Node* p = bt;	if (p->left != NULL)	{
   		p = p->left;			}	first = p;	pre = NULL;	InOrder(bt);}int main() {
   	Node* first,*bt;	//用排序二叉树算法建树	convert(bt, first);//转化为有序单链表	//输出双链表的函数	//销毁双链表	}

6.设计算法交换二叉树b的所有左右子树要求空间复杂度为1

void swap(btnode*b){
   btnode*temp;if(b!=NULL){
   swap(b->lchild);swap(b->rchild);temp=b->lchild;b->lchild=b->rchild;b->rchild=temp;}}//基于后序遍历算法

7.设计算法交换二叉树b的所有左右子树要求不破坏原二叉树结构

btnode* swap(btnode*b){
   btnode*t,*t1,*t2;if(b==NULL)t=NULL;else{
   t=(btnode*)malloc(sizof(btnode));//复制根节点t->data=b->data;t1=swap(b->lchild);t2=swap(b->rchild);t->lchild=t2;t->rchild=t1;}return t;}

8.设计算法利用结点的右孩子指针将一棵二叉树的叶结点从左往右串成单链表

//先序遍历的方法，尾插法构建叶结点，head指向建立单链表的首结点，tail指向尾结点//head tail以引用的方式传入void link(btnode*b,btnode*&head,btnode*&tail){
   if(b!=NULL){
   if(b->lchild==NULL&&b->rchild==NULL)//叶结点{
   if(head==NULL){
   //此时为第一个叶结点head=b;tail=head;}else{
   tail->rchild=b;tail=b;}}if(b->lchild!=NULL){
   link(b->lchild,head,tail);}if(b->rchild!=NULL)link(b->rchild,head,tail);}//创建并输出叶结点构成的单链表void vreateLink(btnode*b){
   btnode*head=NULL,*tail;link(b,head,tail)//注意head一开始指向nulltail->rchild=NULL;//注意尾结点的rchild置空btnode*p=head;while(p!=NULL){
   cout<
   
    data<<",";p=p->next;}}
   

9.设计算法输出所有根结点到叶结点的路径及其路径和

void dispapath(vector
   
    path){
   vector
    
     ::iterator it;int sum=0;for(it=path.begin();it!=path.end();it++){
   sum+=*it;cout<<*it<<" ";}cout<