精华内容
下载资源
问答
  • 中序遍历输出
    2022-02-25 10:22:38

    4-15 根据后序和中序遍历输出先序遍历 (15 分)
    本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

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

    输出格式:
    在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格,行末不得有多余空格。

    输入样例:
    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
    结尾无空行
    输出样例:
    Preorder: 4 1 3 2 6 5 7
    这道题就是前面那道题前序和中序转后序的翻版,只要改一下递归的左右调用就可以,然后要注意的是调用的接口,是0到n-1

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node
    {
        int data;
        struct BiTNode*left,*right;
    }*Tree;
    Tree PreInOd(int post[],int i,int j,int in[],int k,int h);
    Tree PreInOd(int post[],int i,int j,int in[],int k,int h)
    {
        if((j-i)<0)return NULL;
    
          Tree head=(Tree)malloc(sizeof(struct node));
        head->data=post[j];
        int m=k;
    
        while(in[m]!=post[j])
           {
              m++;
           }
          head->left=PreInOd(post,i,i+m-k-1,in,k,m-1);
    
            head->right=PreInOd(post,i+m-k,j-1,in,m+1,h);
        return head;
    }
    void PreOrder(Tree t);
    void PreOrder(Tree t)
    {
        if(t==NULL)return ;
        printf("%d ",t->data);
        PreOrder(t->left);
        PreOrder(t->right);
    }
    main()
    {
        Tree t;
        int n;
        scanf("%d",&n);
        int a[30],b[30];
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int j=0;j<n;j++)
        {
            scanf("%d",&b[j]);
        }
       t= PreInOd(a,0,n-1,b,0,n-1);//注意这里
       printf("Preorder: ");
       PreOrder(t);
    }
    
    
    更多相关内容
  • 本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作。分享给大家供大家参考,具体如下: 实现一个功能:  输入:一颗二叉树的先序和中序遍历  输出:后续遍历 思想: 先序遍历中,第一个元素...
  • 本文实例讲述了C++基于先序、中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含...
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 根据后序和中序遍历输出先序遍历题目介绍分析过程1.首先根据后序遍历确定根节点2.在中序遍历中找到根节点对应的下标3.计算分割区间的左右位置4.终止条件函数代码实现完整代码总结 题目介绍 本题要求根据给定的一棵...

    题目介绍

    本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

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

    输出格式:
    在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格,行末不得有多余空格。

    输入样例:

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

    输出样例:

    Preorder: 4 1 3 2 6 5 7


    分析过程

    直接用题目所给的示例来分析:

    1.首先根据后序遍历确定根节点

    2.在中序遍历中找到根节点对应的下标

    先处理父亲节点
    在这里插入图片描述

    TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd,
    	vector<int>& postorder, int postorderBegin, int postorderEnd) {
    	int rootValue = postorder[postorderEnd - 1];
    	    TreeNode* root = new TreeNode(rootValue);	//创建父亲节点
    	for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; ++delimiterIndex) {
    		if(inorder[delimiterIndex] == rootValue) { //找到中序遍历中父亲节点对应的下标
    			break;
    		}
    	}
    }
    

    3.计算分割区间的左右位置

    计算中序遍历左边区间边界,再计算右边区间边界,对应二叉树的先序序列创建。

    注意:区间形式为 [......) ,既Begin均能取到,End均不取

    在这里插入图片描述
    在这里插入图片描述

    root->left = traversal(inorder, inorderBegin, delimiterIndex,
        	postorder, postorderBegin, postorderBegin + delimiterIndex - inorderBegin);
    root->right = traversal(inorder, delimiterIndex + 1, inorderEnd,
        	postorder, postorderBegin + delimiterIndex - inorderBegin, postorderEnd - 1);
    

    4.终止条件

    1. 当后序区间的区间长度为零

    返回nullptr

    if(postorderBegin == postorderEnd) return nullptr;
    
    1. 区间长度为1

    不用额外计算区间了,区间里只有一个值,直接返回root

    if(postorderEnd - postorderBegin == 1) return root;
    

    函数代码实现

    TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd, 
    	vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if(postorderBegin == postorderEnd) return nullptr;
        
        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);   //创建父亲节点
        
        if(postorderEnd - postorderBegin == 1) return root;
        
        int delimiterIndex;     //分割位置的下标
        for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; ++delimiterIndex) {
        	if(inorder[delimiterIndex] == rootValue) {	//找到中序遍历中父亲节点对应的下标
         		break;
         	}
    	}
        
        root->left = traversal(inorder, inorderBegin, delimiterIndex,
        	postorder, postorderBegin, postorderBegin + delimiterIndex - inorderBegin);
        root->right = traversal(inorder, delimiterIndex + 1, inorderEnd,
        	postorder, postorderBegin + delimiterIndex - inorderBegin, postorderEnd - 1);
        
        return root;
    }
    

    完整代码

    如下:

    #include<bits/stdc++.h>
    using namespace std;
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode():val(0), left(nullptr), right(nullptr) {}
        TreeNode(int value):val(value), left(nullptr), right(nullptr) {}
    };
    TreeNode* traversal(vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd)
    {
        if(postorderBegin == postorderEnd) return nullptr;
        
        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);   //创建父亲节点
        
        if(postorderEnd - postorderBegin == 1) return root;
        
        int delimiterIndex;     //分割位置的下标
        for(delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; ++delimiterIndex) if(inorder[delimiterIndex] == rootValue) break;
        
        root->left = traversal(inorder, inorderBegin, delimiterIndex, postorder, postorderBegin, postorderBegin + delimiterIndex - inorderBegin);
        root->right = traversal(inorder, delimiterIndex + 1, inorderEnd, postorder, postorderBegin + delimiterIndex - inorderBegin, postorderEnd - 1);
        
        return root;
    }
    void Preorder(TreeNode* node) {
        if(node == nullptr) return;
        cout << " " << node->val;
        Preorder(node->left);
        Preorder(node->right);
    }
    int main()
    {
        int n;
        cin >> n;
        vector<int> inorder(n);
        vector<int> postorder(n);
        for(int i = 0; i < n; ++i) cin >> postorder[i];
        for(int i = 0; i < n; ++i) cin >> inorder[i];
        cout << "Preorder:";
        Preorder(traversal(inorder, 0, n, postorder, 0, n));
        return 0;
    }
    

    总结

    后序遍历和中序遍历的容器可以放在主函数外面,这样函数在传参的时候可以少传两个参数,代码会简洁一点。

    展开全文
  • c语言下的线索二叉树的前序遍历建立,中序遍历线索化,中序遍历输出结果 结点和树数据准备 typedef char ElemType; //线索存储标志位 //Link表示指向左右孩子的指针 //Thread表示指向前驱后继的线索 typedef enum {...

    c语言下的线索二叉树的前序遍历建立,中序遍历线索化,中序遍历输出结果

    结点和树数据准备

    typedef char ElemType;
    
    //线索存储标志位
    //Link表示指向左右孩子的指针
    //Thread表示指向前驱后继的线索
    typedef enum {Link, Thread}PointerTag;
    
    typedef struct BiThrNode
    {
    	char data;
    	struct  BiThrNode* lchild, * rchild;
    	PointerTag ltag;
    	PointerTag rtag;
    }BiThrNode, *BiThrTree;
    
    BiThrTree pre;
    

    前序遍历输入数据
    //创建一颗二叉树,约定用户遵照前序遍历的方式输入数据

    void CreateBiTree(BiThrTree* T)
    {
    	char c;
    	scanf("%c", &c);
    	if (' ' == c)
    	{
    		*T = NULL;
    	}
    	else
    	{
    		*T = (BiThrNode*)malloc(sizeof(BiThrNode));
    		(*T)->data = c;
    		(*T)->ltag = Link;
    		(*T)->rtag = Link;
    
    		CreateBiTree(&(*T)->lchild);
    		CreateBiTree(&(*T)->rchild);
    	}
    }
    

    //中序便利线索化

    void InThreading(BiThrTree T)
    {
    	if (T)
    	{
    		//递归左孩子线索化
    		InThreading(T->lchild);
    
    		//结点处理
    		//如果该节点没有左孩子,设置ltag为Thread,并把lchild指向刚刚访问的结点
    		if (!T->lchild)
    		{
    			T->ltag = Thread;
    			T->lchild = pre;
    		}
    
    		if (!pre->rchild)
    		{
    			pre->rtag = Thread;
    			pre->rchild = T;
    		}
    
    		pre = T;
    
    		//递归右孩子结点化
    		InThreading(T->rchild);
    	}
    }
    

    //前序遍历建立线索二叉树之前需要先初始化头结点Pre

    void InOrderThreading(BiThrTree *p, BiThrTree T)
    {
    	*p = (BiThrTree)malloc(sizeof(BiThrNode));
    	(*p)->ltag = Link;
    	(*p)->rtag = Thread;
    	(*p)->rchild = *p;
    	if (!T)
    	{
    		(*p)->lchild = *p;
    	}
    	else
    	{
    		(*p)->lchild = T;
    		pre = *p;
    		InThreading(T);
    		pre->rchild = *p;
    		pre->rtag = Thread;
    		(*p)->rchild = pre;
    	}
    }
    

    //访问数据节点的函数

    void visit(char c)
    {
    	printf("%c", c);
    }
    

    //中序遍历二叉树,迭代法

    void InOrderTraverse(BiThrTree T)
    {
    	BiThrTree p;
    	p = T->lchild;
    
    	while (p != T)
    	{
    		while (p->ltag == Link)
    		{
    			p = p->lchild;
    		}
    
    		visit(p->data);
    
    		while (p->rtag == Thread && p->rchild != T)
    		{
    			p = p->rchild;
    			visit(p->data);
    		}
    
    		p = p->rchild;
    	}
    }
    

    //测试函数

    void func2()
    {
    	BiThrTree P, T = NULL;
    	CreateBiTree(&T);
    	InOrderThreading(&P, T);
    	printf("中序遍历输出结果为:\n");
    	InOrderTraverse(P);
    	printf("\n");
    }
    

    运行结果:
    在这里插入图片描述
    此处的输入为:
    abcd___e__fg__h__h_i__
    中序遍历的结果应该是:
    dcbeagfhi
    和运行截图一致
    每个_都是空格,纸上的二叉树是这样的:
    在这里插入图片描述

    展开全文
  • 分析二叉树遍历的性质 有上述性质,可以分享

    分析二叉树遍历的性质

    根据后序和中序遍历输出先序遍历:
    在这里插入图片描述
    由上述性质,易做:

    题目

    在这里插入图片描述

    code:

    #include<iostream>
    using namespace std;
    const int N = 110;
    
    void make_a(int *c,int *b,int n){
             if(n == 0) return;  
             int x = c[n-1];
             int i;
             for(i=0;i<n;i++)
                   if(b[i] == x) break;
             cout << " " << x;
             make_a(c,b,i);
             make_a(c+i,b+i+1,n-i-1);   // 后缀是从c+i开始,是因为后缀删除的根节点是最后一个节点,并不是第i个节点,所以后缀时仍要用第i个节点,但是不需要用最后一个节点
                                        // 中缀要把第i个结点删除,所以中缀表达式是从i+1个元素开始的;(即后缀每次删最后元素,中缀删掉是中间元素)
    }
    
    int main(){
        int b[N],c[N];  // b->中缀    c->后缀
        int n;
        cin >> n;
        for(int i=0;i<n;i++)
            cin >> c[i];
        for(int i=0;i<n;i++)
            cin >> b[i];
        cout << "Preorder:";
        make_a(c,b,n);
        return 0;
    }
    
    
    

    attention:

    分析后缀、中缀有差别(因为元素的位置不同)
    后缀是从第i个元素(即元素c+i)开始,是因为后缀删除的根节点是最后一个节点,并不是第i个节点,所以后缀时仍要用第i个节点,但是不需要用最后一个节点
    中缀要把第i个结点删除,所以中缀表达式是从i+1个元素(即元素b+i+1)开始的;(即后缀每次删最后元素,中缀删掉是中间元素)

    ps

    补充:树的计数

    已知先序序列和中序序列可确定一棵唯一的二叉树;

    已知后序序列和中序序列可确定一棵唯一的二叉树;

    已知先序序列和后序序列不能确定一棵唯一的二叉树。

    improve: 根据前序和中序遍历输出先序遍历 -> 传送门

    展开全文
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式 第一行给出正整数N (≤30),是树中结点的个数。随后两行,每行给出N 个整数,分别对应后序遍历和中序遍历结果,数字间以...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间...
  • 随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出格式: 在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格,行末不得有多余...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间...
  • PTA—根据后序和中序遍历输出先序遍历 (C语言实现) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以...
  • 7-8 根据后序和中序遍历输出先序遍历 (20分) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数...
  • 7-6 根据后序和中序遍历输出先序遍历 (10 分) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间...
  • 根据先序遍历和中序遍历输出后序遍历 #include <stdio.h> #include <stdlib.h> char Pre[100], In[100]; typedef struct Node { char Data; struct Node* Left; struct Node* Right; }*Tree; Tree Build...
  • 根据给定的二叉树结构描述字符串,输出该二叉树按照中序遍历结果字符串。中序遍历顺序为:左子树,根结点,右子树。输入描述: 由大小写字母、左右大括号、逗号组成的字符串:输出描述: 输出一个字符串,为二叉树中序...
  • 7-2 根据后序和中序遍历输出先序遍历 (25 分) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数...
  • 根据树的前序遍历和中序遍历构造树并输出后序遍历代码如下: <?php class BinaryTreeNode{ public $m_value; public $m_left; public $m_right; } function ConstructCore($preorder,$inorder){ if(count($...
  • 下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,749
精华内容 22,299
关键字:

中序遍历输出