精华内容
下载资源
问答
  • 【二叉树】根据后续和中序遍历输出前序遍历 [建树+非建树做法]
    千次阅读
    2022-03-31 17:22:24

    F . 案例 4-1.1:根据后续和中序遍历输出前序遍历
    Description
    本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

    Input
    第一行给出正整数N (≤30),是树中结点的个数。随后两行,每行给出N 个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。

    Output
    在一行中输出Preorder: 以及该树的先序遍历结果。

    Samples
    Input 复制
    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
    Output
    Preorder: 4 1 3 2 6 5 7

    先贴一篇dalao模拟的题解

    整体思路:由后序遍历找到根节点,然后在中序遍历中找到分割点,然后递归遍历左右子树即可。

    非建树做法:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1010;
    int post[N],mid[N];
    void Pre(int *post,int *mid,int l){
    	if(l<=0) return ;
    	cout<<" "<<post[l-1];
    	int i;//定义左子树的长度
    	for(i=0;i<l;i++) if(mid[i]==post[l-1]) break;//在中序遍历中找到分割点
    	Pre(post,mid,i);//由于我们定义根节点为post[l-1]所以这里我们传长度i
    	Pre(post+i,mid+i+1,l-i-1);//由于左子树长度为i那么去下刚输出的根节点就是l-i-1
    }
    /*
    7
    2 3 1 5 7 6 4 //post
    1 2 3 4 5 6 7 //mid
    
    4 1 3 2 6 5 7
    */
    int main(){
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++) cin>>post[i];
    	for(int i=0;i<n;i++) cin>>mid[i];
    	
    	cout<<"Preorder:";
    	Pre(post,mid,n);
    	
    	return 0;
    }
    

    建议读者看懂上述数组模拟,那下面的呢建树做法就迎刃而解了

    建树做法:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1010;
    int post[N],mid[N];
    struct Node{
    	int val;
    	Node *lch,*rch;
    };
    Node *creat(int *post,int *mid,int l){
    	if(l<=0) return NULL;
    	Node *root=new Node;
    	root->val=post[l-1];
    	int *p;
    	for(p=mid;p!=NULL;p++) if(*p==post[l-1]) break;
    	int i=p-mid;
    	root->lch=creat(post,mid,i);
    	root->rch=creat(post+i,mid+i+1,l-i-1);
    	return root;
    }
    void print(Node *root){
    	if(root==NULL) return ;
    	printf(" %d",root->val);
     	print(root->lch);
    	print(root->rch);
    	
    	//cout<<" "<<*root;
    }
     
    int main(){
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++) cin>>post[i];
    	for(int i=0;i<n;i++) cin>>mid[i];
    	Node *root=new Node;
    	root=creat(post,mid,n);
    	cout<<"Preorder:";
    	print(root);
    	
    	return 0;
    }
    /*
    7
    2 3 1 5 7 6 4 //post
    1 2 3 4 5 6 7 //mid
    
    4 1 3 2 6 5 7
    */
    
    更多相关内容
  • 已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
  • 主要介绍了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作,涉及Python基于先序遍历和中序遍历构造二叉树,再后序遍历输出相关操作技巧,需要的朋友可以参考下
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 主要介绍了Python利用前序和中序遍历结果重建二叉树的方法,实例分析了Python二叉树的定义与遍历操作技巧,需要的朋友可以参考下
  • 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回...
  • 下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式 第一行给出正整数N (≤30),是树中结点的个数。随后两行,每行给出N 个整数,分别对应后序遍历和中序遍历结果,数字间以...

    题目描述
    本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。
    输入格式
    第一行给出正整数N (≤30),是树中结点的个数。随后两行,每行给出N 个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。
    输出格式
    在一行中输出Preorder: 以及该树的先序遍历结果。
    输入样例
    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
    输出样例
    Preorder: 4 1 3 2 6 5 7

    题目不过多复述,看了其他博客,感觉讲的都不清楚,公式推导怎么来的根本没有说清楚,本博客重点讲一下推导过程!

    #include<iostream>
    #include<vector>
    using namespace std;
    struct node
    {
    	int data;
    	node* left = NULL, * right = NULL;
    };
    typedef node* tree;
    int num;
    vector<int>post, in;
    // ax-ay 是遍历后序表的范围  bx-by是中序表的范围
    void create_tree(tree &t,int ax, int ay, int bx, int by)
    {
    	if (ax > ay)
    		return;
    	t = new node;
    	int  root = post[ay],index ;
    	t->data = root;
    	for (int i = bx; i <= by; i++)
    	{
    		if (in[i] == root)
    		{
    			index = i;
    			break;
    		}
    	}
    	//主要是这一行的推导过程尤为重要 接下来详细讲解
    	create_tree(t->left, ax, ax + index - bx - 1, bx, index - 1);
    	create_tree(t->right, ax + index - bx, ay - 1, index + 1, by);
    	return;
    }
    void preorder(tree t)
    {
    	if (t == NULL)
    		return;
    	printf("%d ", t->data);
    	preorder(t->left);
    	preorder(t->right);
    	return;
    }
    int main()
    {
    	cin >> num;
    	post.resize(num+1,0);
    	in.resize(num + 1, 0);
    	for (int i = 1; i <= num; i++)
    		cin >> post[i];
    	for (int i = 1; i <= num; i++)
    		cin >> in[i];
    	tree t;
    	create_tree(t,1,num,1,num);
    	cout << "Preorder: ";
    	preorder(t);
    	return 0;
    }
    

    直接来看公式推导:
    num是数组大小,这里是7
    我们知道后序遍历表的最后一个元素必定是根,我们就从这里出发。

    在这里插入图片描述
    根节点就是 root = a[ay] (后序遍历,最后一个一定是根节点)

    接下来我们去中序遍历中找根节点的下标
    下标 index = 4
    那么在inoder表中
    1-3 就是根的左子树的结点
    5-7 就是根的右子树的结点

    那么
    左子树的结点个数就为 :index - bx
    右子树的结点个数就为 :num - index
    在这里插入图片描述
    下一步我们应该做的就是返回 postorder表中,去寻找左子树在表中的范围与右子树在表中的范围。
    我们接下来就进行数学推导:

    左子树:

    • postorder表中:

    起始位置是ax = 1, 由于左子树的节点数为 index-bx 那么终点位置就为 ax + index - bx -1(自己举个例子看看,比如1-2长度为2,终点就是 1+2-1)

    左子树在postorder表中的范围为 [ax,ax+index-bx-1]

    • inorder表中:

    起始位置就为bx,终点位置为index-1

    右子树同理:

    • postorder表中:

    其实位置就是左子树位置的右边一个位置 即 ax+index-bx,终点位置为ay-1(ay是根节点)

    右子树在postorder表中范围为 [ax+index-bx,ay-1]

    • inorder表中:

    从根节点的右侧一个位置,即index+1到表的末尾by!

    这就是推导过程,写出来感觉清楚些,希望能够帮助大家理解!

    展开全文
  • 二叉树已知后序和中序遍历前序遍历,C++编写已通过编译
  • 前序遍历就是先访问根节点的左子树再前序遍历左子树再遍历右子树 前序遍历算法如下: void _PrintTree_f2(BiTree a) { if(a)//*如果a不为空 { printf("%c\n",a->data);//*访问根结点 _PrintTree_f2(a-&...

    前序遍历就是先访问根节点的左子树再前序遍历左子树再遍历右子树

    前序遍历算法如下:

    void _PrintTree_f2(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f2(a->lchild);//*遍历左子树
    		_PrintTree_f2(a->rchild);//*遍历右子树
    	}
    }

    中序遍历就是先中序遍历根节点的右孩子再访问根节点其次中序遍历左孩子

    中序遍历算法如下:

    void _PrintTree_f4(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		_PrintTree_f4(a->lchild);//*遍历左子树
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f4(a->rchild);//*遍历右子树
    	}
    }

    后序遍历就是先后序遍历左孩子,再后序遍历右子树,最后访问根节点

    后续遍历算法如下:

    void _PrintTree_f3(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		_PrintTree_f3(a->lchild);//*遍历左子树
    		_PrintTree_f3(a->rchild);//*遍历右子树
    		printf("%c\n",a->data);//*访问根结点
    	}
    }

    双序遍历就是先访问根节点然后双序遍历左孩子再访问根节点然后双序遍历右孩子

    中序遍历算法如下:

    void _PrintTree_f1(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f1(a->lchild);//*遍历左子树
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f1(a->rchild);//*遍历右子树
    	}
    }

    完整代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct BiTNode
    {
    	char data;
    	struct BiTNode *rchild,*lchild;
    }*BiTree;
    void CreateBiTree(BiTree *a)
    {
    	char data;
    	scanf("%c",&data);
    	fflush(stdin);
    	if(data=='#')
    	{
    		*a=NULL;
    	}
    	else
    	{
    		*a=(struct BiTNode*)malloc(sizeof(struct BiTNode));
    		(*a)->data=data;
    		printf("请输入左孩子:\n");
    		CreateBiTree(&(*a)->lchild);
    		printf("请输入右孩子:\n");
    		CreateBiTree(&(*a)->rchild);
    	}
    }
    void _PrintTree_f1(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f1(a->lchild);//*遍历左子树
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f1(a->rchild);//*遍历右子树
    	}
    }
    void _PrintTree_f2(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f2(a->lchild);//*遍历左子树
    		_PrintTree_f2(a->rchild);//*遍历右子树
    	}
    }
    void _PrintTree_f3(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		_PrintTree_f3(a->lchild);//*遍历左子树
    		_PrintTree_f3(a->rchild);//*遍历右子树
    		printf("%c\n",a->data);//*访问根结点
    	}
    }
    void _PrintTree_f4(BiTree a)
    {
    	if(a)//*如果a不为空
    	{
    		_PrintTree_f4(a->lchild);//*遍历左子树
    		printf("%c\n",a->data);//*访问根结点
    		_PrintTree_f4(a->rchild);//*遍历右子树
    	}
    }
    void Delete_Tree(BiTree *a)
    {
    	if(*a)
    	{
    		Delete_Tree(&(*a)->lchild);
    		Delete_Tree(&(*a)->rchild);
    		BiTree b;
    		b=*a;
    		free(b);
    	}
    }
    main()
    {
    	BiTree a;
    	printf("请输入根节点:\n");
    	CreateBiTree(&a);
    	printf("双序遍历:\n");
    	_PrintTree_f1(a);
    	printf("中序遍历:\n");
    	_PrintTree_f4(a);
    	printf("前序遍历:\n");
    	_PrintTree_f2(a);
    	printf("后序遍历:\n");
    	_PrintTree_f3(a);
    	Delete_Tree(&a);
    	system("pause");
    	return 0;
    }

    程序运行如下:

    展开全文
  • 针对树这一数据结构的遍历问题主要有四种,前序遍历中序遍历、后序遍历、层序遍历,我们主要说明一下二叉树前序、中序、后序的递归方式代码模板。 基本思想 前序遍历:根结点 —> 左子树 —> 右子树 中序...

    针对树这一数据结构的遍历问题主要有四种,前序遍历、中序遍历、后序遍历、层序遍历,我们主要说明一下二叉树前序、中序、后序的递归方式代码模板。

    基本思想

    前序遍历:根结点 —> 左子树 —> 右子树
    中序遍历:左子树—> 根结点 —> 右子树
    后序遍历:左子树 —> 右子树 —> 根结点

    前序遍历:EBADCGFH

    中序遍历:ABCDEFGH

    后序遍历:ACDBFHGE

    前序遍历

        //前序遍历
        //获取整个树中所有的键
        public Queue<Key> preErgodic(){
            Queue<Key> keys = new Queue<>();
            preErgodic(root,keys);
            return keys;
        }
    
        //获取指定树x的键,放到keys队列中
        public void preErgodic(Node x, Queue<Key> keys){
    
            if(x==null){
                return;
            }
            //把树x的节点放进队列keys中
            keys.enqueue(x.key);
            //遍历左子树
            if(x.left!=null){
                preErgodic(x.left,keys);
            }
            //遍历右子树
            if(x.right!=null){
                preErgodic(x.right,keys);
            }
        }

    中序遍历

      //中序遍历
        public Queue<Key> midErgodic(){
            Queue<Key> keys = new Queue<>();
            midErgodic(root,keys);
            return keys;
        }
    
        public void midErgodic(Node x,Queue<Key> keys){
            if(x==null){
                return;
            }
            //左子树
            if(x.left!=null){
                midErgodic(x.left,keys);
            }
    
            //节点
            keys.enqueue(x.key);
    
            //右子树
            if(x.right!=null){
                midErgodic(x.right,keys);
            }
        }
    

    后序遍历

    //后序遍历
        public Queue<Key> afterErgodic(){
            Queue<Key> keys = new Queue<>();
            afterErgodic(root,keys);
            return keys;
        }
    
        public void afterErgodic(Node x,Queue<Key> keys){
            if(x==null){
                return;
            }
    
            //左
            if(x.left!=null){
                afterErgodic(x.left,keys);
            }
    
            //右
            if(x.right!=null){
                afterErgodic(x.right,keys);
            }
    
            keys.enqueue(x.key);
        }

    测试

    package cn.itcast.algorithm.tree;
    
    
    import cn.itcast.algorithm.queue.Queue;
    
    public class 遍历Test {
        public static void main(String[] args) {
            //创建树对象
            BinaryTree<String, String> tree = new BinaryTree<>();
            tree.put("E","5");
            tree.put("B","2");
            tree.put("G","7");
            tree.put("A","1");
            tree.put("D","4");
            tree.put("F","6");
            tree.put("H","8");
            tree.put("C","3");
    
    
            //前序遍历
            Queue<String> keys1=tree.preErgodic();
            for(String key:keys1){
                String value=tree.get(key);
                System.out.println(key+"-----"+value);
            }
    
            System.out.println("----------------------");
            //中序遍历
            Queue<String> keys2=tree.midErgodic();
            for(String s:keys2){
                String value=tree.get(s);
                System.out.println(s+"-----"+value);
            }
    
            System.out.println("----------------------");
            //后序遍历
            Queue<String> keys3=tree.afterErgodic();
            for (String S:keys3){
                String value=tree.get(S);
                System.out.println(S+"-----"+value);
            }
        }
    }
    

    测试结果

    展开全文
  • 主要介绍了Python二叉树的遍历操作,结合实例形式分析了Python针对二叉树的前序遍历,中序遍历,后序遍历,层序遍历等相关操作实现技巧,需要的朋友可以参考下
  • 现在有一个问题,已知二叉树的前序遍历和中序遍历: PreOrder: GDAFEMHZ InOrder: ADEFGHMZ 我们如何还原这颗二叉树,并求出他的后序遍历? 我们基于一个事实:中序遍历一定是 { 左子树中的节点集合 },root,{ ...
  • 给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度\le 8≤8)。 输入格式 22行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。 输出格式 11行,表示一棵...
  • python实现二叉树遍历(前序遍历中序遍历、后序遍历) 在计算机科学中,二叉树是一种树数据结构,其中每个节点最多有两个子节点,称为左子节点右子节点。使用集合理论概念的递归定义是(非空)二叉树是元组(L, ...
  • 给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一...
  • 众所周知只有前序遍历和后序遍历是不可能推出中序遍历的,所以我就不废话了 1.由树的前序遍历和中序遍历推后序遍历 假设树是酱婶的 首先前序遍历为 123456,中序遍历为324165,没什么问题,如果不会求前序或中序...
  • 1.前序遍历:根->左->右 2.中序遍历:左->根->右 3.后序遍历:左->右->根 于是上图中3种方法遍历结果 1.前序遍历:1 2 4 5 3 6 7 8 9 2.中序遍历:4 2 5 1 6 3 8 9 7 3.后序遍历:4 5 2 6 9 8 7 3...
  • 根据中序遍历前序遍历确定二叉树 对于一棵树而言,前序遍历的形式为: [根节点,[左子树的前序遍历],[右子树的前序遍历]]。 中序遍历形式为: [[左子树的中序遍历],根节点,[右子树的中序遍历]] 因此,只要我们...
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给...
  • 假设有棵树,长下面这个样子,它的前序遍历中序遍历,后续遍历都很容易知道。 PreO...
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给...
  • 根据中序遍历和后续遍历(前序遍历)构造二叉树 首先说说递归:对于大部分人而言递归总是那么难,因为它的过程比较抽象和复杂,但是说到底递归也是分治法的思想只要我们求得 相同子问题的解法那么对每个子问题求解并且...
  • 给树的后序和中序遍历,求先序遍历 假设有一棵树长这样 很容易写出他的后序遍历DBAGFEC 也很容易写出他中序遍历DABCGEF 1.后序遍历是前后根,根节点永远是最后一个,因此我们可以找到根节点c 2.要我们输出前序遍历...
  • 根据节点 V 在其中的访问次序,三种策略也相应地分别称作 先序遍历、中序遍历 后序遍历 。 可以根据节点 V 次序位置进行记忆,先序遍历中 V 位于前端,中序遍历中 V 位于中间,后序遍历中 V 位于后端。 例子1 ...
  • 假设有棵树,长下面这个样子,它的前序遍历中序遍历,后续遍历都很容易知道。...现在,假设仅仅知道前序和中序遍历,如何求后序遍历呢?比如,已知一棵树的前序遍历是”GDAFEMHZ”,而中序遍历是”ADEFGHM...
  • 前序遍历”、“中序遍历”、“后序遍历”里说的遍历,实际上是我们遍历二叉树的方式。 其实一张图就能给你解释什么叫中序遍历: (其中,箭头表示遍历顺序。二叉树本身的箭头没画。) 我们发现,这个“前”、“中...
  • 程序运行后直接输入节点以0结束后可输出二叉树的4种遍历,然后再通过输入前序中序遍历确定后序层序遍历。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,902
精华内容 26,760
关键字:

中序遍历和前序遍历相同

友情链接: ProgressBar.rar