树的遍历和二叉搜索树（自）

一、树的三种遍历

1、先序遍历：根左右

2、中序遍历：左根右

3、后序遍历：左右根

代码模板：

#include<iostream>

using namespace std;

int tree[10]={0,1,2,3,4,5,6,7,8,9};//从0开始存，要是从1开始存，左儿子就是2*x，右儿子就是2*x+1 

void xianxu(int x)//根左右 
{
	if(x>=10)
		return ;
	printf("%d ",tree[x]);//根 
	xianxu(2*x+1);//左 
	xianxu(2*x+2);//右 
}

void zhongxu(int x)//左根右 
{
	if(x>=10)
		return ;
	zhongxu(2*x+1);//左 
	printf("%d ",tree[x]);//根
	zhongxu(2*x+2);//右	
} 

void houxu(int x)//左右根 
{
	if(x>=10)
		return ;
	houxu(2*x+1);//左 
	houxu(2*x+2);//右
	printf("%d ",tree[x]);//根
}

int main()
{
	xianxu(0);
	printf("\n");
	zhongxu(0);
	printf("\n");
	houxu(0); 
	return 0;	
} 

二、二叉搜索树

1、思路

2、代码模板：

#include<iostream>
#include<cstring>
using namespace std;

int tree[1000];//从1开始 
int sum=0;

void insert(int val)//插入一个值 
{
	int idx=1;
	while(tree[idx]!=-1)//值为0代表为空位置，代表找到了该放的位置，就结束 
	{
		if(tree[idx]>val)//如果val小于当前节点，往左儿子走 
			idx=idx*2;
		else
			idx=idx*2+1;//如果val大于当前节点，往右儿子走 
	}
	tree[idx]=val;//在该点记录值x 
}
void find(int x)//查找值为x的位置 
{ 
	int idx=1;//树从1开始 
	while(tree[idx]!=x&&idx<=1000)//当没找到或者 
	{
		if(tree[idx]>x)//当x小于节点时，往左儿子走 
			idx=idx*2;
		else 
			idx=idx*2+1;//当x大于节点时，往右儿子走 
	}
	if(tree[idx]==-1)
		cout<<"查找失败！"<<endl;
	else
		cout<<"该值的节点为："<<idx<<endl;
}
void Delete(int x)//节点的编号为x 
{
	if(tree[x*2]!=-1)//先把左节点移上来
	{  
		tree[x]=tree[x*2]; 
		Delete(x*2);//继续遍历左子树 
	}
	else if(tree[x*2+1]!=-1)//左节点没有值，判断右节点有没有值，右节点有值则移上来 
	{
		tree[x]=tree[x*2+1];
		Delete(x*2+1);//继续遍历右子树 
	}
	else//如果没有左右儿子，就直接删掉 
		tree[x]=-1;
}

void zhongxu(int x)//左根右 
{
	if(tree[x]==-1)
		return ;
	zhongxu(2*x);//左 
	printf("%d ",tree[x]);//根
	zhongxu(2*x+1);//右	
} 

int n,x;//n个点 

int main()
{
	memset(tree,-1,sizeof tree);
	cin>>n;
	while(n--)
	{
		cin>>x;
		insert(x);
	}
	for(int i=1;i<=20;i++)
		cout<<tree[i]<<" "; 
	cout<<endl;
	zhongxu(1);
	return 0;
}
/*
8
5 3 4 1 7 8 2 6
*/