二叉搜索树

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

567432和543267都长这样：

二叉树的前序遍历

（给出的是二叉搜索树序列）

遍历顺序规则为【根左右】12457836

struct node
{
	char val;
	node *lch,*rch;
};
node *insert(node *p,char x)
{
    if(p==NULL)
	{
		node *p=new node;
		p->val=x;
		p->lch=p->rch=NULL;
		return p;
	}
	else
	{
		if(x<p->val)
	    p->lch=insert(p->lch,x);
	    else p->rch=insert(p->rch,x);
	    return p;
	}
}
void pre(node *h)
{
	if(h!=NULL)
	{
		printf("%c",h->val);
		pre(h->lch);
		pre(h->rch);
	}
	return;
}
int main()
{
	char a[30];
	int i;
	node *h;
	while(gets(a))
	{
		h=NULL;
		for(i=0;i<strlen(a);i++)
			h=insert(h,a[i]);
		pre(h);
		printf("\n"); 
	}
	return 0;
}

二叉树的中序遍历

（给出的是二叉搜索树序列）

遍历顺序规则为【左根右】42758136

struct node
{
	char val;
	node *lch,*rch;
};
node *insert(node *p,char x)
{
    if(p==NULL)
	{
		node *p=new node;
		p->val=x;
		p->lch=p->rch=NULL;
		return p;
	}
	else
	{
		if(x<p->val)
	    p->lch=insert(p->lch,x);
	    else p->rch=insert(p->rch,x);
	    return p;
	}
}
void in(node *h)
{
	if(h!=NULL)
	{   
	    in(h->lch);
		printf("%c",h->val);
		in(h->rch);
	}
	return;
}
int main()
{
	char a[30];
	int i;
	node *h;
	while(gets(a))
	{
		h=NULL;
		for(i=0;i<strlen(a);i++)
			h=insert(h,a[i]);
		in(h);
		printf("\n"); 
	}
	return 0;
}

二叉树的后序遍历

（给出的是二叉搜索树序列）

遍历顺序规则为【左右根】47852631

struct node
{
	char val;
	node *lch,*rch;
};
node *insert(node *p,char x)
{
    if(p==NULL)
	{
		node *p=new node;
		p->val=x;
		p->lch=p->rch=NULL;
		return p;
	}
	else
	{
		if(x<p->val)
	    p->lch=insert(p->lch,x);
	    else p->rch=insert(p->rch,x);
	    return p;
	}
}
void post(node *h)
{
	if(h!=NULL)
	{   
	    post(h->lch);
		post(h->rch);
		printf("%c",h->val);
	}
	return;
}
int main()
{
	char a[30];
	int i;
	node *h;
	while(gets(a))
	{
		h=NULL;
		for(i=0;i<strlen(a);i++)
			h=insert(h,a[i]);
		post(h);
		printf("\n"); 
	}
	return 0;
}

二叉树的层次遍历

从上到下，从左到右的顺序进行遍历。

样例输入：

(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

(3,L) (4,R) ()

样例输出：

5 4 8 11 13 4 7 2 1

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
    int v;
    bool hv;
    node *left,*right;
    node():hv(false),left(NULL),right(NULL){}
};     //设置结点
node *root;
vector<int> vec;
int flag;
void add(int va,char a[])
{
    int i;
    node *p=root;
    for(i=0;i<strlen(a);i++)
    {
        if(a[i]=='L')
        {
            if(p->left==NULL)p->left=new node;
            p=p->left;
        }
        else if(a[i]=='R')
        {
            if(p->right==NULL)p->right=new node;
            p=p->right;
        }
    }
    if(p->hv==true)flag++;
    p->v=va;
    p->hv=true;
}     //建树
void bfs()
{
    queue<node*>Q;
    vec.clear();
    Q.push(root);
    while(!Q.empty())
    {
        node *temp=Q.front();
        Q.pop();
        if(temp->hv==false)flag++;
        else
        {
            vec.push_back(temp->v);
            if(temp->left!=NULL)Q.push(temp->left);
            if(temp->right!=NULL)Q.push(temp->right);
        }
    }
}     //遍历
int input()
{
    char s[300];
    int value;
    flag=0;
    root=new node;
    while(1)
    {
        if(scanf("%s",s)!=1)return 0;
        if(strcmp(s,"()")==0)break;
        sscanf(&s[1],"%d",&value);
        add(value,strchr(s,',')+1);
    }
    return 1;
}
int main()
{
    int i;
    while(input())
    {
        bfs();
        if(flag!=0)printf("not complete\n");
        else
        {
            printf("%d",vec[0]);
            for(i=1;i<vec.size();i++)
            printf(" %d",vec[i]);
            printf("\n");
        }
    }
    return 0;
}

二叉树的递归遍历

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
struct node
{
    char val;
    node *lch,*rch;
};
node *insert(node *p,char x)
{
    if(p==NULL)
    {
        node *p=new node;
        p->val=x;
        p->lch=p->rch=NULL;
        return p;
    }
    else
    {
        if(x<p->val)
        p->lch=insert(p->lch,x);
        else p->rch=insert(p->rch,x);
        return p;
    }
}
void pre(node *p)
{
    if(p!=NULL)
    {
        printf("%c",p->val);
        pre(p->lch);
        pre(p->rch);
    }
}
void in(node *p)
{
    if(p!=NULL)
    {
        in(p->lch);
        printf("%c",p->val);
        in(p->rch);
    }
}
void post(node *p)
{
    if(p!=NULL)
    {   
        post(p->lch);
        post(p->rch);
        printf("%c",p->val);
    }
}
int main()
{
    char a[30];
    int i;
    node *h;
    while(gets(a))
    {
        h=NULL;
        for(i=0;i<strlen(a);i++)
            h=insert(h,a[i]);
        pre(h);
        in(h);
        post(h);
        printf("\n"); 
    }
    return 0;
}

已知前序、中序遍历，求后序遍历

参考博客：http://blog.csdn.net/droidphone/article/details/38063897

已知中序、后序遍历，求前序遍历

参考博客：http://blog.csdn.net/u014536527/article/details/51010702