二叉树的遍历问题

二叉树的存储结构

struct node
{
	int data;
	node *lchild,*rchild;
};

二叉树的先序遍历

#include<iostream>
using namespace std;
void Preorder(node *root)
{
	if(root==nullptr) return;
	cout<<root->data<<endl;
	Preorder(root->lchild);
	Preorder(root->rchild);
};

二叉树的中序遍历

#include<iostream>
using namespace std;
void Inorder(node *root)
{
	if(root==nullptr) return;
	Inorder(root->lchild);
	cout<<root->data<<endl;
	Inorder(root->rchild);
}

二叉树的后序遍历

#include<iostream>
using namespace std;
void Postorder(node *root)
{
	if(root==nullptr) return;
	Postorder(root->lchild);
	Postorder(root->rchild);
    cout<<root->data<<endl;
}

二叉树的层序遍历

#include<queue>
#include<iostream>
using namespace std;
void Levelorder(node *root)
{
	queue<node*> q;
    q.push(root);
    while(!q.empty())
    {
        node *tmp=q.front();
        q.pop();
        cout<<tmp->data<<endl;
        if(tmp->lchild) q.push(tmp->lchild);
        if(tmp->rchild)	q.push(tmp->rchild);
    }
}

由二叉树的先序序列与中序序列创建二叉树

const int maxn=xxx;		//序列最大长度依照需求定义
int pre[maxn],in[maxn];
node* create_pre_in(int prel,int prer,int inl,int inr)
{
	if(prel>prer) return nullptr;	//若序列区间为空，返回空指针
	node *root=new node;
    root->data=pre[prel];	//先序遍历首元素即为根节点
    int k;
    for(k=inl;in[k]!=pre[prel];k++)		//找到中序序列中根节点的索引（索引左边序列构成左子树，右边构成右子树）
        ;
   	root->lchild=create_pre_in(prel+1,prel+k-inl,inl,k-1);	//递归构建左右子树（确定子问题的区间即可）
    root->rchild=create_pre_in(prel+k-inl+1,prer,k+1,inr);
    return root;
}

由二叉数的后续序列与中序序列创建二叉树

const int maxn=xxx;
int post[maxn],in[maxn];
node* create_post_in(int postl,int postr,int inl,int inr)
{
    if(posl>postr) return nullptr;
    node *root=new node;
    root->data=post[postr];
    int k;
    for(k=inl;in[k]!=post[postr];k++)
        ;
   	root->lchild=create_post_in(postl,postl+k-inl-1,inl,k-1);
    root->rchild=create_post_in(post+k-inl,postr-1,k+1,inr);
    return root;
}

由二叉树的层序序列与中序序列创建二叉树

const int maxn=xxx;
node* create_level_in(int len,int *level,int *in)
{
	if(!len) return nullptr;
    node *root=new node;
    root->data=level[0];
    int k,len_l=0,len_r=0,level_l[maxn],level_r[maxn];
    for(k=0;in[k]!=level[0];k++)
        ;
   	for(int i=0;i<len;i++)
    {
        for(int j=0;j<k-1;j++)
        {
            if(in[j]==level[i])
            {
                level_l[len_l++]=in[j];
                break;
			}
        }
        for(int j=k+1;j<len;j++)
        {
            if(in[j]==level[i])
            {
                level_r[len_r++]=in[j];
                break;
            }
        }
    }
    root->lchild=create_level_in(len_l,level_l,in);
    root->rchild=create_level_in(len_r,level_r,in+k+1);
    return root;
}