精华内容
参与话题
问答
  • 前序遍历

    2019-11-01 13:57:44
    2.1、前序遍历   首先访问根节点,然后遍历左子树,最后遍历右子树。 2.2、训练 589. N叉树的前序遍历

    2.1、前序遍历

      首先访问根节点,然后遍历左子树,最后遍历右子树。

    2.2、训练

    144. 二叉树的前序遍历
    589. N叉树的前序遍历
    572. 另一个树的子树

    展开全文
  • 0. 写在最前面 希望大家收藏: ...  复习到二叉树,看到网上诸多博客文章各种绕,记得头晕。个人觉得数学、算法这些东西都是可以更直观简洁地表示,然后被记住的,并不需要靠死记硬背。 本文的程序基本来源于《大话...

    0. 写在最前面

    希望大家收藏:

    本文持续更新地址:https://haoqchen.site/2018/05/23/go-through-binary-tree/

        复习到二叉树,看到网上诸多博客文章各种绕,记得头晕。个人觉得数学、算法这些东西都是可以更直观简洁地表示,然后被记住的,并不需要靠死记硬背。

    本文的程序基本来源于《大话数据结构》,个人感觉是一本非常好的书,推荐去看。

    1. 为什么叫前序、后序、中序?

        一棵二叉树由根结点、左子树和右子树三部分组成,若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树的遍历方式有 6 种:DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式:

    DLR--前序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 )

    LDR--中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面)

    LRD--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)

    需要注意几点:

    1. 根是相对的,对于整棵树而言只有一个根,但对于每棵子树而言,又有自己的根。比如对于下面三个图,对于整棵树而言,A是根,A分别在最前面、中间、后面被遍历到。而对于D,它是G和H的根,对于D、G、H这棵小树而言,顺序分别是DGH、GDH、GHD;对于C,它是E和F的根,三种排序的顺序分别为: CEF、ECF、EFC。是不是根上面的DLR、LDR、LRD一模一样呢~~
    2. 整棵树的起点,就如上面所说的,从A开始,前序遍历的话,一棵树的根永远在左子树前面,左子树又永远在右子树前面,你就找他的起点好了。
    3. 二叉树结点的先根序列、中根序列和后根序列中,所有叶子结点的先后顺序一样
    4. 建议看看文末第3个参考有趣详细的推导

                      前序遍历(DLR)                                 中序遍历(LDR)                             后序遍历(LRD)

     

    2. 算法上的前中后序实现

    除了下面的递归实现,还有一种使用栈的非递归实现。因为递归实现比较简单,且容易关联到前中后,所以

    typedef struct TreeNode
    {
        int data;
        TreeNode * left;
        TreeNode * right;
        TreeNode * parent;
    }TreeNode;
     
    void pre_order(TreeNode * Node)//前序遍历递归算法
    {
        if(Node == NULL)
            return;
        printf("%d ", Node->data);//显示节点数据,可以更改为其他操作。在前面
        pre_order(Node->left);
        pre_order(Node->right);
    }
    void middle_order(TreeNode *Node)//中序遍历递归算法
    {
        if(Node == NULL)
            return;
        middle_order(Node->left);
        printf("%d ", Node->data);//在中间
        middle_order(Node->right);
    }
    void post_order(TreeNode *Node)//后序遍历递归算法
    {
        if(Node == NULL)
            return; 
        post_order(Node->left);
        post_order(Node->right);
        printf("%d ", Node->data);//在最后
    }

    3. 层序遍历

      层序遍历嘛,就是按层,从上到下,从左到右遍历,这个没啥好说的。

    参考

    1.《大话数据结构》

    2.https://cnbin.github.io/blog/2016/01/05/er-cha-shu-de-bian-li/

    3.https://blog.csdn.net/soundwave_/article/details/53120766

     

     

     

    展开全文
  • /*函数preorder1()的功能是非递归前序遍历二叉树t*/ void preorder1(bintree t) { seqstack *s; init(s); bintree p=t; while(!empty(s)||p) { if(p) { cout<<p->data; push(s,p); p=...
  • 已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
  • 1.前序遍历 前序遍历(DLR,lchild,data,rchild),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。前序遍历首先访问根结点然后...

    1.前序遍历

        前序遍历(DLR,lchild,data,rchild),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。
    二叉树为空则结束返回,否则:
    (1)访问根结点。
    (2)前序遍历左子树
    (3)前序遍历右子树 。
    前序遍历前序遍历
    需要注意的是:遍历左右子树时仍然采用前序遍历方法。
    如右图所示二叉树
    前序遍历结果:ABDECF
    已知后序遍历和中序遍历,就能确定前序遍历。

        其实在遍历二叉树的时候有三次遍历, 比如前序遍历:A->B->D->D(D左子节点并返回到D)->D(D右子节点并返回到D)->B->E->E(左)->E(右)->->B->A->C->F->F(左)->F(右)->C->C(右),所以可以用栈结构,把遍历到的节点压进栈,没子节点时再出栈。也可以用递归的方式,递归的输出当前节点,然后递归的输出左子节点,最后递归的输出右子节点。直接看代码更能理解:

    package test;
    //前序遍历的递归实现与非递归实现
    import java.util.Stack;
    public class Test 
    {
    	public static void main(String[] args)
    	{
    		TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
    		for(int i = 0; i < 10; i++)
    		{
    			node[i] = new TreeNode(i);
    		}
    		for(int i = 0; i < 10; i++)
    		{
    			if(i*2+1 < 10)
    				node[i].left = node[i*2+1];
    			if(i*2+2 < 10)
    				node[i].right = node[i*2+2];
    		}
    		
    		preOrderRe(node[0]);
    	}
    	
    	public static void preOrderRe(TreeNode biTree)
    	{//递归实现
    		System.out.println(biTree.value);
    		TreeNode leftTree = biTree.left;
    		if(leftTree != null)
    		{
    			preOrderRe(leftTree);
    		}
    		TreeNode rightTree = biTree.right;
    		if(rightTree != null)
    		{
    			preOrderRe(rightTree);
    		}
    	}
    	
    	public static void preOrder(TreeNode biTree)
    	{//非递归实现
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		while(biTree != null || !stack.isEmpty())
    		{
    			while(biTree != null)
    			{
    				System.out.println(biTree.value);
    				stack.push(biTree);
    				biTree = biTree.left;
    			}
    			if(!stack.isEmpty())
    			{
    				biTree = stack.pop();
    				biTree = biTree.right;
    			}
    		}
    	}
    }
    
    class TreeNode//节点结构
    {
    	int value;
    	TreeNode left;
    	TreeNode right;
    	
    	TreeNode(int value)
    	{
    		this.value = value;
    	}
    }
    
    
    
    


    2.中序遍历

    中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,先左后根再右。巧记:左根右。
    中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树
    二叉树为空则结束返回,
    否则:

      
    (1)中序遍历左子树
    (2)访问根结点
    (3)中序遍历右子树
    如右图所示二叉树
    中序遍历结果:DBEAFC

    import java.util.Stack;
    public class Test 
    {
    	public static void main(String[] args)
    	{
    		TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
    		for(int i = 0; i < 10; i++)
    		{
    			node[i] = new TreeNode(i);
    		}
    		for(int i = 0; i < 10; i++)
    		{
    			if(i*2+1 < 10)
    				node[i].left = node[i*2+1];
    			if(i*2+2 < 10)
    				node[i].right = node[i*2+2];
    		}
    		
    		midOrderRe(node[0]);
    		System.out.println();
    		midOrder(node[0]);
    	}
    	
    	public static void midOrderRe(TreeNode biTree)
    	{//中序遍历递归实现
    		if(biTree == null)
    			return;
    		else
    		{
    			midOrderRe(biTree.left);
    			System.out.println(biTree.value);
    			midOrderRe(biTree.right);
    		}
    	}
    	
    	
    	public static void midOrder(TreeNode biTree)
    	{//中序遍历费递归实现
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		while(biTree != null || !stack.isEmpty())
    		{
    			while(biTree != null)
    			{
    				stack.push(biTree);
    				biTree = biTree.left;
    			}
    			if(!stack.isEmpty())
    			{
    				biTree = stack.pop();
    				System.out.println(biTree.value);
    				biTree = biTree.right;
    			}
    		}
    	}
    }
    
    class TreeNode//节点结构
    {
    	int value;
    	TreeNode left;
    	TreeNode right;
    	
    	TreeNode(int value)
    	{
    		this.value = value;
    	}
    }
    
    
    
    

    3.后序遍历(难点)

    后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根。巧记:左右根。
    后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。即:
    二叉树为空则结束返回,
    否则:
    (1)后序遍历左子树
    (2)后序遍历右子树
    (3)访问根结点
    如右图所示二叉树
    后序遍历结果:DEBFCA
    已知前序遍历和中序遍历,就能确定后序遍历。
    算法核心思想:
        首先要搞清楚先序、中序、后序的非递归算法共同之处:用栈来保存先前走过的路径,以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
        后序遍历的非递归算法是三种顺序中最复杂的,原因在于,后序遍历是先访问左、右子树,再访问根节点,而在非递归算法中,利用栈回退到时,并不知道是从左子树回退到根节点,还是从右子树回退到根节点,如果从左子树回退到根节点,此时就应该去访问右子树,而如果从右子树回退到根节点,此时就应该访问根节点。所以相比前序和后序,必须得在压栈时添加信息,以便在退栈时可以知道是从左子树返回,还是从右子树返回进而决定下一步的操作。

    import java.util.Stack;
    public class Test 
    {
    	public static void main(String[] args)
    	{
    		TreeNode[] node = new TreeNode[10];//以数组形式生成一棵完全二叉树
    		for(int i = 0; i < 10; i++)
    		{
    			node[i] = new TreeNode(i);
    		}
    		for(int i = 0; i < 10; i++)
    		{
    			if(i*2+1 < 10)
    				node[i].left = node[i*2+1];
    			if(i*2+2 < 10)
    				node[i].right = node[i*2+2];
    		}
    		
    		postOrderRe(node[0]);
    		System.out.println("***");
    		postOrder(node[0]);
    	}
    	
    	
    	
    	public static void postOrderRe(TreeNode biTree)
    	{//后序遍历递归实现
    		if(biTree == null)
    			return;
    		else
    		{
    			postOrderRe(biTree.left);
    			postOrderRe(biTree.right);
    			System.out.println(biTree.value);
    		}
    	}
    	
    	public static void postOrder(TreeNode biTree)
    	{//后序遍历非递归实现
    		int left = 1;//在辅助栈里表示左节点
    		int right = 2;//在辅助栈里表示右节点
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		Stack<Integer> stack2 = new Stack<Integer>();//辅助栈,用来判断子节点返回父节点时处于左节点还是右节点。
    		
    		while(biTree != null || !stack.empty())
    		{
    			while(biTree != null)
    			{//将节点压入栈1,并在栈2将节点标记为左节点
    				stack.push(biTree);
    				stack2.push(left);
    				biTree = biTree.left;
    			}
    			
    			while(!stack.empty() && stack2.peek() == right)
    			{//如果是从右子节点返回父节点,则任务完成,将两个栈的栈顶弹出
    				stack2.pop();
    				System.out.println(stack.pop().value);
    			}
    			
    			if(!stack.empty() && stack2.peek() == left)
    			{//如果是从左子节点返回父节点,则将标记改为右子节点
    				stack2.pop();
    				stack2.push(right);
    				biTree = stack.peek().right;
    			}
    				
    		}
    	}
    }
    
    class TreeNode//节点结构
    {
    	int value;
    	TreeNode left;
    	TreeNode right;
    	
    	TreeNode(int value)
    	{
    		this.value = value;
    	}
    }
    
    
    

    4.层次遍历

        与树的前中后序遍历的DFS思想不同,层次遍历用到的是BFS思想。一般DFS用递归去实现(也可以用栈实现),BFS需要用队列去实现。
    层次遍历的步骤是:
        1.对于不为空的结点,先把该结点加入到队列中
        2.从队中拿出结点,如果该结点的左右结点不为空,就分别把左右结点加入到队列中

        3.重复以上操作直到队列为空

    	public static void levelOrder(TreeNode biTree)
    	{//层次遍历
    		if(biTree == null)
    			return;
    		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
    		list.add(biTree);
    		TreeNode currentNode;
    		while(!list.isEmpty())
    		{
    			currentNode = list.poll();
    			System.out.println(currentNode.value);
    			if(currentNode.left != null)
    				list.add(currentNode.left);
    			if(currentNode.right != null)
    				list.add(currentNode.right);
    		}
    	}
    先序遍历特点:第一个值是根节点
    中序遍历特点:根节点左边都是左子树,右边都是右子树
    展开全文
  • 二叉树的前序遍历、中序遍历和后序遍历之间还原二叉树1、概念(1)前序遍历 a、访问根节点;b、前序遍历左子树;c、前序遍历右子树。(2)中序遍历 a、中序遍历左子树;b、访问根节点;c、中序遍历右子树。(3)...

    二叉树的前序遍历、中序遍历和后序遍历之间还原二叉树

    1、概念

    (1)前序遍历

          a、访问根节点;b、前序遍历左子树;c、前序遍历右子树。

    (2)中序遍历

          a、中序遍历左子树;b、访问根节点;c、中序遍历右子树。

    (3)后序遍历

          a、后序遍历左子树;b、后续遍历右子树;c、访问根节点。

    2、前序遍历和中序遍历还原二叉树

    思想如下:

        a、根据前序遍历结果,第一个元素为二叉树的根结点;

        b、观察中序遍历结果,根结点左侧的为左子树,若左子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;根结点右侧的为右子树,若右子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;

        c、上面的过程是递归的。先找到当前树的根结点,然后划分为左右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。

    例:

        已知前序遍历:ABDHIEJKCFLMGNO

               中序遍历:HDIBJEKALFMCNGO


    按照上述步骤先画出二叉树,然后在进行求解后序遍历结果。结果为:HIDJKEBLMFNOGCA

    练习:

    1、前序遍历:GDAFEMHZ

          中序遍历:ADEFGHMZ

        求得后序遍历结果为:AEFDHZMG

    2序遍历:ADCEFGHB

          中序遍历:CDFEGHAB

        求得后序遍历结果为:CFHGEDBA

    3、中序遍历和后序遍历还原二叉树

    思想如下:

        a、根据后序遍历结果,最后一个元素为二叉树的根结点;

        b、观察中序遍历结果,其中根结点左侧为左子树,若左子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;其中根结点右侧为右子树,若右子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;

        c、上面的过程是递归的。先根据后序遍历结果找根结点,根结点左侧为左子树,右侧为右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。

    例:

        已知

    中序遍历:HDIBJEKALFMCNGO

    后序遍历:

    HIDJKEBLMFNOGCA

             

    按照上述步骤先画出二叉树,然后在进行求解前序遍历结果。结果为:

    ABDHIEJKCFLMGNO

    练习:可参考前序遍历和中序遍历的练习

    4、前序遍历和后序遍历还原二叉树

    已知前序和中序,后序和中序遍历序列之后,可以唯一确定一棵二叉树。但是,只知道前序和后序遍历序列,是无法知道哪个结点是左子树还算右子树。



    展开全文
  • 一、前序遍历 根节点-&gt;左子树-&gt;右子树 二、中序遍历 左子树-&gt;根节点-&gt;右子树 三、后序遍历 左子树-&gt;右子树-&gt;根节点 四、层次遍历 按照深度,以从上到下、从左到右的顺序...
  • 主要介绍了C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法,涉及C#遍历二叉树的相关技巧,需要的朋友可以参考下
  • 主要介绍了Python二叉树的遍历操作,结合实例形式分析了Python针对二叉树的前序遍历,中序遍历,后序遍历,层序遍历等相关操作实现技巧,需要的朋友可以参考下
  • 《剑指offer》面试题24的相关题目。输入一个整数数组,判断该数组是不是某二叉搜索树的前序遍历。假设输入的数组的任意两个数字互不相同。
  • 作业题目是改写二叉树前序遍历算法 void PreOrder( BinTNode *T ) { if( T != NULL ) { cout<<T->data; PreOrder( T->left_child ); PreOrder( T->right_child ); } }; 要求消除第二个递归调用,怎么做??_
  • 二叉树遍历前序遍历

    2017-07-25 18:22:08
    public void preOrderTraverse(TreeNode node){ Statck nodes=new Statck nodes.push(node); while(!nodes.isEmpty()) { TreeNode current=nodes.pop(); if(current.right!=null) ndoes.push
  • 主要介绍了PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法,涉及php数据结构与算法中关于数的遍历相关操作技巧,需要的朋友可以参考下
  • 如题,二叉树遍历中,前序遍历的最后是否一定是叶节点,急求,忘请各位前辈不吝赐教![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/9.gif)![图片说明]...
  • 数据结构算法及应用 上机作业 谦虚中序遍历顺序&中序后续遍历顺序,还原二叉树并输出
  • 前言 java关于ACM的代码真的好少,想参考如何用java实现...根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序、中序、后序进行遍历 代码 import java.util.Scanner; public
  • 二叉树已知后序和中序遍历求前序遍历,C++编写已通过编译
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 树的遍历顺序大体分为三种:前序遍历(先根遍历、先序遍历),中序遍历(中根遍历),后序遍历(后根遍历)。 如图所示二叉树: 前序遍历前序遍历可以记为根左右,若二叉树为空,则结束返回。 前序遍历的规则: ...
  • 第一行为二叉树的前序遍历结果 第二行为二叉树的中序遍历结果 输出格式: 二叉树后序遍历结果 Example: Inputs: 426315 623415 Outputs: 632514 分析: 前序遍历顺序为根左右。中序遍历结果为左根右。前序遍历结果...
  • 前序遍历、中序遍历和后续遍历

    万次阅读 2019-01-16 09:41:11
    树的遍历顺序大体分为三种:前序遍历(先根遍历、先序遍历),中序遍历(中根遍历),后序遍历(后根遍历)。   如图所示二叉树:   前序遍历前序遍历可以记为根左右,若二叉树为空,则结束返回。 前序...
  • 前序遍历中序遍历后序遍历

    千次阅读 2019-07-02 22:32:33
  • 二叉树的前序遍历

    千次阅读 2016-04-14 20:17:11
    题目描述:给出一棵二叉树,返回其节点值的前序遍历。要求不能用递归。 什么是前序遍历应该已经很清楚了,样例我就省略了。 关于二叉树的前序遍历,我之前已经详细讲过,当时是用的最简单的递归解决这个问题的,...
  • 前序遍历+中序遍历=后序遍历 中序遍历+后序遍历=前序遍历
  • 前序遍历层次遍历

    2017-06-24 21:33:56
    已知前序遍历的序号求层次遍历的序号,反之亦然。 #include #include #include #include #include #include #include using namespace std; int n,q,k; int childnum(int r) { int x=r; while(x*2)x*=2; int...
  • 前序遍历遍历二叉树

    2017-02-14 17:17:23
    前序遍历遍历二叉树
  • 前序遍历:根左右; 中序遍历:左根右; 后续遍历:左右根。 转载于:https://www.cnblogs.com/wumh7/p/9602910.html
  • 前序遍历(DLR) 前序遍历也叫做先根遍历、先序遍历,可记做根左右。 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。 若二叉树为...

空空如也

1 2 3 4 5 ... 20
收藏数 22,686
精华内容 9,074
关键字:

前序遍历