求先序排列

方法：不重构二叉树，直接输出前序排列

在某些大佬思路中，他们用二叉链表作存储结构重构二叉树，在通过对其进行先序遍历输出先序排列。但重构这一步其实是多余的。或者说，如果要通过递归来对二叉树进行先序遍历的话，就必须要重构二叉树（使用数组或二叉链表来存储二叉树的结构）。

但是我们知道，先序遍历的遍历顺序是根结点、左子树、右子树，而子树的后序排列的末尾元素是该子树的父结点，在知道了父结点元素后，可以在中序排列中分离出该父结点的左子树和右子树。知道了左子树和右子树的两个排列后，又可以分离出左子树和右子树的根（注意：结点的子树的根为该结点的孩子结点），不断递归地执行下去，直到分离出所有的结点。

所以对于此题，更优化的思路是不重构二叉树（即不使用任何数据结构存储二叉树的结构），通过题目输入的两个排列，不断地分离出二叉树的结点、结点的左子树以及父结点的右子树，直到分离出所有的结点。

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct node//node表示树的结点
{
    char data;//data意为数据域
    struct node *left_child;//left_child意为左子树的父结点
    struct node *right_child;//right_child意为右子树的父结点
};

//inorder为当前子树的中序排列首元素的地址,postorder为当前子树后序排列末尾元素的地址,length为当前子树的排列长度
int preorder_traversal(char *inorder,char *postorder,int length)
{
    char *border=inorder,*t=inorder;
    int left_length=0,right_length=0;
    printf("%c",*postorder);//输出父结点
    if(length==1)//若当前父结点没有左右子树
    {
        return 0;
    }
    while(*border!=*postorder)
    {
        border++;
    }
    left_length=(int)(border-t);//left_length为当前父结点的左子树的排列长度
    right_length=length-1-left_length;//right_length为当前结点的右子树的排列长度
    if(left_length>0)
    {
        preorder_traversal(inorder,postorder-1-right_length,left_length);//遍历左子树
    }
    if(right_length>0)
    {
        preorder_traversal(inorder+1+left_length,postorder-1,right_length);//遍历右子树
    }
    return 0;
}

int main()
{   //preorder为先序序列,inorder为中序序列,postorder为后序序列
    int length;
    char inorder_sequence[20],postorder_sequence[20],b;
    //输入数据
    scanf("%s%c",inorder_sequence,&b);
    scanf("%s%c",postorder_sequence,&b);
    length=strlen(inorder_sequence);
    //前序遍历
    preorder_traversal(inorder_sequence,postorder_sequence+length-1,length);
    return 0;
}

欢迎加入团队