1.二叉树

1.1二叉树的创建和遍历

#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
	int data;
	node* ltree;
	node* rtree;
};
void Creat(node*& t)
{
	t=(struct node*)malloc(sizeof(struct node));
	cin>>t->data;
	if(t->data==0)
	{
		t=NULL;return;
	}
	Creat(t->ltree);
	Creat(t->rtree);
	return ;
}
void Front(node* t)
{
	while(t)
	{
		cout<<t->data<<" ";
		Front(t->ltree);
		Front(t->rtree);
		break;
	}
}
void Mid(node* t)
{
	while(t)
	{
		Mid(t->ltree);
		cout<<t->data<<" ";
		Mid(t->rtree);
		break;
	}
}
void Behind(node* t)
{
	while(t)
	{
		Behind(t->ltree);
		Behind(t->rtree);
		cout<<t->data<<" ";
		break;
	}
}
int main()
{
	node* T;
	Creat(T);
	Front(T);cout<<endl;
	Mid(T);cout<<endl;
	Behind(T);
}

1.2二叉树查找节点及父节点

#include<iostream>
#include<stdlib.h>
#include<queue>
using namespace std;
struct node{
	int data;
	node* ltree;
	node* rtree;
};
void create(node*& t)
{
	t=(struct node*)malloc(sizeof(struct node*));
	cin>>t->data;
	if(t->data==0)
	{
		t=NULL;
		return;
	}
	create(t->ltree);
	create(t->rtree);
}
int zishu(node* t,int p)
{
	queue<node*>q;
	q.push(t);
	node* fr;
	if(t->data==p)
	{
		return 0;
	}
	while(!q.empty())
	{
		fr=q.front();
		q.pop();
		if(fr->ltree!=NULL)
		{
			if(fr->ltree->data==p)return fr->data;
			q.push(fr->ltree);
		}
		if(fr->rtree!=NULL)
		{
			if(fr->rtree->data==p)return fr->data;
			q.push(fr->rtree);
		}
	}
	return 0;
}
int main()
{
	node* t;
	create(t);
	int n,i,p,num;
	cin>>n;
	while(n--)
	{
		cin>>p;
		num=zishu(t,p);
		cout<<num<<endl;
	}
	return 0;
}

1.3二叉树路径和

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 100+1;
vector<int> ans; // 储存最大路径和路径
struct Node
{
	int val;
	Node *left,*right;
};
void create(Node *&T)
{
	int c;
	cin >> c;
	if(c == 0)T = nullptr;
	else 
	{
		T = new Node();
		T->val = c;
		create(T->left);
		create(T->right);
	}
}
void solve(Node *T,int sum,int &res,vector<int> &v) // sum为当前路径和  res为已知最大路径和   v为当前路径
{	
	if(T)
	{   //处理根结点
		sum += T->val; 
		v.push_back(T->val);  
		if(sum > res)   //如果更优则更新
		{
			ans = v;
			res = sum;
		}
		solve(T->left,sum,res,v);   //递归左子树
		solve(T->right,sum,res,v);  //递归右子树
		v.pop_back();   //左右子树递归结束，说明以这个结点出发的所有路径全部遍历完毕，从路径中去除它，寻找其他路径
	}
}
int main()
{	
	Node *T = nullptr;
	create(T);
	int res = 0;
	vector<int> v;
	solve(T,0,res,v);
	cout << res << endl;
	for(int i=0;i<ans.size();i++)cout << ans[i] << " ";
	cout << endl;
	system("pause");
}

1.4二叉树删除子树

#include<iostream>
#include<stdlib.h>
#include<queue>
using namespace std;
struct node{
	int data;
	node* ltree;
	node* rtree;
};
void create(node*& t)
{
	t=(struct node*)malloc(sizeof(struct node*));
	cin>>t->data;
	if(t->data==0)
	{
		t=NULL;
		return;
	}
	create(t->ltree);
	create(t->rtree);
}
int zishu(node* t,int p)
{
	int flag=1;
	queue<node*>q;
	q.push(t);
	node* fr;
	while(!q.empty())
	{
		fr=q.front();
		q.pop();
		if(fr->ltree!=NULL)
		{
			if(fr->ltree->data==p)
			{
				fr->ltree=NULL,flag=0;break;
			}
			else q.push(fr->ltree);
		}
		if(fr->rtree!=NULL)
		{
			if(fr->rtree->data==p)
			{
				fr->rtree=NULL,flag=0;break;
			}
			else q.push(fr->rtree);
		}
	}
	return flag;
}
void Mid(node* t)
{
	while(t)
	{
		Mid(t->ltree);
		cout<<t->data<<" ";
		Mid(t->rtree);
		break;
	}
}
int main()
{
	node* t;
	create(t);
	int n,i,p,num;
	cin>>n;
	while(n--)
	{
		cin>>p;
		num=zishu(t,p);
		if(!num)
		{
			Mid(t);cout<<endl;
		}
		else cout<<"0"<<endl;
	}
	return 0;
}

2.二叉搜索树

2.1二叉搜索树建树

#include <iostream>
#include<cstdlib>
using namespace std;
struct Node{
    int data;
    Node * left;
    Node * right;
};
typedef Node* Tree;
Tree insert(Tree &BT,int x){//创建树
    if(!BT){
        BT=(Tree)malloc(sizeof(struct Node));
        BT->data=x;
        BT->left=BT->right=NULL;
    }
    else if(x<BT->data)
        BT->left=insert(BT->left,x);
    else if(x>BT->data)
        BT->right=insert(BT->right,x);
    return BT;
}
int main(){
    int n,l,x;
    while(cin>>n&&n){
        cin>>l;
        Tree BT=NULL;
        for(int i=0;i<n;i++){
            cin>>x;
            BT=insert(BT,x);
        }
    }
    return 0;
}

2.2判断是否同一棵二叉搜索树

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* left;
    Node* right;
};
typedef Node* Tree;
Tree insert(Tree BT,int x){//创建树
    if(!BT){
        BT=(Tree)malloc(sizeof(struct Node));
        BT->data=x;
        BT->left=BT->right=NULL;
    }
    else if(x<BT->data)BT->left=insert(BT->left,x);
    else if(x>BT->data)BT->right=insert(BT->right,x);
    return BT;
}
bool check(Node* t1,Node* t2)
{
	if(t1==NULL&&t2==NULL)return true;
	if((t1!=NULL&&t2==NULL)||(t1==NULL&&t2!=NULL)||(t1->data!=t2->data))return false;
	else return (check(t1->left,t2->left)&&check(t1->right,t2->right));
}
int main(){
	int n,m,x;
    while(cin>>n&&n)
	{
		cin>>m;
        Tree BT=NULL;
        for(int i=0;i<n;i++){
            cin>>x;
            BT=insert(BT,x);
        }
        while(m--)
        {
        	Tree BT2=NULL;
        	for(int i=0;i<n;i++)
			{
	            cin>>x;
	            BT2=insert(BT2,x);
        	}
        	if(check(BT,BT2))cout<<"Yes"<<endl;
        	else cout<<"No"<<endl;
		}
    }
    return 0;
}