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

    千次阅读 多人点赞 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

    展开全文
  • 西电复试之——真题2009D 已知先序中序序列,求二叉树的后序序列 测试用例 先序:ABDGCEFH 后序:DGBAECHF 输出:GDBEHFCA #include<iostream> #include<string.h> #include<string> using ...

    西电复试之——真题2009D 已知先序中序序列,求二叉树的后序序列

    测试用例
    先序:ABDGCEFH
    后序:DGBAECHF
    输出:GDBEHFCA

    #include<iostream>
    #include<string.h>
    #include<string>
    
    using namespace std;
    struct node {
    	int data;
    	node* lchild;
    	node* rchild;
    };
    int a[10], b[10];//先中后
    int n;//结点个数
    node* create(int al, int ar, int bl, int br) {
    	if (al > ar) {
    		//先序序列长度小于等于0时
    		return NULL;
    	}
    	//创建一个新的结点,用来存放当前二叉树的根节点
    	node* root = new node;
    	//新结点的数据域为根结点的值
    	root->data = a[al];
    	int k;
    	//在中序中找到a[al]同数据的结点
    	for (k = bl; k <= br; k++) {
    		if (b[k] == a[al]) {
    			break;
    		}
    	}
    	//左子树的结点个数
    	int numleft = k - bl;
    	root->lchild = create(al + 1, al + numleft, bl, k - 1);
    	root->rchild = create(al + numleft + 1, ar, k + 1, br);
    	return root;
    }
    void houxu(node* root) {
    	if (root == NULL) {
    		return;
    	}
    	houxu(root->lchild);
    	houxu(root->rchild);
    	printf("%c", root->data + 'A');
    }
    int main() {
    	string str1, str2;
    	cin >> str1 >> str2;
    	n = str1.length();
    	for (int i = 0; i < str1.length(); i++) {
    		a[i] = str1[i] - 'A';
    		b[i] = str2[i] - 'A';
    	}
    	node* root;
    	//构建出二叉树
    	root=create(0, n - 1, 0, n - 1);
    	//后序遍历
    	houxu(root);
    	return 0;
    }
    
    展开全文
  • 知道任何一棵二叉树先序中序遍历的序列或者中序和后序的遍历序列,都能构造出唯一的一棵二叉树 下面先看一道PTA上的题引入思考 因为知道了先序遍历的特点,从第一个开始,都先从根开始。 把先序的根在中序中...
  • 已知中序先序求后序#include #include #include using namespace std;char inorder[100]; char preorder[100];void build(int in_l, int in_r, int pre_l, int pre_r){ int mid = strchr(inor
  • 通过递归遍历的方法扫描先序中序,构造二叉树; 通过递归遍历的方法扫描后序中序,构造二叉树; 方法理解起来很简单,在纸上自己画画就知道如何去做了,该算法难点在于遍历中需要精确的数学计算,还需要清晰的判断...
  • package demoFive; /* *@author:张文波 ...//已知二叉树前序和中序序列,求二叉树 public class BuildTree { public static String xian="ABC"; public static String zhong="BAC"; public sta...
  • 首先,我们看看前序、中序、后序遍历的特性:前序遍历:1.访问根节点2.前序遍历左子树3.前序遍历右子树(个人觉得这个命名略微有误导性,因为前序的“前”容易让人误会成树的最前边(视觉上的左边)。记住前序遍历就是...
  • 请构造二叉树并返回其根节点 法一:递归分治 对于任意一颗树而言,前序遍历的形式总是 [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是...
  • #include "iostream"using namespace std;char A[50],B[50];struct Node{char Data;Node *left;Node *right;};struct Tree{private:Node *root;public:Tree(){root=NULL;}Node *&Root(){return root;...
  • printf("输入二叉树中序先序序列,后序序列\n"); gets(mid); gets(pre); midprecreat(Troot,mid,pre,0,n-1,0,n-1); print(Troot); printf("程序2 请输入节点个数\n"); scanf("%d",&n); getchar(); printf...
  • 总结下二叉树的已知两种遍历方式第三种遍历顺序的方法,已知先序中序遍历或者后序与中序遍历后二叉树是唯一确定的,下面介绍怎么出第三种遍历顺序。  先序遍历顺序为:根结点——左子结点——右子结点,中序...
  • 首先,我们看看前序、中序、后序遍历的特性:前序遍历:1.访问根节点2.前序遍历左子树3.前序遍历右子树(个人觉得这个命名略微有误导性,因为前序的“前”容易让人误会成树的最前边(视觉上的左边)。记住前序遍历就是...
  • 二叉树的重建过程中必须存在中序序列 ,从先序或者后序中能确定二叉树的根节点,再从中序中确定左右根节点的左右子树,再将左右子树按照之前的方案进行处理; 一:先序序列+中序序列->后序序列 #include #include...
  • 二叉树的性质:二叉树的第 i 层最多有 2i - 1 个结点。由定义可知,二叉树的每个结点最多有两个孩子结点,那么第 i 层最多的结点数等于第 i - 1 层最多结点数的 2 倍。而第 1 层最多只有 1 个结点,所以我们可以知道...
  • 先序中序重构二叉树

    2019-10-11 16:37:55
    已知二叉树先序遍历序列和中序遍历序列,重构出二叉树。 算法简介: 如上图所示的二叉树,其先序遍历序列为:a b d c e f 中序序列为:d b a e c f 首先可以知道根结点为先序的第一个元素即 a ,(a b d c e f...
  • 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 ...
  • 先序遍历:根 —> 左 —> 右 中序遍历:左 —> 根 —> 右 后序遍历:左 —> 右 —>...根据原始的先序中序遍历结果,得到左右子树的先序中序遍历结果,递归还原二叉树 举例: p...
  • 01 如何实现二叉树 首先定义树的结点 public class Node { public int data; public Node left; public Node right; public Node (int data){ this.data=data; this.left=null; this.right...
  • package chazao.shu; import chazao.shu.Node; public class BiTree { private Node root; public BiTree(){ root = null;... System.out.print("二叉树的后序遍历:"); biTree.postOrder(); } }
  • #include "BiTNode.h" #include "SqStack.h" #include "SqQueue.h" #include <...//任务:已知先序遍历中序遍历构造二叉树 BiTree preInCreate(int A[], int startA, int endA, int B[], int start...
  • WAY 1. 由先序和中序遍历序列确定一棵二叉树,再后序遍历得到后序序列。 WAY 2. 不创建树,直接由先序中序序列得到后序遍历序列。

空空如也

空空如也

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

已知先序中序求二叉树