精华内容
下载资源
问答
  • 二叉树已知先序中序求后序、已知中序后序求先序

    千次阅读 多人点赞 2016-07-30 23:18:22
    需要注意的是(我们只能够通过已知先序中序求后序或已知中序后序求先序,而不能够已知先序和后序求中序) 下面总结一下两种题的做法首先回顾知识点 二叉树先序遍历 根结点—->左子树—->右子树 二叉树中序遍历 左...

    在做数据结构面试题的时候我们会经常发现有关二叉树的题目总是这样的
    栗子:
    已知某二叉树先序为……中序为……求后序
    已知某二叉树中序为……后序为……求先序
    需要注意的是(我们只能够通过已知先序中序求后序或已知中序后序求先序,而不能够已知先序和后序求中序
    下面总结一下两种题的做法


    首先回顾知识点

    • 二叉树先序遍历 根结点—->左子树—->右子树
    • 二叉树中序遍历 左子树—->根结点—->右子树
    • 二叉树后序遍历 左子树—->右子树—->根结点
      这个非常好记忆,就是看根结点的位置就可以了

    第一种
    已知一个二叉树的先序遍历结果为:ABCDEFGH,中序遍历结果为BDCEAFHG,求该二叉树的后序遍历。

    思路:拿到这样的题,我们要先根据两种遍历顺序把原始二叉树画出来,然后再根据后序遍历的规则解出后序遍历。

    解析:首先看先序遍历的第一个结点为A,那么根据先序遍历规则先访问根结点,那么A肯定是根结点了。然后根据中序遍历规则先访问左子树中间访问根结点。那么我们可以得出BCDE是根结点A的左子树FHG是根结点A的右子树。那么左子树BCDE当中又怎么排序呢?这个时候我们再来看先序遍历,A结点之后先序先遍历B,说明B一定是根结点A左子树的根结点。如下图
    这里写图片描述
    然后我们再看中序遍历,B是第一个,说明B结点没有左子树,CDE是B的右子树,然后我们想知道CDE如何排序,再次看先序遍历,这个时候先序遍历AB已经排出来。过来是C,说明C是B结点右子树的根结点。可以画出下图
    这里写图片描述
    接下来我们再次看中序遍历,中序遍历B接下来是D,而且我们已经知道C是B右字数的根结点,那么我们根据中序先访问左子树然后访问根结点,就知道D是C结点的左子树。那么E理所当然应该是C结点的右子树。可以画出如下图
    这里写图片描述
    这样我们的左子树就画好了,接下来处理FGH。我们看到F在先序和中序中都先出现,我们就可以确定F是右子树的根结点,并且F没有左子树。接下来先序出现的是G,而中序中G是最后出现的。所以G是F右子树的根结点而H是G的左子树。这样我们就确定了原始树的样子如下图
    这里写图片描述

    最后一步:
    得知原始树
    我们按照后序遍历的规则,先访问左子树再访问右子树最后访问根结点
    可以得到后续遍历的顺序为DECBHGFA


    哈哈,学会了先序中序求后序,我们再看第二种,已知中序后序求先序

    直接上题目
    第二种
    已知一个二叉树的中序遍历结果为: BDACE,后序遍历结果为 DBECA,求该二叉树的先序遍历。

    按照第一题的做法,首先我们知道后序遍历最后遍历根结点,所以A结点一定是这棵树的根结点,然后我们再开中序遍历的结果,A结点是根结点,所以BD是A结点的左子树,CE是根结点的右子树。先看BD。根据中序先遍历左子树然后遍历根结点最后遍历右子树顺序为BD,而后序先遍历左子树再遍历右子树最后遍历根结点顺序为DB。所以可以推出B是A的左子树的根结点,且B没有左子树,B的右子树是D。可画出下图
    这里写图片描述

    接下来我们来看A的右子树。剩下EC两个结点,我们再次看中序与后序遍历的结果。根据中序先遍历左子树然后遍历根结点最后遍历右子树顺序为CE,而后序先遍历左子树再遍历右子树最后遍历根结点顺序为EC。则我们可以推出C应该是A结点右子树的根结点,而E应该是C结点的右子树。这样我们就可以画出原始树如下图
    这里写图片描述

    根据原始树,我们可以按照先序遍历的顺序得到先序遍历结果:ABDCE

    总结:掌握先中后遍历的规则,然后结合先中或者中后以及遍历规则画出原始树,然后根据原始树求出先序或者后序!!

    展开全文
  • 已知先序中序求后序public class BinaryTree1 { private Node root; public void postOrder(){ postOrder(root); } //二叉树构造完毕之后进行后续遍历 private void postOrder(Node localroot) { if(localr

    已知先序中序求后序

    public class BinaryTree1 {
        private Node root;
    
        public void postOrder(){
            postOrder(root);
        }
    
        //二叉树构造完毕之后进行后续遍历
        private void postOrder(Node localroot) {
            if(localroot!=null){
                postOrder(localroot.left);
                postOrder(localroot.right);
                System.out.print(localroot.data+" ");
            }
        }
    
        public void InitTree(int[] preOrder,int[] inOrder){
            this.root=InitTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
        }
    
        /**
         *
         * @param preOrder 先序遍历的数组
         * @param start1 递归每次遍历的数据段在先序遍历数组中的起始位置
         * @param end1 递归每次遍历的数据段在先序遍历数组中的终止位置
         * @param inOrder 中序遍历的数组
         * @param start2 递归每次遍历的数据段在中序遍历数组中的起始位置
         * @param end2 递归每次遍历的数据段在中序遍历数组中的终止位置
         * @return 返回本次递归所构造完毕的树的根节点(从子结点向上依次返回)
         */
        private Node InitTree(int[] preOrder, int start1, int end1, int[] inOrder, int start2, int end2) {
            if(start1>end1||start2>end2){
                return null;
            }
            int rootData=preOrder[start1];
            Node head=new Node(rootData);
            int rootindex=findIndexInArray(inOrder,rootData,start2,end2);
            /**
             * offset为以本次递归构造的节点为根节点的左子树的节点个数
             */
            int offset=rootindex-start2-1;
            Node left=InitTree(preOrder,start1+1,start1+offset+1,inOrder,start2,start2+offset);
            Node right=InitTree(preOrder,start1+offset+2,end1,inOrder,rootindex+1,end2);
            head.left=left;
            head.right=right;
            return head;
        }
    
        //检索出递归方法每次构造的节点在中序遍历数组中的索引
        public int  findIndexInArray(int[] a,int x,int begin,int end){
            for (int i = begin; i <=end; i++) {
                if(a[i]==x){
                    return i;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            BinaryTree1 biTree=new BinaryTree1();
            int[] preOrder={2,1,8,7,4,3,6,5,7,9};
            int[] inorder={1,2,3,4,5,6,7,7,8,9};
            biTree.InitTree(preOrder,inorder);
            System.out.println("后序遍历");
            biTree.postOrder();
        }
    }

    解释:假设先序数组A B D E C F 中序数组D B E A F C

    这里写图片描述

    已知中序后序求先序

    public class BinaryTree2 {
        private Node root;
    
        public void preOrder(){
            preOrder(root);
        }
    
        private void preOrder(Node localroot) {
            if(localroot!=null){
                System.out.print(localroot.data+" ");
                preOrder(localroot.left);
                preOrder(localroot.right);
            }
        }
    
        public void initTree(int[] inOrder,int[] postOrder){
            this.root=initTree(inOrder,0,inOrder.length-1,postOrder,0,postOrder.length-1);
        }
    
        private Node initTree(int[] inOrder, int start1, int end1, int[] postOrder, int start2, int end2) {
            if(start1>end1||start2>end2){
                return null;
            }
            int rootdata=postOrder[end2];
            Node head=new Node(rootdata);
            int rootindex=findIndexInArray(inOrder,rootdata,start1,end1);
            int offset=rootindex-1-start1;
            Node left=initTree(inOrder,start1,start1+offset,postOrder,start2,start2+offset);
            Node right=initTree(inOrder,rootindex+1,end1,postOrder,start2+offset+1,end2-1);
            head.left=left;
            head.right=right;
            return head;
        }
    
        public int  findIndexInArray(int[] a,int x,int begin,int end){
            for (int i = begin; i <=end; i++) {
                if(a[i]==x){
                    return i;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {
            BinaryTree2 biTree=new BinaryTree2();
            int[] inorder={1,2,3,4,5,6,7,7,8,9};
            int[] postOrder={1,3,5,6,4,7,7,9,8,2 };
            biTree.initTree(inorder,postOrder);
            System.out.println("先序遍历");
            biTree.preOrder();
        }
    }

    解释同上。。。。。。

    展开全文
  • 已知先序中序求后序: /* 已知先序和中序 求后序 */ #include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define maxn 1010 int pre[maxn], in...

    简单易忘~~~

    已知先序中序求后序:

    /*
        已知先序和中序 求后序
     */
    
    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    using namespace std;
    
    #define maxn 1010
    
    int pre[maxn], in[maxn], post[maxn];
    int n;
    int cnt;
    
    int ask_root(int len, int root_num, int in[]) { //在当前的子树立找根节点
        for (int i=0; i<len; ++i) {
            if (in[i] == root_num)
                return i;
        }
        return -1;
    }
    
    void askPost(int len, int pre[], int in[]) { // 当前先序和中序序列的长度
        int root_id = ask_root(len, pre[0], in);
        if (root_id < 0) return;
        askPost(root_id, pre+1, in); // 递归到当前根节点的左子树
        askPost(len-root_id-1, pre+root_id+1, in+root_id+1); // 递归到当前根节点的右子树
        post[cnt++] = pre[0]; // 递归完左子树和右子树之后 剩下了最左的叶子结点 加入后序序列中
    }
    
    int main() {
        while(cin >> n) {
             cnt = 0;
             for (int i=0; i<n; ++i) { // 输入先序序列
                cin >> pre[i];
             }
             for (int i=0; i<n; ++i) { // 输入中序序列
                cin >> in[i];
             }
    
             askPost(n, pre, in); //
    
             for (int i=0; i<n; ++i) {
                cout << post[i] << endl;
             }
        }
        return 0;
    }
    

      

    已知中序后序求先序:

    /*
     已知二叉树的中序和后序 求其先序
     */
    
    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #define maxn 1010
    using namespace std;
    
    int pre[maxn], in[maxn], post[maxn];
    int n;
    int cnt;
    
    int ask_root(int len, int root, int in[]) {
        for (int i=0; i<len; ++i) {
            if (in[i] == root)
                return i;
        }
        return -1;
    }
    
    void askPre(int len, int in[], int post[]) {
        int root_id = ask_root(len, post[len-1], in);
    
       // cout << root_id << "===\n";
        if (root_id == -1) return;
        pre[cnt++] = post[len-1]; // 将当前根节点加入到先序序列中
        askPre(root_id, in, post); // 递归到左子树
        askPre(len-root_id-1, in+root_id+1, post+root_id); //递归到右子树
    }
    
    
    int main() {
        while(cin >> n) {
            cnt = 0;
            for (int i=0; i<n; ++i) {
                cin >> in[i]; // 输入中序
            }
            for (int i=0; i<n; ++i) {
                cin >> post[i]; // 输入后序
            }
    
            askPre(n, in, post);
    
            for (int i=0; i<n; ++i) {
                cout << pre[i] << endl;
            }
        }
        return 0;
    }
    

      

    转载于:https://www.cnblogs.com/icode-girl/p/5289167.html

    展开全文
  • 后来尝试着写了一下出栈序列,发现正好是中序遍历结果,那么这道题就转换成已知先序中序求后序的题 对于这道题,入栈序列:123456;出栈序列:324165 根据这个建树然后后序遍历即可 #include<iostream> #...

    在这里插入图片描述
    思路:
    一开始过度关注这个堆栈的过程,半天get不到思路
    后来尝试着写了一下出栈序列,发现正好是中序遍历结果,那么这道题就转换成已知先序中序求后序的题
    对于这道题,入栈序列:123456出栈序列:324165
    根据这个建树然后后序遍历即可

    #include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    struct node{
      int data;
      node *left,*right;
    };
    vector<int> pre,in,post;
    node* create(int prel,int prer,int inl,int inr)
    {
    	if(prel>prer)return NULL; 
    	node* root=new node;
    	root->data=pre[prel];
    	int k;
    	for(k=inl;k<=inr;k++)
    	{
    		if(in[k]==pre[prel])break;
    	}
    	root->left=create(prel+1,prel+k-inl,inl,k-1);
    	root->right=create(prel+k-inl+1,prer,k+1,inr);
    	return root;
    }
    void postorder(node* root)
    {
    	if(root==NULL)return;
    	postorder(root->left);
    	postorder(root->right);
    	post.push_back(root->data);
    }
    int main()
    {
      int n,temp;
      string str;
      stack<int> s;
      cin>>n;
      for(int i=0;i<2*n;i++)
      {
        cin>>str;
        if(str=="Push")
        {
          cin>>temp;
          pre.push_back(temp);
          s.push(temp);
        }
        else
        {
          in.push_back(s.top());
          s.pop();
        }
      }
        node* rot=create(0,n-1,0,n-1);
        postorder(rot);
        for(int i=0;i<n;i++)
        {
        	cout<<post[i];
        	if(i!=n-1)cout<<" ";
        	else cout<<endl;
        }
        return 0;
    }
      
    
    展开全文
  • 已知先序中序求后序

    2016-03-15 11:33:11
    竟然必须要写说明!不然不能发表。
  • 总结下二叉树的已知两种遍历方式第三种遍历顺序的方法,已知先序中序遍历或者后序中序遍历后二叉树是唯一确定的,下面介绍怎么出第三种遍历顺序。  先序遍历顺序为:根结点——左子结点——右子结点,中序...
  • 知道任何一棵二叉树的先序中序遍历的序列或者中序后序的遍历序列,都能构造出唯一的一棵二叉树 下面先看一道PTA上的题引入思考 因为知道了先序遍历的特点,从第一个开始,都先从根开始。 把先序的根在中序中...
  • 通过递归遍历的方法扫描先序中序,构造二叉树; 通过递归遍历的方法扫描后序中序,构造二叉树; 方法理解起来很简单,在纸上自己画画就知道如何去做了,该算法难点在于遍历中需要精确的数学计算,还需要清晰的判断...
  • 已知先序中序求后序.pdf
  • 二叉树的重建过程中必须存在中序序列 ,从先序或者后序中能确定二叉树的根节点,再从中序中确定左右根节点的左右子树,再将左右子树按照之前的方案进行处理; 一:先序序列+中序序列->后序序列 #include #include...
  • // tree.cpp : Defines the entry point for the console application. // #include <stdio.h> #include "string.h" typedef struct node { char data; struct node *lchild,*rchild;...} Bi...
  • //已知先序 中序 求后序  void dg(int r1,int l1,int r2,int l2) { int i; if(r1>l1) return; for(i=r2;w[i]!=q[r1];i++); dg(r1+1,l1-l2+i,r2,i-1); dg(l1-l2+i+1,l1,i+1,l2); if(e==1) ...
  • Tree描述Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes. This is an example of one of ...
  • package chazao.shu; import chazao.shu.Node; public class BiTree { private Node root; public BiTree(){ root = null;... //后序遍历方法递归实现 public void postOrder(Node localRoot){ ...
  • 题目描述不说了。 前序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ ...求中序遍历。 1 确定根,确定左子树,确定右子树。 2 在左子树中递归。 3 在右子树中递归。 4 打印当前根。 代码如下: 1 #incl...
  • 解题思路: 得到隐藏条件——入栈顺序是一颗二叉树的先序序列,然后根据这两个序列找到所有根节点及其对应的左右子树,将根节点放在左右子树后面输出,就得到后序序列了。 AC代码 #include using namespace std; ...
  • 二叉树_已知先序中序求后序 #include #include using namespace std ; class Node { public : int data; Node *lchild, *rchild; Node( int _data) { data = _data; lchild = NULL; rchild =...
  • 树的三种遍历方式的遍历顺序: 先序遍历:根、左子树、右子树(特点:第一个元素为根) 中序遍历:左子树、根、右子...1、已知先序中序求后序 先序遍历的第一个字符为根,因此只需在中序遍历中找到它,就可以把根...
  • 先 中转后序的 两种实现 对比
  • 中序后序求先序 怎么破? 捞干的: 做过笔试题的童鞋 绝对不陌生吧 二叉树遍历问题几乎是必考点之一 , 求解这类题思路非常重要: 最近琐事繁多图就比较简陋 但以老夫三寸不烂之舌, 让诸位听懂还是没得问题. 把握一个...
  • C++源码,使用VC6.0打开编译后即可运行。 使用递归方法,极其经典,代码简短易懂。
  • #include #include #include struct node { char data; struct node *l,*r; }; struct node *creat(struct node *root,char *a,char *b,int n) { int p; if(n)return NULL; r
  • 根据先序 中序求后序

    2016-05-23 11:24:20
    使用数组求解已知树的先序中序求解后序的问题
  • 输入先序遍历跟中序遍历,输出后序遍历 #include #include #include #include #include using namespace std; const int N=1010; struct node { int v; node *left , *right; node():left(NULL),right(NULL)
  • 树的三种遍历方式的遍历顺序: 先序遍历:根、左子树、右子树(特点:第一个元素为根) 中序遍历:左子树、根、右子树(特点:...1、已知先序中序求后序 先序遍历的第一个字符为根,因此只需在中序遍历中找到它,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,488
精华内容 2,195
关键字:

已知先序中序求后序