精华内容
下载资源
问答
  • 根据后序中序遍历序列求二叉树 中序:左、、右 后序:左、右、 直接上题: 中序:DCBGEAHFIJK 后序:DCEGBFHKJIA 第一步:还是找到老父亲节点 后序的最后一个节点:A 第二步:划分大哥二弟的家族 在中序...

    根据后序和中序遍历序列求二叉树

    中序:左、根、右
    后序:左、右、根

    直接上题:

    中序:DCBGEAHFIJK
    后序:DCEGBFHKJIA

    第一步:还是先找到老父亲节点

    后序的最后一个节点:A

    第二步:划分大哥和二弟的家族

    在中序中,老父亲节点左边的为大哥家族,右边的为二弟家族

    在这里插入图片描述

    第三步:完善细节、总结经验

    我们先看左边的节点,还是那样,找在两个序列中都挨在一起的几个节点:
    1.D、C
    2.E、G
    3.B、G

    1.先看第一个:D和C,D在先序中是第一个访问的,所以他在整个树中是最左边的那个点,他俩在中序和后序中都是同样的顺序:说明他俩一个为父亲,一个为左节点,至于为啥不是同一个父亲的两个孩子,这个想想就知道了,如果他俩有共同的父亲,那么在中序中,访问完左孩子后就应该访问父亲,但是没有。
    在这里插入图片描述

    2.再看E、G:在中序和后序中,这两个的出现顺序是相反的,那么他俩一定是父亲和右孩子,谁是父亲很好判断,在中序中,谁先出来谁是父亲
    在这里插入图片描述

    3.继续看B、G,和2相同,顺序相反,这就可以把B连上去了
    在这里插入图片描述

    我们在来看一下顺序,在中序中的顺序是BGE,后序中是EGB,连接方式就是一条右直线。可以得到结论:如果在中序和后序中多个点是在一起出现的,且顺序相反,那么他们能连成一条右直线

    大致的连接方式都画出来了,剩下的就是把他们拼在一起

    CD两个点可以确定是在最左边,接下来有两种连法,我们先试一下,再来找规律:
    一:B为C的右孩子
    在这里插入图片描述
    二:C为B的左孩子
    在这里插入图片描述

    先看一这种连接方式,满足中序的DCBGE,后序呢?DEGBC和题目不符,舍去

    那么只有二了,二的连接方式是完全符合题目的。。

    总结一下:如果两个点在中序和后序种同时出现(中间没有任何其他点),那么,作为父亲的节点只有一个孩子

    间--------------------隔---------------------------线

    左边的完成了,接下来画右边的
    同样的方法:找到在两个序列中连着出现的点
    1.I、J、K
    2.H、F

    1很容易,中序中和后序中三个点的出现顺序完全相反
    瞬间画出结果,而且还能确定很重要的一点:J只有K一个孩子
    在这里插入图片描述
    根据中序中,K是最后访问到的,所以K位于该二叉树的最右端,在后序中,I是倒数第二个访问的,所以I的老父亲A的右孩子

    在这里插入图片描述

    2.HF在两个序列中出现顺序相反
    也是直接画出结果
    在这里插入图片描述
    接下来就是把这两个连起来

    之前得到的结论,J只有K一个孩子,而K是整个树中最右边的节点,所以只能这么连:
    在这里插入图片描述
    这样一个二叉树就画完了,最后在根据二叉树写一下他的中序和后序序列验证一下结果。我比较有自尊,坚信自己是对的,就不验证了。

    展开全文
  • 根据前序遍历序列和中序遍历序列重建二叉树题目描述输入某二叉树的前序遍历中序遍历的结果,请重建出该二叉树。假设输入的前序遍历中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}...

    根据前序遍历序列和中序遍历序列重建二叉树

    题目描述

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。


    编程思路:

    1.先求出根节点(前序序列第一个元素)。
    2.将根节点带入到中序遍历序列中求出左右子树的中序遍历序列。
    3.通过左右子树的中序序列元素集合带入前序遍历序列可以求出左右子树的前序序列。
    4.左右子树的前序序列第一个元素分别是根节点的左右儿子
    5.求出了左右子树的4种序列可以递归上述步骤


    源代码(c++):

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
            //判定递归终止条件;
            if(pre.size() == 0 || in.size() == 0) {
                return NULL;
            }
            //定义Node节点并其求根节点;
            int root = pre[0];
            TreeNode* node = new TreeNode(root);
            vector<int>::iterator it;
            //1.求左右子树的遍历序列;
            vector<int> preLeft, preRight, inLeft, inRight;
                //(1).求根节点在中序遍历序列中的位置;
            vector<int>::iterator i;
            for(it = in.begin(); it != in.end(); it++) {
                if(root == *it) {
                    i = it;
                }
            }
                //(2).求左右子树的中序遍历子序列;
            int k = 0;
            for(it = in.begin(); it != in.end(); it++) {
                if(k == 0) {
                    inLeft.push_back(*it);
                }
                else if(k == 1) {
                    inRight.push_back(*it);
                }
                else {}
                if(it == i) {
                    k = 1;
                }  
            }
                //(3).求左右子树的前序遍历子序列;
            k = 0;
            vector<int>::iterator ite;
            for(it = pre.begin()+1; it != pre.end(); it++) {
                for(ite = inLeft.begin(); ite != inLeft.end(); ite++) {
                    if(*it == *ite) {
                        preLeft.push_back(*it);
                        k = 1;
                    }
                }
                if(k == 0) {
                    preRight.push_back(*it);
                }
                k = 0;
            }
            //根据遍历序列求出跟的左右节点;
            node->left = reConstructBinaryTree(preLeft,inLeft);
            node->right = reConstructBinaryTree(preRight,inRight);
            //返回节点地址;
            return node; 
        }
    };
    展开全文
  • 文章目录题目解答 题目 已知: 前序 1,2,4,7,3,5,6,8 中序 4,7,2,1,5,3,8,6 ...重新构建一颗二叉树 ...因为前序的第一个就是节点,所以...出两个序列中,左子树的范围右子树的范围 参考: 重建二叉树 ...

    文章目录

    题目

    已知:
    前序 1,2,4,7,3,5,6,8
    中序 4,7,2,1,5,3,8,6

    要求:
    重新构建一颗二叉树

    解答

    因为前序的第一个就是根节点,所以先找到根节点在中序中的位置
    在这里插入图片描述求出左子树的长度,确定左子树在前序和中序中的范围,以及右子树在前序和中序中的范围

    在这里插入图片描述求出两个序列中,左子树的范围和右子树的范围
    在这里插入图片描述

    class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
            return pre_order(0, vin.size() - 1, 0, vin.size() - 1, pre, vin);
        }
    
        TreeNode *pre_order(int leftpre, int rightpre, int leftin, int rightin, vector<int> &pre, vector<int> &in) {
            if (leftpre > rightpre || leftin > rightin)
                return NULL;
            TreeNode *root = new TreeNode(pre[leftpre]);
            int rootin = leftin;
            while (rootin <= rightin && pre[leftpre] != in[rootin])
                rootin++;
            int left = rootin - leftin;
            root->left = pre_order(leftpre + 1, leftpre + left, leftin, rootin - 1, pre, in);
            root->right = pre_order(leftpre + left + 1, rightpre, rootin + 1, rightin, pre, in);
            return root;
        }
    };

    参考:
    重建二叉树

    展开全文
  • 1、这里根据先序序列的特性,其左孩子必为先序序列中根节点的下一个位置上的结点 2、那么右孩子呢?可以这么考虑:先序序列遍历顺序为:根->左->右,那你要早右孩子在先序序列中的位置,可以先求出根结点的左...

    思想:借助分治思想,时间复杂度O(NlogN),空间复杂度为O(logN)
    时间复杂度计算利用Master定理:
    T(n) = 2T(n/2)+ n
    借助先序序列构建当前根结点root,然后再借助中序序列去求root的左和右孩子在先序序列中的位置,这也是这题得到巧妙之处
    怎么求?
    1、这里根据先序序列的特性,其左孩子必为先序序列中根节点的下一个位置上的结点
    2、那么右孩子呢?可以这么考虑:先序序列遍历顺序为:根->左->右,那你要早右孩子在先序序列中的位置,可以先求出根结点的左子树右多少个结点,假设有m个.然后右孩子对应的下标即为当前根结点在先序序列中的下标+m.(prestart+rootidx-inStart+1)
    那么怎么求这个m呢?借助中序遍历的特性:左->根->右,所以只要找出根结点在中序序列中的下标然后减去中序序列的起始下标+1即为其左子树有多少个结点(m=rootidx-inStart+1

    class Solution {
          /*
        @attribute int istart(iend):初始值应为原中序序列的首尾下标,然后进行迭代后,其值分别表示root的左(右)子树在中序序列中的起始位置
        @attribute int pStart:代表待创建的根节点在先序序列中的下标
        */
        public TreeNode bulider(int[]preorder,int pstart,int[]inorder,int istart,int iend){
           if(pstart>=preorder.length||istart>iend){//这里后面的那个判断是为了当前子树在中序序列的区间是有效的
               return null;
           }
            TreeNode root = new TreeNode(preorder[pstart]);
            int rootIdxInInorder = istart;
            //先找到根节点在中序序列中的位置
           // 由于这里要去遍历中序遍历导致时间复杂度变为O(nlogn),所以要改进时间复杂度就从这里入手,借助一个Map来存储中序遍历序列中每个下标对应的节点所在的位置
    while(rootIdxInInorder<inorder.length&&inorder[rootIdxInInorder]!=preorder[pstart]){
              rootIdxInInorder++;
            }
            //计算其左孩子的个数
            int leftNodeMount = rootIdxInInorder-istart;
            root.left = bulider(preorder,pstart+1,inorder,istart,rootIdxInInorder-1);
            root.right = bulider(preorder,pstart+leftNodeMount+1,inorder,rootIdxInInorder+1,iend);
            return root; 
        } 
        public TreeNode buildTree(int[] preorder, int[] inorder) {
         if(preorder.length==0) return null;
         return bulider(preorder,0,inorder,0,inorder.length-1);
        }
    }
    

    【改进型】:
    借助一个Map来存储中序遍历序列中每个下标对应的节点所在的位置,避免再递归时再去遍历中序序列去找到root在中序序列中的位置
    时间复杂度O(N) ,空间复杂度O(N)
    T(N) = 2T(n/2) +O(1)

    class Solution {
        private TreeNode helper(int[]preorder,int pstart,int[] inorder,int instart,int inend,Map<Integer,Integer>map){
            if(instart>inend){
                return null;
            }
            if(instart==inend){
                return new TreeNode(preorder[pstart]);
            }
            TreeNode root = new TreeNode(preorder[pstart]);
            int idx = map.get(preorder[pstart]);
            root.left = helper(preorder, pstart+1, inorder, instart, idx-1,map);
            root.right = helper(preorder, pstart+(idx-instart+1), inorder, idx+1, inend,map);
            return root;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
           int pLen = preorder.length, iLen = inorder.length;
           if(pLen==0||iLen==0||pLen!=iLen){
               return null;
           }
           Map<Integer,Integer> map = new HashMap<>();
           for(int i=0;i<iLen;i++){
               map.put(inorder[i],i);
           } 
           return helper(preorder,0,inorder,0,iLen-1,map);  
        }
    }
    
    展开全文
  • 介绍一下树的层次遍历,顾名思义一层一层的遍历输出,...前序遍历有一个特点,第一个节点为二叉树节点,根据这个节点可以在中序序列中找到节点的左右子树。例如:一个二叉树前序序列是:a b d e g c f,...
  • 解析: 首先分析:给出先序遍历的二叉树的结果,我们知道先序是: 左 右;中序是:左 右;...思想:根据二叉树的先序序列和中序序列恢复二叉树的递归思想是:先根据先序序列的第一个结点建立
  • 这是一个典型的已知中序先序求二叉树的案例,具体实现步骤如下: 1、先根据先序序列确定树的节点 2、根据根节点在中序在中序序列中划分出二叉树的左右子树包含哪些节点,然后根据左右子树节点在先序序列中的...
  • 例如输入前序遍历序列{1,2,4,7,3,5,6,8}中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 算法思想:(tips:前序遍历, 节点在左节点在右节点;中序遍历,左节点在节点最后右节点) 先序遍历的第...
  • 还原二叉树 要求1: 给定一颗二叉树的先序遍历序列和中序遍历序列,...这就是说,在先序遍历序列中,第一个结点一定是二叉树结点。 同样根据定义,二叉树的中序遍历是遍历左子树,然后访问结点,最后再遍历...
  • /*根据二叉树的前序序列和中序序列建立该二叉树。这个过程是 *一个递归过程,其基本思想是:跟据前序序列的第一个元素建立 *节点,然后在中序序列中找到该元素,确定节点的左、右子树的中序序列; *再再...
  • A、acbed B、 decab C、 deabc D、 cedba 解法如下: 在两种遍历序列中找临近的两个或三个字符(内容相同,但顺序可能相同或者不同),如上例,从右向左找,找出的是ab,根据后序中序,可还原一棵子树是b是左...
  • 关键是怎么根据前中序推出二叉树。假设前序为1245367,中序为4251637。那么结点为1,在中序找到1,则左边为1的...代码实现:建树,然后算出其前序中序序列,最后再根据序列求出树,看是否刚开始建的树相同,
  • 对于一个二叉搜索树来说,因为他的特性,导致所有的左子树小于右子树,而又因为对于二叉树的节点来说,生成序列中左子树右子树的先后顺序不影响其的生成。 并且,对于二叉搜索树,结点一定在最前面。 这样我们...
  • 重建二叉树

    2018-09-25 21:19:43
    题目描述: 输入某二叉树的前序遍历中序遍历的结果,请重建出该二叉树。假设输入的前序遍历中序遍历的结果...2.根据根节点出中序遍历序列中左右子树的中序遍历序列,前序遍历序列的左右子树的前序序列。 3....
  • 4-1-4 二叉树及其遍历 还原二叉树 (25 分) 给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该...本题主要分成两个部分:根据先序中序遍历序列建树、高度 (+/后=后/)(即必须包含中序遍历序列
  • 这两天做PTA总是碰到这种问题,所以想着做一个总结。基本思路来源于别人。 题目例如:根据后序中序遍历输出先序遍历、*根据后序...在二叉树中先根后左再右。 上图先序遍历顺序为:ABDECF 2.中序遍历(左根右)...
  • 例子: 前序:1, 2, 3, 4, 5, 6(左右) ...中序则是按照:左—–—–右 的顺序排列,其中左,右子树按照同样的结构,所以我们可以从前序遍历的节点入手,迅速定位中序序列的结构左子树
  • 解题思路:开始时我只知道通过先序、中序二叉树,然后再后序遍历二叉树,这当然也是一种解题思路,但是会做一些无用功,比如:计算二叉树。其实,可以直接通过先序序列和中序序列直接出后序序列的。思路如下...
  • 根据树的先根和后根能否确定唯一的一棵树,并举例说明; 在n个没有顺序的序列中,取前k和最小的元素,k远小于n。你认为哪种排序方式比较好。根据你选择的排序方式,在给出的一串数取前几个元素,然后问比较...
  • 编写算法,求二叉树(二叉链表)的直径。 (2)已知二叉树(二叉链表)结点指针bt,树两个结点的指针p、q。编写算法求距离结点*p*q最近的公共祖先的地址。 (3)已知二叉树(二叉链表)结点指针bt,利用二叉树叶子结点...
  • 图示窗口显示二叉树的逻辑结构遍历结果输出的结点序列,图指针 bt 指向当前遍历的二叉树结点。 17. 线索二叉树 图示窗口显示二叉树的存储结构,但结点只含标志域,而以结点间的黑色连线表示指针,红色...
  • 数据结构演示软件

    2013-06-02 21:32:36
    图示窗口显示二叉树的逻辑结构遍历结果输出的结点序列,图指针 bt 指向当前遍历的二叉树结点。 17. 线索二叉树 图示窗口显示二叉树的存储结构,但结点只含标志域,而以结点间的黑色连线表示指针,红色...
  • 或者两个整数mn需要改变m二进制的多少位才能得到n,可以做 m^n 的异或运算,然后这个数有多少个1。 面试题11:数值的整数次方:如果采用常规解法,需要注意的地方:当指数为负数的时候;当底数为零且指数...
  • 图示窗口显示二叉树的逻辑结构遍历结果输出的结点序列,图指针 bt 指向当前遍历的二叉树结点。 17. 线索二叉树 图示窗口显示二叉树的存储结构,但结点只含标志域,而以结点间的黑色连线表示指针,红色...
  • 二叉树的构造与遍历问题:给定二叉树,能给出相应的前后序遍历序列;给定一个中序遍历序列,再给出一个前序或后序遍历序列,构造出二叉树 考点5. Huffman树的构造与Huffman编码:节点的权值,到叶子节点的路径...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...
  • 数据结构实验

    2012-04-13 09:55:47
    已知有—棵以二叉链表存储的二叉树,root指向结点,p指向二叉树中任一结点,如何结点到p所指结点之间的路径? 实验6:二分查找、Hash查找算法的程序实现 (第十五三周星期三7、8节) 一、 实验目的 1 ....
  • (3)本程序使用栈将逻辑表达式的变量进行存储,然后将栈的元素作为二叉树的结点结构,然后根据优先级读取表达式建立二叉树,并通过逐个判断实现对重言式的判别。 测试数据 (1) (A|~A)&(B|~B) (2) (A&~A)&C (3...
  • (13) 设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(B) 注:利用公式n=n0+n1+n2、n0=n2+1完全二叉数的特点可出 A. 349 B. 350 C. 255 D. 351 (14) 结构化程序设计主要强调的是(B) A.程序的规模 ...

空空如也

空空如也

1 2
收藏数 30
精华内容 12
关键字:

根据先根和中根序列求二叉树