二叉树的构造（C++）

╰半夏微凉° 2024-04-17 05:52 51阅读 0赞

已知先序序列（preorder）和中序序列（inorder），构造出的二叉树是唯一的。

已知后序序列（postorder）和中序序列（inorder），构造出的二叉树是唯一的。

先序、中序序列构造二叉树，然后先序遍历：

#include <cstdio>
    #include <vector>
    using namespace std;
    //声明结点
    struct node
    {
        int val;
        node *left;
        node *right;
    };
    //先序序列
    vector<int> pre;
    //中序序列
    vector<int> in;
    int n;
    bool flag=false;
    //构造二叉树
    node *build(int preindex,int instart,int inend)
    {
        node *root=NULL;
        int i;
        int mid=-1;
        for(i=instart;i<=inend;i++)
        {
            if(pre[preindex]==in[i])
            {
                mid=i;
                break;
            }
        }
        if(mid!=-1)
        {
            root=new node;
            root->val=pre[preindex];
            root->left=build(preindex+1,instart,mid-1);
            root->right=build(preindex+mid-instart+1,mid+1,inend);
        }
        return root;
    }
    //先序遍历二叉树
    void traversal(node *root)
    {
        if(root==NULL)
            return;
        if(flag)
            printf(" ");
        printf("%d",root->val);
        flag=true;
        traversal(root->left);
        traversal(root->right);
    }
    int main()
    {
        scanf("%d",&n);
        int i;
        int t;
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            pre.push_back(t);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            in.push_back(t);
        }
        node *root=build(0,0,n-1);
        traversal(root);
        printf("\n");
        return 0;
    }

**先序、中序序列构造二叉树的函数只需要传入3个参数，先序序列当前的下标preindex、在中序序列中查找范围的下界和上界。以先序序列当前的元素pre\[preindex\]为参照，找到其在中序序列指定范围内的位置，将该位置的下标设为mid，这样****中序序列指定范围就被分成了两段，mid之前构造左子树，mid之后构造右子树****，利用递归最终形成二叉树。**

后序、中序序列构造二叉树，然后层次遍历：

#include <cstdio>
    #include <vector>
    #include <queue>
    using namespace std;
    //声明结点
    struct node
    {
        int val;
        node *left;
        node *right;
    };
    //后续序列
    vector<int> post;
    //中序序列
    vector<int> in;
    //用于层次遍历的队列
    queue<node *> que;
    //结点数
    int n;
    node *build(int postindex,int instart,int inend)
    {
        node *root=NULL;
        int i;
        int mid=-1;
        for(i=instart;i<=inend;i++)
        {
            if(post[postindex]==in[i])
            {
                mid=i;
                break;
            }
        }
        if(mid!=-1)
        {
            root=new node;
            root->val=post[postindex];
            root->right=build(postindex-1,mid+1,inend);
            root->left=build(postindex-(inend-mid)-1,instart,mid-1);
        }
        return root;
    }
    int main()
    {
        scanf("%d",&n);
        int i;
        int t;
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            post.push_back(t);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            in.push_back(t);
        }
        //生成二叉树
        node *root=build(n-1,0,n-1);
        que.push(root);
        bool flag=false;
        //层次遍历
        while(!que.empty())
        {
            node *now=que.front();
            que.pop();
            if(flag)
                printf(" ");
            printf("%d",now->val);
            if(now->left!=NULL)
            {
                que.push(now->left);
            }
            if(now->right)
            {
                que.push(now->right);
            }
            flag=true;
        }
        printf("\n");
        return 0;
    }

**后序、中序序列构造二叉树的函数也只需要传入3个参数，后续序列当前的下标postindex、在中序序列中查找范围的下界和上界。以后后序序列当前的元素post\[postindex\]为参照，找到其在中序序列指定范围内的位置，将该位置的下标设为mid，这样****中序序列指定范围就被分成了两段，mid之后构造右子树，mid之前构造左子树****，利用递归最终形成二叉树。**

**需要注意的是，无论是先序、中序序列构造二叉树还是后序、中序序列构造二叉树，最关键的一步都是找根，只有根可以将下面的结点分为左子树和右子树。这就是为什么用后序、中序序列构造二叉树时最开始传入函数的postindex是后序序列的最后一个元素的下标，因为最后一个元素是根。**

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/8657865aef354bc1b90afafb3341991e.jpg