精华内容
下载资源
问答
  • 二叉树的相互求解 已知前序中序求后序 已知后序前序求中序 已知前序后序求中序

    一:已知前序中序求后序

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    int pre[1001], in[1001];
    
    void SetPost(int a, int b, int n, int flag)
    {
        if(n <= 0) return ;
        if(n == 1)
        {
            printf("%d ",pre[a]);
            return ;
        }
        int i;
        for(i = 0; pre[a] != in[b+i]; i++);//找到划分点也就是根节点
        SetPost(a + 1, b, i, 0);//左子树的遍历
        SetPost(a + i + 1, b + i + 1, n - i - 1, 0);//右子树的遍历
        if(flag) printf("%d", pre[a]);
        else printf("%d ", pre[a]);
    }
    
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            for(int i = 1; i <= n; i++)
                scanf("%d",&pre[i]);
            for(int i = 1; i <= n; i++)
                scanf("%d",&in[i]);
            SetPost(1, 1, n, 1);
            printf("\n");
        }
        return 0;
    }
    /**
    8
    1 2 3 4 5 6 7 8
    3 2 5 4 1 7 6 8
    
    3 5 4 2 7 8 6 1
    */
    

    二:已知后序中序求前序

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    int post[1001], in[1001];
    
    void setPre(int a, int b, int n, int flag)
    {
        if(n <= 0) return ;
        if(n == 1)
        {
            printf(" %d",post[a]);
            return ;
        }
        int i;
        if(flag == 1) printf("%d", post[a]);
        else printf(" %d", post[a]);
        for(i = 0; post[a] != in[b+i]; i++);//找出根节点
        setPre(a-n+i, b, i, 0);//左子树的遍历
        setPre(a-1, b+i+1, n-i-1, 0);//右子树的遍历
    }
    
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            for(int i = 1; i <= n; i++) scanf("%d", &post[i]);
            for(int i = 1; i <= n; i++) scanf("%d", &in[i]);
            setPre(n, 1, n, 1);
            printf("\n");
        }
        return 0;
    }
    

    三:已知前序后序求中序

    由唯一输出yes+中序,不唯一输出no+任意一个中序

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <stdlib.h>
    #include <vector>
    using namespace std;
    
    int n, pre[50], post[50], ans[50], t = 0, flag = 1;
    
    int findFromPre(int x, int l, int r)
    {
        for(int i = l; i <= r; i++)
            if(x == pre[i])  return i;
        return -1;
    }
    
    void setIn(int prel, int prer, int postl, int postr)
    {
        if(prel == prer)
        {
            ans[t++] = pre[prel];
            return;
        }
        if(pre[prel] == post[postr])
        {
            int x = findFromPre(post[postr - 1], prel + 1, prer);
            if(x - prel > 1)
            {
                setIn(prel + 1, x - 1, postl, postl + x - prel - 2);
                ans[t++] = post[postr];
                setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
            }
            else
            {
                flag = 0;
                ans[t++] = post[postr];
                setIn(x, prer, postl + x - prel - 2 + 1, postr - 1);
            }
        }
    
    }
    
    int main()
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", &pre[i]);
        for(int i = 0; i < n; i++) scanf("%d", &post[i]);
        setIn(0, n-1, 0, n-1);
        if(flag) printf("Yes\n");
        else printf("No\n");
        printf("%d", ans[0]);
        for (int i = 1; i < t; i++)
            printf(" %d", ans[i]);
        printf("\n");
        return 0;
    }
    
    


    展开全文
  • 已知前序中序求后序

    千次阅读 2018-07-16 22:20:55
    题目描述: 输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树。...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。 思路...

    参考:https://blog.csdn.net/u010412719/article/details/49227411

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

    思路
    根据前序遍历的数组,arr[0]为根节点,在中序遍历中找到值等于arr[0]的位置index,则index的左边为此节点的左子树,右边为此节点的右子树。于是递归构建该节点的左右子树。

    测试用例:

    8

    1, 2, 4, 7, 3, 5, 6, 8

    4, 7, 2, 1, 5, 3, 8, 6

    ----------------------------------------

    5

    1, 2, 3, 4, 5

    5, 4, 3, 2, 1

    ----------------------------------------

    5

    1, 2, 3, 4, 5

    1, 2, 3, 4, 5

    ----------------------------------------

    1

    1

    1

    ----------------------------------------

    7

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

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

    ----------------------------------------

    7

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

    4, 2, 8, 1, 6, 3, 7

    //问题描述:已知一个二叉树的前序遍历和中序遍历,求改二叉树的后序遍历,
    //二叉树中没有相同的元素,数据为整型。
    //例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},
    //则重建二叉树并输出它的后序遍历序列。
    
    //思路
    //根据前序遍历的数组,arr[0]为根节点,在中序遍历中找到值等于arr[0]的位置index,
    //则index的左边为此节点的左子树,右边为此节点的右子树。于是递归构建该节点的左右子树。
    
    /*
    输入:
    输入可能包含多个测试样例,对于每个测试案例,
    
    输入的第一行为一个整数n(1<=n<=1000):代表二叉树的节点个数。
    
    输入的第二行包括n个整数(其中每个元素a的范围为(1<=a<=1000)):代表二叉树的前序遍历序列。
    
    输入的第三行包括n个整数(其中每个元素a的范围为(1<=a<=1000)):代表二叉树的中序遍历序列。
    
    输出:
    对应每个测试案例,输出一行:
    
    如果题目中所给的前序和中序遍历序列能构成一棵二叉树,则输出n个整数,代表二叉树的后序遍历序列,每个元素后面都有空格。
    
    如果题目中所给的前序和中序遍历序列不能构成一棵二叉树,则输出”No”。
    
    样例输入输出:
    8
    1 2 4 7 3 5 6 8
    4 7 2 1 5 3 8 6
    7 4 2 5 8 6 3 1
    
    8
    1 2 4 7 3 5 6 8
    4 1 2 7 5 3 8 6
    No
    
    */
    
    #include<stdio.h>
    #include<stdlib.h>
    #define true 1
    #define false 0
    typedef int bool;
    
    typedef struct BiTreeNode
    {
    	int data;
    	struct BiTreeNode *lchild;
    	struct BiTreeNode *rchild;
    }BiTreeNode,*BiTree;
    
    bool CanConstruct;
    
    void RebuildTree(BiTree *root,int len,int *PreTraverse,int *InTraverse)
    {
    	if (PreTraverse == NULL || InTraverse == NULL)
    	{
    		CanConstruct = false;
    		return;
    	}
    	if (len < 1)
    		return;
    	//在中序遍历中找到前序遍历的头结点的左右子结点
    	int index = -1;
    	for (int i = 0; i < len; i++)
    	{
    		if (PreTraverse[0] == InTraverse[i])
    		{
    			index = i;
    			break;
    		}
    	}
    	if(index==-1)//这种情况就是没有找到当前根结点在中序遍历的位置。因此不能重构 
    	{ 
    		CanConstruct = false;
    		return;
    	}
    	//找到了之后就开始构建此结点
    	//为当前结点分配空间 
    	*root = (BiTree)malloc(sizeof(BiTreeNode));
    	(*root)->data = PreTraverse[0];
    	(*root)->lchild = NULL;
    	(*root)->rchild = NULL;
    	//接下来开始构建该结点的左右子树。 
    	RebuildTree(&(*root)->lchild, index, PreTraverse + 1, InTraverse);
    	RebuildTree(&(*root)->rchild, len - index - 1, PreTraverse + index + 1, InTraverse + index + 1);
    }
    
    
    void PostOrderTree(BiTree root)
    {
    	if (!root)
    		return;
    	PostOrderTree(root->lchild);
    	PostOrderTree(root->rchild);
    	printf("%d ", root->data);
    }
    
    
    int main(void)
    {
    	int n;
    	while (scanf("%d", &n) && n > 0)
    	{
    		int *PreTraverse = (int *)malloc(sizeof(int)*n);
    		if (!PreTraverse)
    			exit(EXIT_FAILURE);
    		int *InTraverse = (int *)malloc(sizeof(int)*n);
    		if (!InTraverse)
    			exit(EXIT_FAILURE);
    		for (int i = 0; i < n; i++)
    		{
    			scanf("%d", PreTraverse[i]);
    		}
    		for (int i = 0; i < n; i++)
    		{
    			scanf("%d", InTraverse[i]);
    		}
    		BiTree root;
    		CanConstruct = true;
    		RebuildTree(&root, n, PreTraverse, InTraverse);
    		if (CanConstruct)
    		{
    			PostOrderTree(root);
    			printf("\n");
    		}
    		else
    		{
    			printf("No\n");
    		}
    	}
    	return 0;
    }

     

    展开全文
  • writer:pprp 思路很容易理解,但是实现还是有一点...//已知前序中序求后序 #include <iostream> using namespace std; //a是前序,b是中序 void hwg(string a,string b) { int ll,lr; for(...

    writer:pprp

    思路很容易理解,但是实现还是有一点难度,容易错

    参考书目:《算法竞赛宝典》

    代码如下:

    //已知前序中序,求后序
    #include <iostream>
    
    using namespace std;
    
    //a是前序,b是中序
    void hwg(string a,string b)
    {
        int ll,lr;
    
        for(unsigned int i = 0; i < b.length(); i++)
        {
            if(a[0] == b[i])    //找到根节点
            {
                ll = i;                   //分别计算出左右子树的长度
                lr = b.length()-1-ll;
                if(ll)                     //
                {
                    string part1(a,1,ll),part2(b,0,11);
                    hwg(part1,part2);
                }
                if(lr)
                {
                    string part3(a,1+ll,lr),part4(b,1+ll,lr);
                    hwg(part3,part4);
                }
                cout << a[0];
                break;
            }
        }
    }
    
    int main()
    {
        string a,b;
        cout <<"请输入前序:"<<endl;
        cin >> a;
        cout <<"请输入中序:"<<endl;
        cin >> b;
        cout <<"后序为:"<<endl;
        hwg(a,b);
        return 0;
    }

     

    转载于:https://www.cnblogs.com/pprp/p/7220630.html

    展开全文
  • 描述:二叉树的重建 已知前序 中序 求后序 来源:http://www.cnblogs.com/lovell-liu/archive/2011/09/06/2169170.html 日期:20140820 */ #include using namespace std; struct NODE{ NODE* pLeft; NODE* ...

    算法介绍:

    例如:先序遍历为DBACEGF,中序遍历为ABCDEFG。

    递归的方法解决问题
    先序串:DBACEGF,先序的第一个节点一定是根节点,这样我们就知道了根节点是D.
    再看中序, 在中序串之中,根结点的前边的所有节点都是左子树中,ABCDEFG,所以D节点前面的ABC就是左子树的中序串。再看前续串 DBACEGF,由于左子树的节点是ABC,我们可以得到左子树的前续周游的串为: BAC.子树的前序串BAC,和中序串ABC ,我们就可以递归的把左子树给建立起来。 同样,可以建立起右子树。 


    /*
    描述:二叉树的重建 已知前序 中序 求后序
    来源:http://www.cnblogs.com/lovell-liu/archive/2011/09/06/2169170.html
    日期:20140820
    */
    #include <iostream>
    using namespace std;
    
    struct NODE{
    	NODE* pLeft;
    	NODE* pRight;
    	char chValue;
    };
    
    int GetPos(char* str, char ch)
    	// 得到元素位于字符串的位置,就隐含了一个要求,字符不能重复
    {
    	for(int i=0; i<strlen(str); i++)
    	{
    		if(ch==str[i])
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    void Rebuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot)
    {
    	if(*pRoot==NULL)
    		return;
    	*pRoot=(NODE*)malloc(sizeof(NODE));
    	(*pRoot)->chValue = pPreOrder[0];
    	int i=GetPos(pInOrder, pPreOrder[0]);
    	if(i>=nTreeLen-1)
    		(*pRoot)->pRight=NULL;
    	if(i==0)
    		(*pRoot)->pLeft=NULL;
    	Rebuild(&pPreOrder[1], pInOrder, i, &(*pRoot)->pLeft);
    	Rebuild(&pPreOrder[i+1], &pInOrder[i+1],nTreeLen-i-1, &(*pRoot)->pRight); 
    }
    
    void PostOrderRetrieval(NODE* root)    //后序遍历树
    {
    	if(root==NULL)
    		return;
    	if(root->pLeft !=NULL)
    		PostOrderRetrieval(root->pLeft);
    	if(root->pRight !=NULL)
    		PostOrderRetrieval(root->pRight);
    	printf("%c ", root->chValue);
    }
    
    int main()
    {
    	NODE** root;
    	root = (NODE**)malloc(sizeof(NODE*));
    	Rebuild("abdehcfgij", "dbheafcgji", 10, root);
    	printf("后序遍历该树的结果为:\n");
    	PostOrderRetrieval(*root);
    	printf("\n");
    	free(*root);
    	free(root);
    }


    二叉树的遍历多例子,使用str输入  使用静态变量向树中添加

    #include<stdio.h>
    #include<stdlib.h>
    #include<string>
    #include <iostream>
    using namespace std;
    typedef struct node
    {
    	char num;
    	node* left;
    	node* right;
    }node,*pnode;
    
    static int len=-1;//全局的静态变量自动增加,确定加入的字符
    void CreatTree(pnode* p,string str)//注意是node* *
    {
    	char c;
    	node* tp;
    	c=str[++len];
    	
    	if ('#'==c)
    	{
    		*p=NULL;
    	}
    	else
    	{
    		tp=new(node);
    		tp->left=NULL;
    		tp->right=NULL;
    		tp->num=c;
    		*p=tp;
    		CreatTree(&(*p)->left,str);
    		CreatTree(&(*p)->right,str);
    	}
    
    }
    void DestroyTree(pnode *p)  
    { /* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */  
    	if(*p) /* 非空树 */  
    	{  
    		if((*p)->left) /* 有左孩子 */  
    			DestroyTree(&(*p)->left); /* 销毁左孩子子树 */  
    		if((*p)->right) /* 有右孩子 */  
    			DestroyTree(&(*p)->right); /* 销毁右孩子子树 */  
    		free(*p); /* 释放根结点 */  
    		*p=NULL; /* 空指针赋0 */  
    	}  
    }  
    void travel(node *p)
    {
    	if (p)
    	{
    		travel(p->left);
    		cout<<p->num<<" ";
    		travel(p->right);
    	}
    }
    
    int main() {
    	string str;
    	while (cin>>str)
    	{
    		len=-1;;
    		node *root=NULL;
    		CreatTree(&root,str);
    		travel(root);
    		cout<<endl;
    		DestroyTree(&root);
    	}
    	
    	return 1;
    }


    展开全文
  • 二叉树根据前序中序求后序
  • 传入前序遍历序列和中序遍历序列,后划分为左子树的前序中序遍历序列和右子树前序中序遍历序列,符合递归的思想,而后序遍历的遍历为:左->右->根,所以先递归左子树序列,后递归右子树序列,再输出根节点 ...
  • 详细清晰的思路介绍可以参见博客:已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历 下面给出题目和python实现代码: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历...
  • <题目重现> HDU - 1710 ...A binary tree is a finite ...仿照递归遍历的方法进行构建,将后序遍历的顺序直接保存至数组中,这里用到distance,distance的返回值为查找值到起始索引的距离,有关distance的介绍见...
  • 转载于:https://my.oschina.net/scutcoder/blog/680162
  • 网上看到的一篇关于前序中序求后续的文章,利用递归的方法,内容很不错,值得收藏。 题目描述: 输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的...
  • 已知前序中序 求后序-c代码实现

    千次阅读 2018-06-09 22:10:42
    #include "stdlib.h" #include "stdio.h" #include "string.h" /*此代码并未考虑边界和错误处理,只体现思路*/ void GetRear(char* pre, char* mid) ... //中序 GetRear(a,b); // printf("%s",a); }
  • 我们定义post_order(str1, str2)为一棵前序遍历的结果为str1,中序遍历的结果为str2的二叉树的后序遍历的结果。 如果要求解post-order(str1, str2)的话,首先不难发现,根据‘前序遍历’str1=‘根节点’+‘左子树的...
  • = in_order.length() ) //前序中序元素个数不相等出错 { cout ; exit(1); } if( pre_order.length() == 1 ) //递归终止 { if( pre_order != in_order ) //一个元素时前序中序不相等 { cout ; ...
  • 树就是很烦
  • 二叉树的遍历(前序中序、后序、已知中序求后序、已知后序求前序) 之前的一篇随笔(二叉树、前序遍历、中序遍历、后序遍历)只对二叉树的遍历进行了笼统的描述,这篇随笔重点对前、中、后序的遍历顺序...
  • 讨论本题:题目描述:若某二叉树的前遍历访问顺序是序abdgcefh,中序遍历顺序是dgbaechf,则后序遍历的访问顺序是...就说上面这棵二叉树的遍历结果吧:前序:abdgcefh中序:dgbaecfh后序:gdbehfca如何分析前序中序后序
  • A - Tree Recovery Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u SubmitStatus Description ...Little Valentine liked playing with binary trees very much....
  • 树-前序中序求后序

    2020-02-24 13:55:26
    已知前序中序求后序 #include <iostream> #include <cstdio> using namespace std; void post(char * pre, char * in, int len){ char ch; if(len == 0) return; ch = * pre; int i; for(i = 0; i...
  • 本题问题在于如何根据给定的前序中序结果画出二叉树,从而来确定后序的问题。 分析过程如下: (1)前序顺序为根左右,根据前序知道:a为根节点,然后观察a在中序遍历中的结果得到:dgb为a的左子树的中序遍历...
  • 已知前序中序求后序,我认为它就是一个DFS。 看了好多非链表的法,自己根据喜好写了个便于自己理解的。 #include #include char preorder[30]; char inorder[30]; char postorder[30]; void build(int n, ...
  • 1、先说根据前序中序求后序,前序总是沿着根往树的左边一直跑,所以前序遍历的前面肯定是根节点 中序则是按照:左—–根—–右 的顺序排列,其中左,右子树按照同样的结构,所以我们可以从前序遍历的根节点入手,...
  • 二叉树已知前序中序求后序序列(C语言)题目大体思路代码 题目 已知二叉树前序为 ABDFGCEH 后序序列为 BFDGACEH ,要求输出后序遍历为 FGDBHECA 大体思路 又先序得出根,先序的根后为左树一部分,我们再在中序序列...
  • 今天来总结下二叉树前序中序后序遍历相互法,即如果知道两个的遍历,如何第三种遍历方法,比较笨的方法是画出来二叉树,然后根据各种遍历不同的特性来,也可以编程出,下面我们分别说明。 首先,我们看...
  • 使用前序中序求后序遍历 使用前序中序求后续遍历参照这篇博客 # encoding: utf-8 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回构造的...
  • 已知前序中序求后序: 由前序可知顶点是G,由中序可知左子树为ADEF 右子树为:HMZ 在左子树中由前序可知,顶点为D,由中序可知子左子树为A,右子树为EF; 由前序知F为顶点,由中序知E为左子树 右子树HMZ由前序知M...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,130
精华内容 2,452
关键字:

已知前序中序求后序