精华内容
下载资源
问答
  • 数据结构——二叉树先序中序后序三种遍历二叉树先序中序后序三种遍历三、代码展示: 二叉树先序中序后序三种遍历 先序遍历:3 2 2 3 8 6 5 4 中序遍历:2 2 3 3 4 5 6 8 后序遍历: 2 3 2 4 5 6 8 3 ...

    一、图示展示:

    (1)先序遍历

    先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果

    先序遍历结果为:A B D H I E J C F K G

    在这里插入图片描述
    动画演示:

    记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解

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

    (2)中序遍历

    中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最左边开始垂直掉到地上),然后从左往右数,得出的结果便是中序遍历的结果

    中遍历结果为:H D I B E J A F K C G
    在这里插入图片描述

    动画展示:

    记住,中序遍历就是从最左边开始,把每个节点垂直投影到同一直线上,然后从左往右读值就可以了,多看几遍动图就理解了

    在这里插入图片描述

    (3)后序遍历

    后序遍历就像是剪葡萄,我们要把一串葡萄剪成一颗一颗的

    还记得我上面提到先序遍历绕圈的路线么?(不记得翻上面理解)

    就是围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄)(也就是葡萄要一个一个掉下来,不能一口气掉超过1个这样),就把它剪下来,组成的就是后序遍历了。

    后序遍历中,根节点默认最后面

    后序遍历结果:H I D J E B K F G C A
    在这里插入图片描述
    动画展示:
    在这里插入图片描述

    (4)层次遍历

    层次遍历很好理解,就是从根节点开始,一层一层,从上到下,每层从左到右,依次写值就可以了

    层次遍历结果:A B C D E F G H I J K

    在这里插入图片描述

    解释外圈跑的意思:

    绕着外围跑一整圈的真正含义是:遍历所有结点时,都先往左孩子走,再往右孩子走。

    (5)口诀

    先序遍历: 先根 再左 再右

    中序遍历: 先左 再根 再右

    后序遍历: 先左 再右 再根

    这里的根,指的是每个分叉子树(左右子树的根节点)根节点,并不只是最开始头顶的根节点,需要灵活思考理解,建议画图理解!!

    二、代码展示:

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Tree{
     
     int data;					//	存放数据域
     struct Tree *lchild;			//	遍历左子树指针
     struct Tree *rchild;			//	遍历右子树指针
     
    }Tree,*BitTree;
    
    BitTree CreateLink()
    {
    	int data;
    	int temp;
    	BitTree T;
    	
    	scanf("%d",&data);		//	输入数据
    	temp=getchar();			//	吸收空格
    	
    	if(data == -1){			//	输入-1 代表此节点下子树不存数据,也就是不继续递归创建
    		
    		return NULL;
    
    	}else{
    		T = (BitTree)malloc(sizeof(Tree));			//		分配内存空间
    		T->data = data;								//		把当前输入的数据存入当前节点指针的数据域中
    		
    		printf("请输入%d的左子树: ",data);		
    		T->lchild = CreateLink();					//		开始递归创建左子树
    		printf("请输入%d的右子树: ",data);			
    		T->rchild = CreateLink();					//		开始到上一级节点的右边递归创建左右子树
    		return T;							//		返回根节点
    	}	
    	
    }
    //	先序遍历
    void ShowXianXu(BitTree T)			//		先序遍历二叉树
    {
    	if(T==NULL)						//	递归中遇到NULL,返回上一层节点
    	{
    		return;
    	}
    	printf("%d ",T->data);
    	ShowXianXu(T->lchild);			//	递归遍历左子树
    	ShowXianXu(T->rchild);			//	递归遍历右子树
    }
    //	中序遍历
    void ShowZhongXu(BitTree T)			//		先序遍历二叉树
    {
    	if(T==NULL)						//	递归中遇到NULL,返回上一层节点
    	{
    		return;
    	}
    	
    	ShowZhongXu(T->lchild);			//	递归遍历左子树
    	printf("%d ",T->data);
    	ShowZhongXu(T->rchild);			//	递归遍历右子树
    	
    }
    //	后序遍历
    void ShowHouXu(BitTree T)			//		后序遍历二叉树
    {
    	if(T==NULL)						//	递归中遇到NULL,返回上一层节点
    	{
    		return;
    	}
    	
    	ShowHouXu(T->lchild);			//	递归遍历左子树
    	ShowHouXu(T->rchild);			//	递归遍历右子树
    	printf("%d ",T->data);
    }
    
    
    int main()
    {
    	BitTree S;
    	printf("请输入第一个节点的数据:\n");
    	S = CreateLink();			//		接受创建二叉树完成的根节点
    	printf("先序遍历结果: \n");
    	ShowXianXu(S);				//		先序遍历二叉树
    
    	printf("\n中序遍历结果: \n");
    	ShowZhongXu(S);				//		中序遍历二叉树
    	
    	printf("\n后序遍历结果: \n");
    	ShowHouXu(S);				//		后序遍历二叉树
    	
    	return 0;	
    } 	
    
    
    展开全文
  • 1.题目:牛客网 NC45 (实现二叉树先序中序和后序遍历) 描述 分别按照二叉树先序中序和后序打印所有的节点。 示例1 输入: {1,2,3} 返回值: [[1,2,3],[2,1,3],[2,3,1]] 2.二叉树的遍历 a.先序遍历: 如果...

    1.题目:牛客网 NC45 (实现二叉树先序,中序和后序遍历)

    描述
    分别按照二叉树先序,中序和后序打印所有的节点。
    示例1
    输入:
    {1,2,3}
    返回值:
    [[1,2,3],[2,1,3],[2,3,1]]
    

    2.二叉树的遍历

    a.先序遍历:
    如果二叉树为空,什么也不做。否则:
    1)访问根节点
    2)先序遍历左子树
    3)先序遍历右子树

    b.中序遍历:
    如果二叉树为空,什么也不做。否则:
    1)中序遍历左子树
    2)访问根节点
    3)中序遍历右子树

    c.后序遍历:
    如果二叉树为空,什么也不做。否则:
    1)后序遍历左子树
    2)后序遍历右子树
    3)访问根节点

    很明显,先中后序遍历都可以很方便地用递归实现。

    3.代码实现

    /**
     * struct TreeNode {
     *	int val;
     *	struct TreeNode *left;
     *	struct TreeNode *right;
     * };
     */
    
    class Solution {
    public:
        /**
         * 
         * @param root TreeNode类 the root of binary tree
         * @return int整型vector<vector<>>
         */
        vector<vector<int> > threeOrders(TreeNode* root) {
            // write code here
            vector<int> xianxu;
            vector<int> zhongxu;
            vector<int> houxu;
            //二叉树先序遍历
            vector<vector<int> > res;
            res.push_back(PreOrder(root,xianxu));
            res.push_back(InOrder(root,zhongxu));
            res.push_back(PostOrder(root,houxu));
            return res;
            
        }
        vector<int> PreOrder(TreeNode* root,vector<int> &xianxu)
        {
            //vector<int> xianxu;
            if(root!=NULL)
            {
                xianxu.push_back(root->val);
                PreOrder(root->left,xianxu);
                PreOrder(root->right,xianxu);
            }
            return xianxu;
        }
        vector<int> InOrder(TreeNode* root,vector<int> &zhongxu)
        {
            //vector<int> zhongxu;
            if(root!=NULL)
            {
                InOrder(root->left,zhongxu);
                zhongxu.push_back(root->val);
                InOrder(root->right,zhongxu);
            }
            return zhongxu;
        }
        vector<int> PostOrder(TreeNode* root,vector<int> &houxu)
        {
            //vector<int> houxu;
            if(root!=NULL)
            {
                PostOrder(root->left,houxu);
                PostOrder(root->right,houxu);
                houxu.push_back(root->val);
            }
            return houxu;
        }
    };
    
    展开全文
  • 二叉树已知先序中序求后序、已知中序后序求先序

    千次阅读 多人点赞 2016-07-30 23:18:22
    需要注意的是(我们只能够通过已知先序中序求后序或已知中序后序求先序,而不能够已知先序后序求中序) 下面总结一下两种题的做法首先回顾知识点 二叉树先序遍历 根结点—->左子树—->右子树 二叉树中序遍历 左...

    在做数据结构面试题的时候我们会经常发现有关二叉树的题目总是这样的
    栗子:
    已知某二叉树先序为……中序为……求后序
    已知某二叉树中序为……后序为……求先序
    需要注意的是(我们只能够通过已知先序中序求后序或已知中序后序求先序,而不能够已知先序和后序求中序
    下面总结一下两种题的做法


    首先回顾知识点

    • 二叉树先序遍历 根结点—->左子树—->右子树
    • 二叉树中序遍历 左子树—->根结点—->右子树
    • 二叉树后序遍历 左子树—->右子树—->根结点
      这个非常好记忆,就是看根结点的位置就可以了

    第一种
    已知一个二叉树的先序遍历结果为:ABCDEFGH,中序遍历结果为BDCEAFHG,求该二叉树的后序遍历。

    思路:拿到这样的题,我们要先根据两种遍历顺序把原始二叉树画出来,然后再根据后序遍历的规则解出后序遍历。

    解析:首先看先序遍历的第一个结点为A,那么根据先序遍历规则先访问根结点,那么A肯定是根结点了。然后根据中序遍历规则先访问左子树中间访问根结点。那么我们可以得出BCDE是根结点A的左子树FHG是根结点A的右子树。那么左子树BCDE当中又怎么排序呢?这个时候我们再来看先序遍历,A结点之后先序先遍历B,说明B一定是根结点A左子树的根结点。如下图
    这里写图片描述
    然后我们再看中序遍历,B是第一个,说明B结点没有左子树,CDE是B的右子树,然后我们想知道CDE如何排序,再次看先序遍历,这个时候先序遍历AB已经排出来。过来是C,说明C是B结点右子树的根结点。可以画出下图
    这里写图片描述
    接下来我们再次看中序遍历,中序遍历B接下来是D,而且我们已经知道C是B右字数的根结点,那么我们根据中序先访问左子树然后访问根结点,就知道D是C结点的左子树。那么E理所当然应该是C结点的右子树。可以画出如下图
    这里写图片描述
    这样我们的左子树就画好了,接下来处理FGH。我们看到F在先序和中序中都先出现,我们就可以确定F是右子树的根结点,并且F没有左子树。接下来先序出现的是G,而中序中G是最后出现的。所以G是F右子树的根结点而H是G的左子树。这样我们就确定了原始树的样子如下图
    这里写图片描述

    最后一步:
    得知原始树
    我们按照后序遍历的规则,先访问左子树再访问右子树最后访问根结点
    可以得到后续遍历的顺序为DECBHGFA


    哈哈,学会了先序中序求后序,我们再看第二种,已知中序后序求先序

    直接上题目
    第二种
    已知一个二叉树的中序遍历结果为: BDACE,后序遍历结果为 DBECA,求该二叉树的先序遍历。

    按照第一题的做法,首先我们知道后序遍历最后遍历根结点,所以A结点一定是这棵树的根结点,然后我们再开中序遍历的结果,A结点是根结点,所以BD是A结点的左子树,CE是根结点的右子树。先看BD。根据中序先遍历左子树然后遍历根结点最后遍历右子树顺序为BD,而后序先遍历左子树再遍历右子树最后遍历根结点顺序为DB。所以可以推出B是A的左子树的根结点,且B没有左子树,B的右子树是D。可画出下图
    这里写图片描述

    接下来我们来看A的右子树。剩下EC两个结点,我们再次看中序与后序遍历的结果。根据中序先遍历左子树然后遍历根结点最后遍历右子树顺序为CE,而后序先遍历左子树再遍历右子树最后遍历根结点顺序为EC。则我们可以推出C应该是A结点右子树的根结点,而E应该是C结点的右子树。这样我们就可以画出原始树如下图
    这里写图片描述

    根据原始树,我们可以按照先序遍历的顺序得到先序遍历结果:ABDCE

    总结:掌握先中后遍历的规则,然后结合先中或者中后以及遍历规则画出原始树,然后根据原始树求出先序或者后序!!

    展开全文
  • 二叉树先序和中序后序的代码。已知道先序是中序如何找后序的方法。
  • 实现二叉树先序中序和后序遍历 题目描述 分别按照二叉树先序中序和后序打印所有的节点。 输入描述: 第行输入两个整数 n root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。 以下 n 行每行三个...
    实现二叉树先序,中序和后序遍历

    题目描述

    分别按照二叉树先序,中序和后序打印所有的节点。

    输入描述:

    第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。

    以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)

    输出描述:

    输出三行,分别表示二叉树的先序,中序和后序。

    示例1
    输入
    3 1
    1 2 3
    2 0 0
    3 0 0
    
    输出
    1 2 3
    2 1 3
    2 3 1
    
    备注:

    1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1n106

    1 ≤ r o o t , f a , l c h , r c h ≤ n 1 \leq root,fa,lch,rch \leq n 1root,fa,lch,rchn


    题解:

    先序遍历:根 左 右

    中序遍历:左 根 右

    后序遍历:左 右 根

    先、中、后序遍历按照上面的顺序进行即可。此题如果使用递归,那就非常简单了。鉴于自己对递归转非递归一直未能掌握,此处使用非递归版本代码。稍微麻烦点的是中序遍历,但后续遍历非常麻烦。。。

    #include <cstdio>
    #include <stack>
    
    using namespace std;
    
    struct BST{
        int val;
        struct BST * lch, * rch;
        BST() {}
        BST(int v) : val(v), lch(NULL), rch(NULL) {}
    };
    
    void createTree(BST* root) {
        int fa, lch, rch;
        scanf("%d %d %d", &fa, &lch, &rch);
        if (lch) {
            root->lch = new BST(lch);
            createTree(root->lch);
        }
        if (rch) {
            root->rch = new BST(rch);
            createTree(root->rch);
        }
        return;
    }
    
    void preorder(BST* root) {
        if (!root) return;
        stack<BST*> buff;
        buff.push(root);
        while (!buff.empty()) {
            root = buff.top();
            buff.pop();
            printf("%d ", root->val);
            if (root->rch) buff.push(root->rch);
            if (root->lch) buff.push(root->lch);
        }
        puts("");
    }
    
    void inorder(BST* root) {
        if (!root) return;
        stack<BST*> buff;
        while (!buff.empty() || root) {
            if (root) {
                buff.push(root);
                root = root->lch;
            } else {
                root = buff.top();
                buff.pop();
                printf("%d ", root->val);
                root = root->rch;
            }
        }
        puts("");
    }
    
    void postorder(BST* root) {
        if (!root) return;
        stack<BST*> buff;
        buff.push(root);
        BST *tmp = NULL;
        while (!buff.empty()) {
            tmp = buff.top();
            if (tmp->lch && root != tmp->lch && root != tmp->rch) {
                buff.push(tmp->lch);
            } else if (tmp->rch && root != tmp->rch) {
                buff.push(tmp->rch);
            } else {
                printf("%d ", tmp->val);
                buff.pop();
                root = tmp;
            }
        }
        puts("");
    }
    
    int main(void) {
        int n, rt;
        scanf("%d%d", &n, &rt);
        BST* root = new BST(rt);
        createTree(root);
        preorder(root);
        inorder(root);
        postorder(root);
        return 0;
    }
    
    展开全文
  • 遍历二叉树 MFC 先序 中序 后序 非递归 实现创建并遍历二叉树
  • 二叉树先序中序后序),代码适合初学者,学习数据结构用
  • NC45 实现二叉树先序中序和后序遍历 描述 分别按照二叉树先序中序和后序打印所有的节点。 示例1 输入: {1,2,3} 复制 返回值: [[1,2,3],[2,1,3],[2,3,1]] 复制 import java.util.*; public class Solution { ...
  • NewCoder045–实现二叉树先序中序和后序遍历 题目描述 分别按照二叉树先序中序和后序打印所有的节点。 示例1 输入 {1,2,3} 返回值 [[1,2,3],[2,1,3],[2,3,1]] 备注: n≤106n≤106n≤106n≤106n \leq 10^6n≤...
  • 给出一棵二叉树中序后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。 Input 两行,每行个字符串,分别表示中序和后序排列 Output 个字符串,表示所求先序排列 Sample Input ...
  • 分别按照二叉树先序中序和后序打印所有的节点。 2、解题1 递归方式 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * ...
  • 已知先序中序后序: /* 已知先序中序 求后序 */ #include <stdio.h> #include <string.h> #include <iostream> using namespace std; #define maxn 1010 int pre[maxn], in...
  • 简单算法 实现二叉树先序中序和后序遍历(java) 描述 分别按照二叉树先序中序和后序打印所有的节点。 想法:无 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null;...
  • 二叉树先序中序后序遍历 有递归与非递归两中做法
  • 程序设计任务: 设计个程序,演示二叉树先序中序后序的读取的过程。基本要求:以二叉树序列的形式从终端输入语法正确的二叉树。利用教科书6,.8(a)给出的二叉树关系,实现先序、中序后序的读取。测试数据:AB...
  • 非递归实现二叉树先序中序和后序遍历 用递归方式实现二叉树先序中序和后序遍历很简单。 用递归方法解决的问题都能用非递归的方法实现。递归就是利用函数栈来保存信息,如果用自己申请的数据结构来代替函数栈,...
  • 已知先序中序后序public class BinaryTree1 { private Node root; public void postOrder(){ postOrder(root); } //二叉树构造完毕之后进行后续遍历 private void postOrder(Node localroot) { if(localr
  • 二叉树先序中序后序遍历非递归实现 二叉树先序中序后序遍历非递归实现
  • 首先得明白什么是二叉树先序中序后序遍历: c++ 二叉树的创建 前中后序遍历 以及遇到的坑 给出先序中序遍历重建二叉树: 思路: 1二叉树的先序遍历的第个结点是根节点; 2、中序遍历的根节点左边的序列是左...
  • 二叉树先序中序得到后序,并画图,数据结构课程设计。简单易用。。但图像下面会交叉。
  • 笔试题常驻嘉宾-先序中序求后序 & 中序后序求先序 怎么破? 捞干的: 做过笔试题的童鞋 绝对不陌生吧 二叉树遍历问题几乎是必考点之 , 求解这类题思路非常重要: 最近琐事繁多图就比较简陋 但以老夫三寸不烂之舌,...
  • 根据先序 中序后序

    2016-05-23 11:24:20
    使用数组求解已知树的先序和中序求解后序的问题
  • 实现二叉树先序中序和后序遍历 题目描述: 分别按照二叉树先序中序和后序打印所有的节点。 花了个多小时才做出来。。。。 难点:不知道树节点个数即不能直接创建数组,怎么存储遍历的数值 思路: 用ArrayList...
  • 二叉树先序中序后序java实现) 代码实现: ** * 二叉树先序中序后序) */ public class Tree { private void preOrder(Node node){ if(node!=null){ System.out.println(node.data); preOrder(node.g...
  • 知道任何一棵二叉树先序和中序遍历的序列或者中序和后序的遍历序列,都能构造出唯一的一棵二叉树 下面先看一道PTA上的题引入思考 因为知道了先序遍历的特点,从第个开始,都先从根开始。 把先序的根在中序中...
  • 二叉树先序中序后序遍历的递归算法
  • 牛客题霸 [ 实现二叉树先序中序和后序遍历]C++题解/答案 题目描述 分别按照二叉树先序中序和后序打印所有的节点。 题解: 先序,中序后序都是按照各自规律的 先序的遍历顺序是中前后 中序是前中后 后序是前后...
  • 本文是左程云老师所著的《程序员面试代码指南》第三章中“分别用递归非递归方式实现二叉树先序中序和后序遍历”这题目的C++复现。 本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的...
  • 1.先序遍历(根左右),中序遍历(左根右)后序遍历(左右根)都可以用递归实现,类似于DFS,左子树都在右子树之前遍历,不同的是根的遍历顺序。层序遍历则类似于BFS。...3.二叉树先序中序后序遍历。遍历过程...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,722
精华内容 13,888
关键字:

一棵二叉树的先序中序和后序