精华内容
下载资源
问答
  • 此时已知前()序遍历和中序遍历 根据二叉树的性质,已知前()序遍历和中序遍历可以唯一的确定一颗二叉树 思路 递归思想,首先找到前序遍历节点(第一个节点),再找出该值对应在中序遍历序列的位置,...

    给定前序或后序的序列,判断该序列是否能构成一颗二叉搜索树(或镜像的二叉搜索树)

    假设能构成一颗二叉搜索树,那么这棵树的中序遍历必定为有序的序列
    此时已知前(后)序遍历和中序遍历
    根据二叉树的性质,已知前(后)序遍历和中序遍历可以唯一的确定一颗二叉树

    思路
    递归思想,首先找到前序遍历中的根节点(第一个节点),再找出该值对应在中序遍历序列中的位置,分界后分别对左右子树进行递归。

    注意:由于可能存在数值相同的节点,根据原树和镜像树的不同需要找到中序遍历中第一次出现或是最后一次出现对应的节点,具体见代码

    此算法也可用于已知前(后)序遍历和中序遍历求后(前)序遍历

    代码实现

    //此算法假定中序遍历为升序且已知前序遍历
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int n, cnt;
    int preorder[N], inorder[N], postorder[N]; //分别表示前、中、后序遍历
    
    bool build(int il, int ir, int pl, int pr, int t) //是否能建树
    {
        int root = preorder[pl]; //当前根节点的数值
        int k; //中序遍历的根节点的位置
        
        if (t == 0) //表示为原二叉搜索树
        {
            for (k = il; k <= ir; k ++ ) //找出中序遍历中第一次出现的位置
                if (root == inorder[k])
                    break;
        }
        else //镜像
        {
            for (k = ir; k >= il; k -- ) //找出中序遍历中最后一次出现的位置
                if (root == inorder[k])
                    break;
        }
        
        if (k > ir || k < il) return false; //不能在中序遍历对应的位置找出根节点的值,说明无法建树
        
        bool f = true;
        if (il < k && !build(il, k - 1, pl + 1, pl + 1 + k - 1 - il, t)) f = false; //左子树存在
        if (k < ir && !build(k + 1, ir, pr - (ir - k - 1), pr, t)) f = false; //右子树存在
        
        postorder[cnt ++ ] = root; //递归后记录的即为后序遍历
        //若是记录前序遍历,需在递归前记录
        
        return f;
    }
    
    int main()
    {
        cin >> n;
        for (int i = 0; i < n; i ++ )
        {
            cin >> preorder[i];
            inorder[i] = preorder[i];
        }
        
        sort(inorder, inorder + n); //升序排列
        
        if (build(0, n - 1, 0, n - 1, 0))
        {
            cout << "YES\n";
            cout << postorder[0];
            for (int i = 1; i < n; i ++ )
                cout << ' ' << postorder[i];
        }
        else
        {
        	//判断镜像能否建树
            reverse(inorder, inorder + n);
            cnt = 0;
            if (build(0, n - 1, 0, n - 1, 1))
            {
                cout << "YES\n";
                cout << postorder[0];
                for (int i = 1; i < n; i ++ )
                    cout << ' ' << postorder[i];
            }
            else
                cout << "NO";
        }
        return 0;
    }
    

    题目来源:PAT甲级1043 Is It a Binary Search Tree

    展开全文
  • 森林的遍历

    万次阅读 多人点赞 2016-10-15 17:23:03
    树的遍历主要有先根遍历和后根遍历。 先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 后根遍历:若树非空,则按照从左到...

    树和森林的遍历

    @(数据结构)

    不要带着二叉树的遍历来限制了对树的遍历的理解。
    树的遍历的定义:以某种方式访问树中的每一个结点,且仅访问一次。
    树的遍历主要有先根遍历后根遍历

    • 先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同

    • 后根遍历:若树非空,则按照从左到右的顺序遍历根结点的每一棵子树,之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同

    这里写图片描述

    根据这幅图:
    树的先根遍历:A-B-E-F-G-C-H-D-I-J
    对应的二叉树的先序遍历:A-B-E-F-G-C-H-D-I-J

    二者是一致的。

    树的后根遍历:E-F-G-B-H-C-I-J-D-A
    对应的二叉树的后序遍历:G-F-E-H-J-I-D-C-B-A
    对应的二叉树的中序遍历:E-F-G-B-H-C-I-J-D-A(与树的后根遍历相一致)

    注意到我们并没有定义一般树的中根遍历,因为子结点该怎么分两部分并没有定义,所以只定义先、后根。

    以上只是模拟证实。

    森林的遍历:需要澄清的是,只有二叉树森林才有中序遍历与完整二叉树中序遍历对应
    先序遍历森林。

    • 若森林非空,访问森林的第一棵树的根结点。
    • 先序遍历第一棵树中根结点的子树
    • 先序遍历除去掉遍历过的树的森林

    中序遍历森林:普通的树构成的森林是不存在中序遍历的,这里的中序遍历必然指代的是化成二叉树的森林。

    后序遍历也可以相似定义。

    这里写图片描述

    我们看这个森林和二叉树的各种遍历。

    森林的先根遍历:A-B-C-D-E-F-G-H-J-I
    二叉树森林的先序遍历:A-B-C-D-E-F-G-H-J-I(相同)
    完整二叉树的先序遍历:A-B-C-D-E-F-G-H-J-I (相同)

    森林的后根遍历:B-C-D-A-F-E-J-H-I-G
    二叉树森林的后序遍历:D-C-B-A-F-E-J-I-H-G
    完整二叉树的后序遍历:D-C-B-F-J-I-H-G-E-A(不同于二叉树森林的后序遍历)
    二叉树森林的中序遍历:B-C-D-A-F-E-J-H-I-G(与森林的后根遍历相同)
    完整二叉树的中序遍历:B-C-D-A-F-E-J-H-I-G(与森林的后根遍历相同,自然也与二叉树森林的中序遍历相同)

    2019.10 Update:

    第一届PAT算法直播课培训班招募帖,欢迎点击查看详情、

    END.

    展开全文
  • 对于后中重构,我们很容易得到右子树的,却难得到左子树的,利用上述结论,可以间接求出右子树的长度,进而确定中序遍历中,左子树的位置,进而找到后序,左子树的具体在哪 L2-006树的遍历(25分) 给定一...

    这个题是利用树的基础,来模拟人为通过后中重构树的过程

    有个小技巧在于,前中后遍历中,虽然所得结果的排序不同,但是子树所在的区域近乎相同,相差不大于1

    对于后中重构中,我们很容易得到右子树的根,却难得到左子树的根,利用上述结论,可以间接求出右子树的长度,进而确定中序遍历中,左子树的位置,进而找到后序中,左子树的根具体在哪

    L2-006 树的遍历 (25分)

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    输入格式:

    输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

    输出格式:

    在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

    输入样例:

    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
    

    输出样例:

    4 1 6 3 5 7 2
    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    #define MAXN 50
    int hind[MAXN];
    int mid[MAXN];
    int n;
    int index,lnum,rnum;
    struct node
    {
        int value;
        node *left;
        node *right;
    }*T = NULL;
    void Create(node *&R,int l,int r,int index)
    {
        if(l>r) return;
        int p;
        R = new node;
        R->value = hind[index];
        R->left = NULL;
        R->right = NULL;
        for(int i = l; i <= r; i++) if(mid[i] == hind[index]) {p = i;break;};
        Create(R->right,p+1,r,index-1);
        Create(R->left,l,p-1,index+p-r-1);
    }
    void bfs()
    {
        queue<node*> q;
        q.push(T);
        bool flag = false;
        while(!q.empty())
        {
           node* temp = q.front();
           q.pop();
           if(!flag)
           {
               flag = true;
               printf("%d",temp->value);
           }
           else printf(" %d",temp->value);
           if(temp->left) q.push(temp->left);
           if(temp->right) q.push(temp->right);
        }
    }
    int main()
    {
        cin>>n;
        for(int i = 0; i < n; i++) scanf("%d",&hind[i]);
        for(int i = 0; i < n; i++) scanf("%d",&mid[i]);
        Create(T,0,n-1,n-1);
        bfs();
        return 0;
    }
    

     

    展开全文
  • 树的遍历主要有先根遍历和后根遍历。 先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 后根遍历:若树非空,则按照从左到...

    树的遍历

    树的遍历主要有先根遍历后根遍历

    先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。

    后根遍历:若树非空,则按照从左到右的顺序遍历根结点的每一棵子树,之后再访问根结点。其访问顺序与这棵树对应的二叉树的中序遍历顺序相同。

    森林的遍历

    森林的遍历包括先序遍历中序遍历

    若森林非空:

    先序遍历

    • 访问森林的第一棵树的根结点
    • 先序遍历第一棵树中根结点的子树
    • 先序遍历除去掉遍历过的树的森林

    中序遍历

    • 中序遍历第一棵树中根结点的子树
    • 访问第一棵树的根结点
    • 中序遍历除去掉遍历过的树的森林

    总结

    树、森林、二叉树之间的遍历有对应的关系

    森林 二叉树
    先根遍历 先序遍历 先序遍历
    后根遍历 中序遍历 中序遍历

    参考

    王道2021数据结构

    树和森林的遍历

    展开全文
  • 数据结构——树森林的遍历方法

    千次阅读 2017-10-15 12:22:51
    树的遍历主要有先根遍历和后根遍历。 2、(1)先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 (2)后根遍历:若树非空...
  • 二叉树的随机生成及其遍历 张 zhaohan 10804XXXXX 2010/6/12 问题重述 利用随机函数产生 50个 ( 不大于 100且各不相同的 )随机整数用这些整数来生成一棵二叉 树分别对二叉树进行先根遍历中根遍历和后根遍历并输出树...
  • 题目 思路 先知道一个定律:从前序/后序遍历+...所以当我们知道前序遍历和中序遍历,大体思路如下: 前序遍历的第一个为节点 接着我们去中序遍历寻找节点所在位置,那么节点前面的就是左子树所有的节...
  • 后根遍历:树非空,则按照从左到右的顺序遍历根节点的每一颗子树,之后在访问根节点。其访问顺序这棵树对应的二叉树的中序遍历顺序相同。 二叉树:先序遍历,后序遍历,中序遍历       图的遍历   ...
  • 题目描述:设一棵二叉树各结点的值各不相同,其先序遍历序列中序遍历序列分别存于两个一维数组A[1...n]B[1..n],试编写算法建立该二叉树的二叉链表。 算法思想:根据二叉树的先序遍历序列中序遍历序列可以...
  • 如果在算法暂时忽略访问节点的printf语句,则3种遍历算法完全相同。因此,从递归执行的角度来看,先序、中序后序遍历是完全相同的。上图的用带箭头的虚线表示这3种遍历算法执行的过程。其中,向下的箭头表示...
  • 先序遍历-递归非递归(java版)

    千次阅读 2018-11-20 20:52:56
    根据先序遍历访问的顺序,优先访问结点,然后再分别访问左孩子右孩子。即对于任一结点,其可看做是结点,因此可以直接访问,访问完之后,若其左孩子不为空,按相同规则访问它的左子树;当访问其左子树时,再...
  • 后序遍历的序列,最后一个数字是树的节点 ,数组前面的数字可以分为两部分:第一部分是左子树节点 的值,都比节点的值小;第二部分 是右子树 节点的值,都比 节点 的值大,后面用递归分别判断前...
  • 题意:给一颗点带权(权值各不相同,都是小于10000的正整数)的二叉树的...首先我想先改变这几个遍历的名字(前根序遍历中根遍历后根遍历);前中后本来就是相对于根结点来说的,少一个字会产生很多不必要的误
  • 原理我写过的“二叉树——根据先序(后序)中序遍历建树”的原理是相同的,除了一个层序遍历,这里说明一下层序遍历的原理: 加一个变量index,表示当前的结点在二叉树所对应的下标(从1开始),所以进行...
  • 最常规的遍历是三序遍历:先、。区别在于打印节点的顺序。 先序遍历是“-左-右”,中序遍历是“左--右”,后序遍历是“左-右-”。 遍历方法有两种:递归迭代。绝大多数二叉树题目都涉及递归,递归也...
  • 二:同一个树中序遍历和后序遍历包含元素相同(顺序不同),通过中序遍历的分隔点返回后序遍历,找到左右子树的后序遍历。 两点注意事项:一个是小心笔误;第二个是找到节点,到中序遍历找到分隔点,这个分隔...
  • 1、思路举例说明:以{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是结点的值。在这个数组,前3个数字5、76都比8小,是值为8的结点的左子树结点;3个数字9、1110都比8大,是值为8的结点的右子树...
  • 分析:在二叉搜索树的后序遍历中节点在最后面。前面的序列可以分为两个部分:一个为左子树,小于节点的值;一个为右子树,大于节点的值。左子树序列右子树序列同样应该为后序遍历序列,则可以通过递归判断...
  • 题意 输入一个整数数组,判断该数组是不是某二叉...思路注意这里是二叉搜索树的后序遍历所以结点一定在后面最后一个元素,思路二叉树的重建是一样的 在后序遍历的数组找到左子树的区间右子树的区间 class So...
  • 由于二叉搜索树左子树的值都比节点小,右子树都比节点大,使用后序遍历时最后一个值为节点的值,所以确定节点遍历序列寻找第一个比节点值大的数,则该数的左边都比节点小,为左子树;右边为右子树...
  • 首先这个数组是搜索二叉树的后序遍历,因为搜索二叉树满足左小右大的规则,并且后序遍历中最后一个遍历的是节点,因此,我们能根据最后一个数字将数组分为两部分,前面的一部分都比最后一个节点小,后面的一部分都...
  • 以{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是结点的值。在这个数组,前3个数字5、76都比8小,是值为8的结点的左子树结点;3个数字9、1110都比8大,是值为8的结点的右子树结点。 ...
  • 在后序遍历序列,最后一个值是树的节点,前面一部分结点是的左子树;左子树后面,节点前面是的右子树。依次递归判断左子树右子树是不是二叉搜索树。 3、代码如下 import java.util.Arrays;
  • 区别在于,在这一题,后序遍历的最后一个值为节点。 然后仍然是找到节点,划分左右子树,递归构建。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left;...
  • 以{5,7,6,9,11,10,8}为例,后序遍历结果的最后一个数字8就是结点的值。在这个数组,前3个数字5、76都比8小,是值为8的结点的左子树结点;3个数字9、1110都比8大,是值为8的结点的右子树结点。 我们接下...
  • 1)后序数组的最后一个元素为节点,根据节点可将中序数组划分为左子树序列表右子树中序数组 2)又因为一棵树的中序数组长度与后序数组长度大小相同,所以可以根据长度划分序数组为左右子树后序数组 3)...
  • C++Builder画二叉树

    2018-07-13 16:18:50
    二、若二叉树各结点的值均不相同,则由二叉树的前根遍历序列和中根遍历序列,由其中根遍历序列和后根遍历序列均能唯一确定一颗二叉树。根据输入的中根遍历序列和前(后)根遍历序列,以动画方式画出对应的二叉树
  • 数据结构:第五章树和...一颗树的后根遍历和该树的二叉树的中根遍历相同 二叉树的先根和中根相同,则无左子孩子 二叉树的先根和中根相反,则无右孩子 二叉树采用二叉链式存储结构 树采用孩子兄弟链表存储结构 ...
  • 1.树转换为二叉树 ...当 以二叉链表作树的存储结构时,树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。   森林的遍历方法: 森林的前序遍历和二叉树的前序遍历结果相同,森...

空空如也

空空如也

1 2 3 4 5
收藏数 86
精华内容 34
关键字:

中根遍历和后根遍历相同