精华内容
下载资源
问答
  • 二叉树的前序中序后序遍历
  • 树的递归、非递归前序中序后序遍历实现,层序遍历,及树的Morris前序中序后序遍历实现。main函数有测试样例,测试样例是A B D F E C G H I 。注意空出的地方是空格,前序建树。
  • 二叉树,前序中序中序后序构造,前序、中序、后序遍历
  •    可能对二叉树不熟悉的朋友看到这里的时候就蒙了,不知道应该怎么做下去了,其实这个是很简单的,我们只需要记住前序 中序 后序的含义即可:     前序: 根左右;     中序:左根右;     后序:左右根;   ...

       看到一个面试题挺有意思的,记录分享一下.说已知一颗二叉树,如果中序遍历是:DBFEACHGI,后序遍历的节点顺序是:DFEBHIGCA.
       可能对二叉树不熟悉的朋友看到这里的时候就蒙了,不知道应该怎么做下去了,其实这个是很简单的,我们只需要记住前序 中序 后序的含义即可:
        前序: 根左右;
        中序:左根右;
        后序:左右根;
      不知道朋友们有没有发现一个规律,前序 中序 后序 变化的只是他的根节点,而他的左右子节点的顺序 一直是 从左到右排序的.所以我们只需要记住他根节点的位置即可.下面是一直我在网上找的二叉树的图片:
    满二叉树
      我们可以先用这个图练习一下我们前中后序的一个数据结构.首先前序是: 根左右, 我们可以先找出他的根节点 :A B C;
    然后BC呢还有他的子节点,然后我们就可以根据规则:根左右 的顺序把他的子节点添加进去: A + DBE + FCG = ADBEFCG; 所以他的前序就是: ADBEFCG;
      同样的道理 中序是:左根右; 就可以先得出 B  A  C,然后我们在把B
    C的子节点也给添加进去: DBE + A + FCG = DBEAFCG;所以他的中序就是:DBEAFCG ;
      然后在看他的后序:左右根, 首先我们可以首先得出: B  C  A,然后在把BC的子节点加进去:DEB + FGC + A=DEBFGCA,所以他的后序就是DEBFGCA.
    这个时候我们就可以得出上面二叉图的前序 中序 后序 的数据了.
      这个时候在来看我们的面试题:

      说已知一颗二叉树,如果中序遍历是:DBFEACHGI,后序遍历的节点顺序是:DFEBHIGCA.
    然后通过中序:左根右与后序的:左右根,就可以先确定根节点是 A,
    所以DBFE是根节点A的左侧树,
    CHGI是根节点A的右侧树.
    而他的左右树都是4位,由此推断左右两边的树不是二叉满树
    

      这个时候我们在看他的后序DFEBHIGCA,然后我们在根据后序的公式:左右根,进行嵌套

    后序:左右根
       DFEB是根节点A的左侧树
       HIGC是根节点A的右侧树.
    就可以得出 B 是左侧树的根, C 是右侧树的根节点,
    中序:左根右
       DBFE是根节点A的左侧树,
       CHGI是根节点A的右侧树.
       通过后序得到左侧树的根节点是 B ,而上面我们也通过中序得到了左右树不是满树.
       这个时候我们可以根据中序的左根右进行嵌套左侧树. 
       B 是根节点,D 是 B 的左侧树,而左侧树是4位,不是一个满二叉树,所以F 与E有一个是根节点,一个是子节点. 而根据 左根右 的定律,E是F的根节点,
       同理在看我们的右侧树的根节点是 C ,而 C 的左边没有值,也就是说根节点 C 下面只有一个右侧树,而没有左侧树,这样就可以得出 G 是 C 的右侧树H   I 分别是G的左右树.
    

    然后就可以得出下列这个二叉图!
    在这里插入图片描述

    然后根据这个二叉图,我们就可以得出他的前序:

    前序:ABDEFCGHI
    中序: DBFEACHGI,
    后序:DFEBHIGCA.
    

      朋友们是不是很简单?我们只需要记住二叉树的前中后序变化的只是他的根节点,而他的左右节点的顺序是不变的,这样我们就可以轻松的算出二叉树的顺序了.
      如果有不对的地方,请在留言区留言,我会立马修正,如果感觉可以,请点一个赞,方便我也向大家学习.

    展开全文
  • 前序中序后序

    2017-07-25 15:57:52
    三种遍历方法 前序:先根结点后左孩子最后右孩子 中序:先左孩子后根结点最后右...后序:B F E A H G D C已知二叉树的中序前序或后续可以还原出二叉树(注:中序是必须知道的)  1. 前根序遍历:
    三种遍历方法
    前序:先根结点后左孩子最后右孩子
    中序:先左孩子后根结点最后右孩子
    后序:先左孩子后右孩子最后根结点
    
    
    
    下列二叉树的前序序列、中序序列和后序序列.

    前序:C A B E F D H G 中序:B A F E C H D G 后序:B F E A H G D C
    已知二叉树的中序加前序或后续可以还原出二叉树(:中序是必须知道的)

     

     

    1. 前根序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树。

    ABDHECFG

    2.中根序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树。

    HDBEAFCG

    3.后根序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。

    HDEBFGCA

    已知一棵二叉树的前根序序列和中根序序列,构造该二叉树的过程如下: 1. 根据前根序序列的第一个元素建立根结点; 2. 在中根序序列中找到该元素,确定根结点的左右子树的中根序序列; 3. 在前根序序列中确定左右子树的前根序序列; 4. 由左子树的前根序序列和中根序序列建立左子树; 5. 由右子树的前根序序列和中根序序列建立右子树。

    已知一棵二叉树的后根序序列和中根序序列,构造该二叉树的过程如下: 1. 根据后根序序列的最后一个元素建立根结点; 2. 在中根序序列中找到该元素,确定根结点的左右子树的中根序序列; 3. 在后根序序列中确定左右子树的后根序序列; 4. 由左子树的后根序序列和中根序序列建立左子树; 5. 由右子树的后根序序列和中根序序列建立右子树。

    展开全文
  • 二叉树前序中序后序遍历相互求法
  • 1.复习前序 中序 后序 结构: 前序:根(左子树)(右子树) 中序:(左子树)根 (右子树) 后序:(左子树)(右子树)根 2. 前序+中序->后序 由于前序的结构,第一个是根,中序中根的位置是介于左子树和右子树...

    最近开始复习数据结构,就从二叉树开始吧

    1.复习前序 中序 后序
    结构:
    前序:根(左子树)(右子树)
    中序:(左子树)根 (右子树)
    后序:(左子树)(右子树)根
    2. 前序+中序->后序
    由于前序的结构,第一个是根,中序中根的位置是介于左子树和右子树,所以我们可以通过前序获得根,通过中序将二叉树分裂,由于后序中的根在最后一个,所以我们可以通过先左后右依次将分裂到最小的树的根存储即可,所有这明显是个递归思想,看代码吧
    样例:
    前序:BAGCDZHKX
    中序:ACGDBHZKX

    #include<bits/stdc++.h>
    using namespace std;
    string qian,zhong;
    int j=0;
    char houxu[1000];
    void hou(int gen,int start,int end){
      if(start>ends)//判断退出的条件
      return;
      int i;
      i=zhong.find(qian[gen]);//在中序里找到根所在的位置
      hou(gen+1,start,i-1);
      hou(gen+1+i-start,i+1,end);
      houxu[j]=qian[gen];
      j++;
    }
    int main(){
      cout<<"请输入前序:"<<endl; 
      cin>>qian;
      cout<<"请输入中序:"<<endl;
      cin>>zhong;
      hou(0,0,qian.size()-1);//前序的第一个就是总根 由于从左开始,所以start就是0,end就是总的节点数
      for(int i=0;i<j;i++){
       cout<<houxu[i];
      }
    }

    3.中序+后序->前序
    由于后序的结构,最后一个是根,中序中根的位置是介于左子树和右子树,所以我们可以通过后序获得根,通过中序将二叉树分裂,由于前序中的根在第一个一个,所以我们可以把从左往右的每次分类的根存储即可,所有这明显是个递归思想,看代码吧(嘿嘿 我就是复制上面的,代码也差不多)
    中序:GDHBAEICF
    后序:GHDBIEFCA

    #include<bits/stdc++.h>
    using namespace std;
    string hou,zhong;
    char qian[1000]; 
    int j=0;
    void qianxu(int gen,int start,int end)
    {
     if(start>end) 
     return ;//退出条件
     int i;
     i=zhong.find(hou[gen]); 
     qian[j]=hou[gen]; 
     j++;
     qianxu(gen+i-end-1,start,i-1);
     qianxu(gen-1,i+1,end); 
    }
    int main()
    {
     cout<<"输入中序:"<<endl;
     cin>>zhong;
     cout<<"输入后序:"<<endl;
     cin>>hou;
     j=0;
     qianxu(hou.size()-1,0,zhong.size()-1);
     for(int i=0;i<j;i++){
      cout<<qian[i];
     }
    } 

    3.后序和前序没法求出中序
    以下是我在《大话数据结构》中学后自己理解:
    比如前序是ABC 后序是CBA 我们可以确定A是根节点,但无法确定其他的点的是左子树还是右子树,我们上面判断左右子树是通过中序判断的,在中序中左边的就是左子树的点,右边的就是右子树的点,但在这里无法判断。

    展开全文
  • 前序遍历图解: 前序遍历结果:ABDECF ...前序中序后序遍历代码C++版 示例二叉树 示例代码:#include<iostream> using namespace std; //使用c++模板 template <typename T> //...

    前序遍历图解

    1
    2
    3
    4
    5
    6
    7
    8

    前序遍历结果:ABDECF

    中序遍历图解:

    9
    10
    11
    12
    13
    14

    中序遍历结果:BDAC

    后序遍历图解:

    15
    16
    17
    18
    19
    20
    21

    后序遍历结果:DBCA

    前序中序后序遍历代码C++版

    • 示例二叉树
      22
    • 示例代码:
      #include<iostream>
      using namespace std;
      //使用c++模板
      template <typename T>    //类型不同时使用
      struct BNode{
      	T Data;
      	BNode<T> *lchild;
      	BNode<T> *rchild;
      	//相当于类的构造函数Data(x) <=> Data = x
      	BNode(T x):Data(x),lchild(NULL),rchild(NULL){} 
      };
      
      template <typename T>
      void PreOrderTraverse(BNode<T> *root){
      	if(root){  //如果结点不为空
      		//先打印结点值
      		cout<<root->Data;
      		//再递归左子树
      		PreOrderTraverse(root->lchild);
      		//然后递归右子树
      		PreOrderTraverse(root->rchild);
      	}
      }
      template <typename T>
      void InOrderTraverse(BNode<T> *root){
      	if(root){
      		InOrderTraverse(root->lchild);
      		cout<<root->Data;
      		InOrderTraverse(root->rchild);
      	}
      }
      template <typename T>
      void PostOrderTraverse(BNode<T> *root){
      	if(root){
      		PostOrderTraverse(root->lchild);
      		PostOrderTraverse(root->rchild);
      		cout<<root->Data;
      	}
      }
      
      void creat_BTree(){
      	//建立一颗二叉树
      	BNode<char> *node1 = new BNode<char>('-');
      	BNode<char> *node2 = new BNode<char>('+');
      	BNode<char> *node3 = new BNode<char>('/');
      	BNode<char> *node4 = new BNode<char>('a');
      	BNode<char> *node5 = new BNode<char>('*');
      	BNode<char> *node6 = new BNode<char>('e');
      	BNode<char> *node7 = new BNode<char>('f');
      	BNode<char> *node8 = new BNode<char>('b');
      	BNode<char> *node9 = new BNode<char>('-');
      	BNode<char> *node10 = new BNode<char>('c');
      	BNode<char> *node11 = new BNode<char>('d');
      	node1->lchild = node2;
      	node1->rchild = node3;
      	node2->lchild = node4;
      	node2->rchild = node5;
      	node3->lchild = node6;
      	node3->rchild = node7;
      	node5->lchild = node8;
      	node5->rchild = node9;
      	node9->lchild = node10;
      	node9->rchild = node11;
      
      	cout<<"前序遍历:";
      	PreOrderTraverse(node1);
      	cout<<"\n中序遍历:";
      	InOrderTraverse(node1);
      	cout<<"\n后序遍历:";
      	PostOrderTraverse(node1);
      }
      
      int main(){
      	creat_BTree();
      	return 0;
      }
      
      
      Output:
      前序遍历:-+a*b-cd/ef
      中序遍历:a+b*c-d-e/f
      后序遍历:abcd-*+ef/-
      
    有任何问题可以留言小g
    展开全文
  • 数据结构:二叉树遍历,前序中序后序 题型: 知前序中序,得后序 知后序中序,得前序 (注:仅知前序后序,无法确定中序,因为不知道左右子树。) 特征: 前序,根左右 中序,左根右 后序,左右根 关键思路: 关键是...
  • 排序二叉树前序中序后序遍历,需要自己创建二叉树
  • 一、什么是前序中序后序遍历: 如图: 前序遍历:根-》左》右         ABDCEF 中序遍历 左-》根-》右         DBAECF 后序遍历 左-》右-》...
  • 用C语言实现数据结构中二叉树的前序中序后序遍历 int main()//主函数部分 { BiTree T=NULL; int Layer=0; int LayerT=0; printf("请输入二叉树:\n"); CreatBiTree(&T);printf("你输入的二叉树为:(竖型树状...
  • 二叉排序树的建立 前序 中序 后序 遍历 主要根据文档《大话数据结构》 题目描述 输入一系列整数,建立二叉排序数,并进行前序中序后序遍历。 输入描述: 输入第一行包括一个整数n(1<=n<=100)。 ...
  • 前序中序后序实现二叉树遍历(迭代、非递归) 二叉树先序、中序、后序遍历超级简单的实现(Java) 前序遍历迭代 public void preOrder(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>();...
  • 二叉树 ---- 前序 中序 后序 知二求一 先说一下什么是二叉树的前中后序; 根:根节点 左代表遍历左子树 右代表遍历右子树 前序:根—左---右 中序:左—根---右 后序:左—右---根 如图求前序: //叶子结点简单的说就是...
  • 二叉树前序中序后序排序 前序:根-左-右 中序:左-根-右 后序:左-右-根 二叉树遍历代码 #先构造树,然后再进行前序中序后序遍历 #class是一个类,一个类里面包含很多个属性 class Tree: def __init__(self, data):...
  • C++用类实现二叉树的创建,前序中序后序遍历(附完整代码)前序、中序、后序遍历直接上代码 前序、中序、后序遍历 二叉树的遍历分为前序遍历,中序遍历和后序遍历三种遍历方法。前序遍历的顺序为“根左右”,中序...
  • 【数据结构与算法】二叉树前序 中序 后序遍历间关系
  • 二叉树前序中序后序遍历的递归遍历非常简单,这里就写一下非递归的方法。 核心思路是把每一个结点看成父节点,叶子结点是左右孩子是null的父结点。 前序遍历 思路: 使用一个栈来存储结点,以便回到之前的父结点...
  •  现在记录已知二叉树的前序中序后序遍历的两个,求另外一个。一般,这两个中一定有中序遍历。  1、已知前序和中序,求后序遍历: 前序:ABDECFG 中序:DBEAFCG 思路简单:前序的第一个节点就是根节点,  中序...
  • 在前一篇文章对二叉树进行的部分介绍:数据结构—— 树(二叉树)详解 在后面当中简介了一下遍历方法,随后对遍历方法实现: ...最后就是对前序中序后序的方法实现。 class Node { private int no; p
  • LeetCode中N叉树的前序中序后序递归和非递归写法 相关题: 589. N叉树的前序遍历 429. N叉树的层序遍历 N叉树的后序遍历 589. N叉树的前序遍历 给定一个 N 叉树,返回其节点值的前序遍历。 递归写法 /* // ...
  • 马上网易游戏笔试,为了不重蹈覆辙,最近复习了下二叉树 前序 中序 后序遍历的递归,非递归的Python实现方法。在这里做个记录 代码 class Node(object): def __init__(self, val, left=None, right=None): ...
  • 3.什么是前序中序后序 前序 中左右 中序 左中右 后序 左右中 他们之间的区别就是中间节点的位置 4. 如何创建一个二叉树 package com.qin.tree; public class BinaryTree { public static void main(String[] ...
  • 我们实习的任务 做出来分享一下!!!二叉树 C++实现 建树 前序 中序 后序 层序
  • 建立一棵二叉树,并对其进行遍历(先序、中序后序),打印输出遍历结果。 [基本要求] 从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),并采用递归算法对其进行遍历(先序、中序、...
  • 二叉树——前序中序后序1. 概述2. 根据前序中序重建二叉树3. 代码实现 1. 概述 前序:根节点 > 左节点 > 右节点 中序:左节点 > 根节点 > 右节点 后序:左节点 > 右节点 > 根节点 2. 根据...
  • 2.对二叉树进行前序中序后序遍历 输入 扩展的前序序列.在一棵树处理结束后,根据响应判断是否处理下一棵树 输出 前序中序后序 样例输入 ab##c## Y abc#### N 样例输出 abc bac bca abc cba cba #include<...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,950
精华内容 18,380
关键字:

前序中序后序