精华内容
参与话题
问答
  • 关于二叉树的前序、中序、后序三种遍历

    万次阅读 多人点赞 2018-05-07 12:25:02
    二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先左...

    二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。

    比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右);中序顺序是BAC(先左后根最后右);后序顺序是BCA(先左后右最后根)。

        

    比如上图二叉树遍历结果

        前序遍历:ABCDEFGHK

        中序遍历:BDCAEHGKF

        后序遍历:DCBHKGFEA

    分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析)


    展开全文
  • 最近有同学考计算机二级不懂树遍历的计算,就找上我解惑。作为老好人的博主的我,但是义不容辞的上来阐述了一番。 先来官方的概念: 树的遍历:是指对树中所有结点信息的访问...先序遍历(先根遍历):先访问根节...

    最近有同学考计算机二级不懂树遍历的计算,就找上我解惑。作为老好人的博主的我,但是义不容辞的上来阐述了一番。

    先来官方的概念:

    树的遍历:是指对树中所有结点信息的访问,即依次对树中每个结点的访问一次且仅访问一次。
    分为:先序遍历,后序遍历,层次遍历。(普通的树是没有中序遍历的)

    这里我们说一下二叉树的遍历:

    二叉树的遍历分成三种,按照根节点的访问先后分为:
    先序遍历(先根遍历):先访问根节点,然后访问左子树, 最后访问右子树。
    中序遍历(中根遍历):先访问左子树,然后访问根节点, 最后访问右子树。
    后续遍历(后根遍历):先访问左子树,然后访问右子树, 最后访问根节点

    如:
    在这里插入图片描述

    先序遍历的顺序:ABC (先根节点A,在左子树B,然后右子树C);
    中序遍历的顺序:BAC (先左子树B,在根节点A,然后右子树C);
    后序遍历的顺序:BCA (先左子树B,在右子树C,然后根节点A)。

    在这里插入图片描述
    上图二叉树遍历结果:

    先序遍历:ABDFCEGHI
    中序遍历:BFDACHGIE
    后序遍历:FDBHIGECA
    

    第一种分析方法:(此处分析先序遍历)

    ①:从A根节点开始,根据先序遍历的原则:首先访问根节点A,然后访问它的左子树B, 在访问右子树C,遍历顺序就是A->B->C
    ②:左子树B 也按照先序遍历的原则来处理, 遍历顺序就是B->D。B的右子树也按照先序遍历的原则,顺序是D->F
    ,就可以得到A->B->D->F->C
    ③:右子树C按照先序遍历的原则处理,顺序是C->E,同理C的子树得遍历顺序E->G->H->I
    那么, 这棵树先序遍历的结果就是,A->B->D->F->C->E->G->H->I

    这是递归思路,根据原则遍历子树,子树没了子节点遍历完,则遍历同深度。

    第二种分析方法:(此处分析中序遍历)

    在这里插入图片描述

    推导计算,两种遍历序列算出第三种序列。
    在这里插入图片描述
    记住两点:
    先序,后序遍历可以确定根节点。
    中序遍历可以确定左子树和右子树。
    做这种题就是,反复来回这两点
    题目分析:

    由前序遍历知道,A是根节点。
    则根据中序遍历 知道HBDF是左子树 EKCG是右子树的
    然后在根据前序遍历 BHFD 知道B是左子树的根节点 ,再根据中序遍历知道H是左子树,DF是右子树,同理F是根,D是左子树。
    由此也可推出A的右子树的结构
    所有整个树的结构是:
    在这里插入图片描述
    因此后序遍历是:
    HDFBKGCEA
    答案是B

    展开全文
  • 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

     

     

     

    展开全文
  • 二叉树的先序、中序、后序遍历序列

    万次阅读 多人点赞 2018-06-08 10:41:57
    二叉树的遍历主要有三种: (1)先(根)序遍历(根左右) (2)中(根)序遍历(左根右) (3)后(根)序遍历(左右根) 举个例子: 先(根)序遍历(根左右):A B D H E I C F J K G 中(根)序遍历(左根右) : D...

        二叉树的遍历主要有三种:

    (1)先(根)序遍历(根左右)

    (2)中(根)序遍历(左根右)

    (3)后(根)序遍历(左右根)

    举个例子:

    先(根)序遍历(根左右):A B D H E I C F J K G

    中(根)序遍历(左根右) : D H B E I A J F K C G

    后(根)序遍历(左右根) : H D I E B J K F G C A

        以后(根)序遍历为例,每次都是先遍历树的左子树,然后再遍历树的右子树,最后再遍历根节点,以此类推,直至遍历完整个树。

        此外,还有一个命题:给定了二叉树的任何一种遍历序列,都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意的另一种遍历序列,就可以唯一地确定二叉树。

    例子1:已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba)。

    (1)中序遍历:debac

    后序遍历:dabec

    后序遍历序列的最后一个结点是根结点,所以可知c为根结点。

    中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点c只有左子树,没有 右子树。

     

    (2)中序遍历:deba

    后序遍历:dabe

    后序遍历序列的最后一个结点是根结点,所以可知e为c的左子树的根结点。

    中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点e的左子结点是d,右子树是ba。

     

    (3)中序遍历:ba

    后序遍历:ab

    由后序遍历序列可知b为e的右子树的根结点。由中序遍历序列中可看出,a为根结点b的右子结点。

    树的结构如下:

    class Node:
        def __init__(self, dat, left=None, right=None):
            self.data = dat
            self.left = left
            self.right = right
    
    
    def rebuild(rear, center):
        if not rear:
            return
        cur = Node(rear[-1])
        index = center.index(rear[-1])
        cur.left = rebuild(rear[:index], center[:index])
        cur.right = rebuild(rear[index:-1], center[index + 1:]) #rear[index:-1]是到倒数第二个数
        return cur
    
    
    def pre_order(t):
        if t == None:
            return
        print(t.data)
        pre_order(t.left)
        pre_order(t.right)
    
    
    if __name__ == "__main__":
        rear = ['d','a','b','e','c']
        center = ['d','e','b','a','c']
        t = rebuild(rear, center)
        pre_order(t)

    例子2:已知二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,它的前序遍历序列是(gdbehfca)。

     

    (1)先序遍历:abdgcefh

    中序遍历:dgbaechf

    先序遍历序列的第一个结点是根结点,所以可知a为根结点。

    中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点a的左子树是dgb,右子树是echf。

    a的左子树:

    (2)先序遍历:bdg

    中序遍历:dgb

    先序遍历序列的第一个结点是根结点,所以可知b为a的左子树的根结点。

    中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点b的左子树是dg,没有右子树。

     

    b的左子树:

    (3)先序遍历:dg

    中序遍历:dg

    由先序遍历序列可知d为b的左子树的根结点。

    中序遍历序列的根结点在中间,其左边是左子树,右边是右子树。所以从中序遍历序列中可看出,根结点d的右子结点是g。

     

    a的右子树:

     

    (4)先序遍历:cefh

    中序遍历:echf

    由先序遍历序列可知c为a的右子树的根结点。

    从中序遍历序列中可看出,根结点c的左子结点是e,右子树是hf。

     

     

    c的右子树:

    (5)先序遍历:fh

    中序遍历:hf

    由先序遍历序列可知f为c的右子树的根结点。

    从中序遍历序列中可看出,根结点f的左子结点是h,没有右子树。

    树的结构如下:

    class Node:
        def __init__(self, dat, left=None, right=None):
            self.data = dat
            self.left = left
            self.right = right
    
    
    def rebuild(pre, center):
        if not pre:
            return
        cur = Node(pre[0])
        index = center.index(pre[0])
        cur.left = rebuild(pre[1:index + 1], center[:index])
        cur.right = rebuild(pre[index + 1:], center[index + 1:])
        return cur
    
    
    def post_order(t):
        if t == None:
            return
        post_order(t.left)
        post_order(t.right)
        print(t.data)
    
    
    if __name__ == "__main__":
        pre = ['a','b','d','g','c','e','f','h']
        center = ['d','g','b','a','e','c','h','f']
        t = rebuild(pre, center)
        post_order(t)

     

    展开全文
  • 二叉树的遍历方式有 先序遍历(preorder traeversal)、中序遍历(inorder traversal)、后序遍历(postorder traversal) 三种,假设结点为 N,左子结点为 L,右子结点为 R。则: 先序遍历:NLR(N 在最前面) 中序遍历...
  • 二叉树的先序遍历

    千次阅读 2019-10-04 09:21:14
    给定一组输入数据,要求按照该输入数据构造一棵二叉树并且使用非递归的先序遍历算法遍历该二叉树。PS:不能使用递归先序遍历算法,必须是非递归。 Input 按照满二叉树的对应位置(即将输入的元素层序按从根到叶节点,...
  • 根据二叉树先序遍历和中序遍历构建二叉树

    万次阅读 多人点赞 2019-04-24 21:20:37
    对于本题,根据二叉树先序遍历和中序遍历构建二叉树,思路: 我们可以求得根节点左子树的先序和中序序列,以及右子树的先序和中序序列 此问题变成了根据左子树的先序和序列构建左子树的二叉树,根据右子树的先序和...
  • 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA eg2: 前序遍历:1 2 4 5 7 8 3 6 中序遍历:4 2 7 5 8 1 3 6 后序遍历:4 7 8 5 2 6 3 1 层次遍历:1 2 3 4 5 6 7 8 ...
  • 非递归实现先序遍历

    千次阅读 2019-01-22 22:19:11
  • [算法] 二叉树的 先序遍历、中序遍历、后序遍历

    万次阅读 多人点赞 2018-02-27 16:28:05
    本文根据清华大学邓俊辉老师课程...二叉树本身并不具有天然的全局次序, 故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序, 间接地定义某种全局次序。 按惯例左兄弟优先于右兄弟, 若记做节点 V ,...
  • 二叉树遍历方式分为三种:先序,中序和后序。 可以以根节点的位置为参考来记遍历方式,在第一个为先序,中间为中序,最后为后序; 即:先序: 根左右;中序:左根右;后序:左右根。 借个图: 之前看过一个...
  • 快速判断二叉树先序遍历 后序遍历

    千次阅读 2019-04-09 18:29:24
    一、知道二叉树的先序/后序遍历和中序遍历(中序必须要知道,不然无法判断),要快速判断后序/先序遍历,首先要了解二叉树的遍历规律 二、二叉树遍历规律 1、三种遍历都有一个规律,就是:逆时针沿着二叉树外缘...
  • 二叉树的先序遍历-递归和非递归算法

    万次阅读 多人点赞 2018-11-16 13:55:04
    需要实践先序遍历,我们先建立二叉树。这里采用先序序列建立二叉树,不为别的,因为简单。 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }*BiTree, BiTNode...
  • C++先序遍历的顺序建立二叉链表
  • 【算法步骤】 扫描字符序列,读入字符ch. ...创建二叉链表如图所示: 代码如下: #include <iostream> using namespace std; typedef struct BiNode { char date; //二叉链表的定义 struct BiNode *lchi
  • #include #include<stdlib.h>#define FALSE 0 #define TRUE 1 #define ERROR 0 #define OK 1 #define OVERFLOW -2 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 ...//二叉树的二叉链表
  • 补充树的3中遍历方式: 看下图: 先序遍历序列(4,1,3,2,6,5,7) 中序遍历序列(1,2,3,4,5,6,7) 后序遍历序列(2,3,1,5,7,6,4) 观察遍历的方式,我们...如果给出一棵树的先序遍历或者后序遍历让你还原树,是不可能的...
  • 已知二叉树按照二叉链表方式存储,利用栈的基本操作写出先序遍历非递归形式的算法: void pre_order(BiTree root); 在遍历过程中,pre_order函数需要调用 visit_node 函数来实现对结点的访问,该函数声明如下: ...
  • 转载自:...#include //定义节点 typedef struct btnode { char value; struct btnode *left; struct btnode *right;...//该函数的作用是:返回在中序遍历序列数组中
  • 1、二叉树的数据结构:二叉链表 package BT; public class BinearyTree&lt;E&gt; {  E data;   BinearyTree&lt;E&gt; lchild;  BinearyTree&lt;E&gt; rchild;  public BinearyTree(E...

空空如也

1 2 3 4 5 ... 20
收藏数 47,855
精华内容 19,142
关键字:

先序遍历