精华内容
下载资源
问答
  • 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果. 8 / \ 6 10 / \ / \ 5 7 9 11因此返回true。如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。本题...
  • 以前大学学数据结果的时候,我们就知道,根据一棵树的先序遍历和中序遍历,或者后序遍历和中序遍历序列,都可以唯一地确定一棵树。
  • 有一个整数型列表,判断该列表是否为对应二叉搜索树的后序遍历结果 ''' 二叉搜索树 二叉排序树 二叉查找树 前序遍历 中序遍历 后序遍历 根节点 算法: 1. 找到根节点 2. 遍历序列,找到第一个大于根节点的元素i,则i...
  • 题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解题思路:递归 class Solution: def VerifySquenceOfBST(self,...
  • 根据二叉树的中序和后序遍历结果画出二叉树: 1.首先根据后序遍历结果判断根节点(最右边的元素); 2.在中序遍历结果中找到该根节点,该节点的左边为根节点的左子树,节点右边为根节点的右子树; 3.回到后序遍历中...

    根据二叉树的中序和后序遍历结果画出二叉树:
    1.首先根据后序遍历结果判断根节点(最右边的元素);
    2.在中序遍历结果中找到该根节点,该节点的左边为根节点的左子树,节点右边为根节点的右子树;
    3.回到后序遍历中找点左子树在后序遍历中最右边的元素即为左子树的根节点;
    4.回到中序遍历中找到步骤3中的左子树的根节点,跟步骤2一样判断根节点左子树的根节点对应的其左子树和右子树;
    循环步骤2,3
    最后输出结果。

    展开全文
  • 用非递归后序遍历二叉树的方式实现的表达式计算,进行了精细的表达式逻辑判断和处理,可进行加减乘除、括号、小数的计算。项目结构清晰,基本都有代码注释,可用于数据结构实验。同为学习人,能力有限,不足之处还请...
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 【二叉树】由前序和中序结果求后序遍历结果 构造二叉树前序遍历由前序和中序遍历构建二叉树 求后序遍历结果三级目录 前序遍历 前序遍历:若二叉树为空,则空操作返回,否则先访问根节点,再遍历左子树再遍历右子树。...

    前序遍历

    前序遍历:若二叉树为空,则空操作返回,否则先访问根节点,再遍历左子树再遍历右子树。
    中序遍历:若树为空,则空操作传回,否则从根节点开始(注意不是访问)中序遍历根节点的左子树,然后访问根节点,再中序遍历右子树。
    后序遍历:若树为空,则空操作传回,否则从左到右先叶子后节点的方式遍历访问左右子树,最后访问根节点。
    前序:根-左子树-右子树
    中序:左子树-根-右子树
    后序:左子树-右子树-根

    以该树为例
    前序遍历:ABDGHICEJF
    中序遍历:GDIHBAEJCF
    后旭遍历:GIHDBJEFCA
    运用递归容易求解

    由前序和中序遍历构建二叉树 求后序遍历结果

    先根据前序遍历找到根节点,再在中序遍历结果中找到根节点的位置,根节点前面就是左子树,右边就是右子树。
    以上例:由前序遍历得到A为根节点,由中序遍历得到根节点A左子树为GDIHB,右子树为EJCF。再在前序遍历中找到左子树右子树的根节点。
    由上述重复性的算法可知要用递归求解。
    下面展示一些 内联代码片

    // 由前序和中序求后序
    
    // An highlighted block
    void CreateTree(BiTree*& root, char* pre_str, char* in_str, int length)
    {
    	if (length == NULL || pre_str == NULL || in_str == 0)
    	{
    		return;
    	}
    	root = (BiTree*)malloc(sizeof(BiTree));
    	(root)->data = pre_str[0];
    	(root)->lchild = NULL;
    	(root)->rchild = NULL;
    	char* p = strchr(in_str, pre_str[0]);
    	if (p != NULL)
    	{
    		int nLeft = p - in_str;//头指针相减 左子树长度
    		CreateTree((root)->lchild, pre_str + 1, in_str, nLeft);
    		CreateTree((root)->rchild, pre_str +nLeft+ 1, in_str + nLeft + 1, length - nLeft-1);
    	}
    }
    

    后序遍历(递归表示)

    // An highlighted block
    void fun1(BiTree* root)
    {
    	if (root == NULL)
    		return;
    	fun1(root->lchild);
    	fun1(root->rchild);
    	cout << root->data;
    }
    

    后序遍历(非递归)

    由后序和中序遍历构建二叉树 求前序遍历结果

    下面展示一些 内联代码片

    // 直接上代码
    
    // An highlighted block
    void CreateTree_2(BiTree*& root, char* re_str, char* in_str, int length)
    {
    	if (length == NULL || re_str == NULL || in_str == 0)
    	{
    		return;
    	}
    	root = (BiTree*)malloc(sizeof(BiTree));
    	(root)->data = re_str[length-1];
    	(root)->lchild = NULL;
    	(root)->rchild = NULL;
    	char* p = strchr(in_str, re_str[length-1]);
    	if (p != NULL)
    	{
    		int nLeft = p - in_str;//头指针相减 左子树长度
    		CreateTree_2((root)->lchild, re_str, in_str, nLeft);//左子树
    		CreateTree_2((root)->rchild, re_str + nLeft , in_str + nLeft + 1, length - nLeft - 1);//右子树
    	}
    }
    

    下面展示一些 内联代码片

    // 前序遍历(递归)
    
    // An highlighted block
    void fun1(BiTree* root)
    {
    	if (root == NULL)
    		return;
    	cout << root->data;
    	fun1(root->lchild);
    	fun1(root->rchild);
    }
    
    展开全文
  • 首先得明白什么是二叉树的先序中序后序遍历: c++ 二叉树的创建 前中后序遍历 以及遇到的坑 给出先序和中序遍历重建二叉树: 思路: ...如先序遍历结果 1 2 , 后序遍历结果 2 1 ,我们只知道根节点为1

    首先得明白什么是二叉树的先序中序后序遍历:

    c++ 二叉树的创建 前中后序遍历 以及遇到的坑

    给出先序和中序遍历重建二叉树:

    思路:
    1、二叉树的先序遍历的第一个结点是根节点;
    2、中序遍历的根节点左边的序列是左子树的结点,右边的序列是右子树的结点;
    3、左子树和右子树分别重复步骤1、2;

    步骤如下:
    在这里插入图片描述

    给出先序和后序遍历重建二叉树:

    这个无法给出正确的树结构,因为先序(根左右)和后序(左右根)遍历的左右孩子遍历的顺序一样,无法区分。
    如先序遍历结果 1 2 , 后序遍历结果 2 1 ,我们只知道根节点为1,却不知道2是左孩子还是右孩子

    给出中序和后序遍历重建二叉树:

    与先序和中序的思路差不多:
    1、二叉树的后序遍历的最后一个结点是根节点;
    2、中序遍历的根节点左边的序列是左子树的结点,右边的序列是右子树的结点;
    3、左子树和右子树分别重复步骤1、2;

    步骤如下:
    在这里插入图片描述

    最后:

    如果想看c++代码实现:c++ 刷题 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。

    展开全文
  • 数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
  • 二叉树先序遍历结果为aferpkwhjl, 中序遍历结果为repfwkajhl,那么后序遍历结果是什么呢? 先序遍历的顺序是:根 -左子树 -右子树 中序遍历的顺序是:左子树 -根 -右子树 后序遍历的顺序是:左子树 -右子树 -根 ...

    二叉树先序遍历结果为aferpkwhjl, 中序遍历结果为repfwkajhl,那么后序遍历结果是什么呢?
    先序遍历的顺序是:根 -左子树 -右子树
    中序遍历的顺序是:左子树 -根 -右子树
    后序遍历的顺序是:左子树 -右子树 -根
    由此可以得到一个结论:先序遍历的第一个元素一定是树的根,中序遍历根的左侧一定是左子树的遍历结果, 右侧一定是
    右子树遍历的结果
    那么这道题的解决思路是:1.根据先序遍历的结果可以得到当前树的根
    2. 根据中序遍历的结果和前面得到的根, 可以得到左子树的中序遍历结果和右子树的中序遍历

    3.根据左子树中序遍历结果可以在当前树的先序遍历结果中得到左子树的先序遍历结果
    (左子树中元素的顺序要与当前树先序遍历结果中元素的顺序一致),右子树也是如此
    4.将左子树和右子树分别设置为当前树。重复进行1-3步骤(这是树的福利, 逻辑很简单,
    使用递归后,代码就简单多了)
    我们可以采用单向链表来存储树的先序,中序遍历结果;
    link.h

    #ifndef LINK
    #define LINK
    
    #define SUCCESS 10000
    #define FAILURE 10001
    
    typedef char ElemType;
    
    typedef struct node      //链表的节点
    {
        ElemType data;
        struct node * next;
    }Node, *pNode;
    
    int Init(pNode *); //初始化链表(建立头节点)
    int Insert(pNode, ElemType);//尾插法
    int Delete(pNode, ElemType);//根据节点的数据,来删除对应的节点
    pNode Find(pNode, ElemType);//根据节点的数据,来找到对应节点的前一个节点的指针(得到前一个节点的指针,是为了方便在单向链表中删除该节点)
    int GetLength(pNode);//得到链表中节点的个数,本次程序并未用到该接口, 可以不用理他
    int Destroy(pNode * phead);//销毁一个链表,即删除所有的节点(包括头节点),本次程序中新生左子树链表直接继承当前树链表,所以不需要该接口来销毁一个链表,只需要将当前树的根节点free掉即可
    pNode CreateLink(ElemType e[], int length);//根据树的先序,中序遍历结果,建立相对应的链表,本次程序中只在main中建立初始树的先序,中序遍历链表, 后面子树遍历链表并未用到该接口
    
    #endif
    

    link.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "link.h"
    
    int Init(pNode *phead)
    {
        if (phead == NULL)
            return FAILURE;
        (*phead) = (pNode)malloc(sizeof(Node) * 1); 
        if (*phead == NULL)
            return FAILURE;
        (*phead)->next = NULL;
        return SUCCESS;
    }
    int Insert(pNode head, ElemType e)
    {
        if (head == NULL)
            return FAILURE;
        pNode p = head;
        while(p->next != NULL)
            p = p->next;
        pNode newnode = (pNode)malloc(sizeof(Node) * 1); 
        if (newnode == NULL)
            return FAILURE;
        newnode->data = e;
        newnode->next = NULL;
        p->next = newnode;
        return SUCCESS;
    }
        int Delete(pNode head, ElemType e)
    {
        pNode ret = Find(head, e);
        if (ret == NULL)
            return FAILURE;
        pNode p = ret->next;
        ret->next = p->next;
        free(p);
        return SUCCESS;
    }
    pNode Find(pNode head, ElemType e)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        pNode p = head;
        while (p->next != NULL && p->next->data != e)
            p = p->next;
        if (p->next == NULL)
            return NULL;
        return p;
    
    }
    /*
    int GetLength(pNode head)
    {
        if (head == NULL)
            return  FAILURE;
        int count = 0;
        pNode p = head;
        while (p->next != NULL)
        {
            count++;
            p = p->next;
        }
        return count;
    }
    int Destroy(pNode * phead)
    {
        if (phead == NULL || *phead == NULL)
            return FAILURE;
        pNode p = *phead, pp;
        while (p != NULL)
        {
            pp = p->next;
            free(p);
            p = pp;
        }
        phead = NULL;
        return SUCCESS;
    }
    */
    pNode  CreateLink(ElemType e[], int length)
    {
        pNode head;
        int ret = Init(&head);
        if (ret == FAILURE || e == NULL)
            return NULL;
        for (ret = 0; ret < length; ret++)
        {
            Insert(head, e[ret]);
        }
        return head;
    }
    

    tree.h

      #ifndef TREE
        #define TREE
        #include "link.h"
        void InOrder_Left_Right(ElemType rootdata, pNode In, pNode * LeftIn, pNode * RightIn);
        void PreOrder_Left_Right(pNode Pre, pNode In, pNode * LeftPre, pNode * RightPre, pNode * LeftIn, pNode * RightIn);
        void Post(pNode Pre, pNode In);
        
        #endif
    

    tree.c

    #include "link.h"
    #include "tree.h"
    
    void InOrder_Left_Right(ElemType rootdata, pNode In, pNode * LeftIn, pNode * RightIn)
    {
        if (LeftIn == NULL || Init(RightIn) != SUCCESS || In == NULL)
            return;
        pNode ret;
        *LeftIn = In; //左子树中序链表直接继承当前树中序链表,就可以省去销毁当前树链表的步骤
        if (Init(RightIn) == FAILURE)
            return;
        ret = Find(In, rootdata);
        if (ret == NULL)
            return;
        else 
        {   
            (*RightIn)->next = ret->next->next;//本质是建立右子树中序遍历链表
            free(ret->next);//删除当前树的根节点
            ret->next = NULL;//本质是建立左子树中序遍历链表
        }   
    }
    void PreOrder_Left_Right(pNode Pre, pNode In, pNode * LeftPre, pNode * RightPre, pNode * LeftIn, pNode * RightIn)
    {
        if (LeftPre == NULL || Init(RightPre) !=  SUCCESS || Pre == NULL || In == NULL || Pre->next == NULL || In->next == NULL)
            return ;
        ElemType rootdata = Pre->next->data, e;
        pNode p, ret;
        InOrder_Left_Right(rootdata, In, LeftIn, RightIn);
        (*LeftPre) = Pre;//左子树先序链表直接继承当前树先序遍历链表
        Delete(*LeftPre, rootdata);//删除根节点
        p = Pre->next;
        while (p != NULL)
        {
            ret = Find(*LeftIn, p->data);
            e = p->data;
            p = p->next;
            if (ret == NULL)
            {
                Insert(*RightPre, e);//本质是建立右子树先序遍历链表
                Delete(*LeftPre, e);//本质是建立左子树先序遍历链表
            }
        }
    }
    void Post(pNode Pre, pNode In)
    {
        if (Pre->next == NULL || In->next == NULL || Pre ==  NULL || In == NULL)
            return;
        ElemType e = Pre->next->data;//先保存根节点数据,后面Pre链表会被修改,所以一定要先保存一下
        pNode LeftPre, LeftIn, RightPre, RightIn;//建立左子树,右子树先序,中序遍历链表
        PreOrder_Left_Right(Pre, In, &LeftPre, &RightPre, &LeftIn, &RightIn);
        Post(LeftPre, LeftIn);//先左子树
        Post(RightPre, RightIn);//然后右子树
        printf("%c",e);//最后根节点
    }
    

    main.c

     #include <stdio.h>
        #include <stdlib.h>
        #include <string.h>
        #include "tree.h"
        #include "link.h"
        
        int main()
        {
            ElemType pre[20] = "aferpkwhjl";
            ElemType in[20] = "repfwkajhl";
            pNode Pre = CreateLink(pre, strlen(pre));
            pNode In = CreateLink(in, strlen(in));
            Post(Pre, In);
            printf("\n");
            return 0;
        }
    ~    
    

    结果为:rpewkfjlha

    展开全文
  • 按要求输入二叉树,然后执行可输出先序 中序 后序遍历二叉树的结果
  • 题目链接: PTA L2-004 递归原理分析: ...首先分解求后序遍历结果的过程: 求出左子树的后序遍历结果 求出右子树后序遍历的结果 将当前子树的根节点加入后序遍历的结果中去 void getPost(int roo.
  • BinaryTree 基于MFC的二叉树的先序、中序、后序遍历的动画演示
  • 1)根据给定二叉树的先序遍历和中序遍历结果,构造出该二叉树; (2)给出该二叉树的后序遍历结果; (3)判定该二叉树是否为平衡二叉树;
  • 本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作。分享给大家供大家参考,具体如下: 实现一个功能:  输入:一颗二叉树的先序和中序遍历  输出:后续遍历 思想: 先序遍历中,第一个元素...
  • 最近在学习二叉树,遇到了这样一题,在这里给大家提供一种方法,可能不是最好的,仅供大家参考和相互交流学习。 已知一个二叉树前序遍历、中序遍历的结果,请确定该...则应该能够得出后序遍历结果为:D G E B H F ...
  • //C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include “stdafx.h”#include<iostream>#include<string>#include <stack>using namespace std;template<class>struct BiNode{ T data; struct...
  • 我们先理解一下前中后序遍历,这是基础。 //前序遍历 void Tree::PreOrderTraverse(BiTree *T) { if(!T) { return ; } else { cout&lt;&lt;T-&gt;data&lt;&lt;" "; ...
  • 前序、中序、后序遍历结果重建二叉树推导遍历结果前序、中序遍历结果重建二叉树中序、后续遍历结果重建二叉树结论源代码 推导遍历结果 前序、中序遍历结果重建二叉树 已知一棵二叉树的前序遍历结果为{1,2,4,5,3,6},...
  • 已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
  • 编写程序,用先序递归遍历法建立二叉树的二叉链表存储结构,然后输出其先序、中序、后序遍历第k个访问结点。二叉树结点数据类型建议选用字符类型且各结点数据域值互不相同;输出用结点数据域的字符表示;求第k个访问...
  • C语言实现数据结构中根据中序、后序遍历构建树,并进行先序与层次遍历,以树形结构输出,附有详细中文注释
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • 已知一棵二叉树,如果先序遍历的节点顺序是:ADCEFGHB,中序遍历是:CDFEGHAB,则后序遍历结果为:()   A. CFHGEBDA   B. CDFEGHBA   C. FGHCDEBA   D. CFHGEDBA  解析:由先序遍历序列和中序遍历...
  • 二叉树前序遍历规则是:根、左子树、右子树;中序遍历规则是:左子树、根、右子树;后序遍历规则是:左子树、右子树、根。
  • 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。 目录 题目描述 代码实现 题目描述 二叉树的后序遍历。输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是...
  • c语言,二叉树的先序,中序,后序遍历以及叶子结点数目

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 104,245
精华内容 41,698
关键字:

后序遍历结果