精华内容
参与话题
问答
  • 二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;父节点被访问的次序位于左右孩子...

    概述

    二叉树的遍历是一个很常见的问题。二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;父节点被访问的次序位于左右孩子节点之间,就是中序遍历;访问完左右孩子节点之后再访问父节点,就是后序遍历。不论是先序遍历、中序遍历还是后序遍历,左右孩子节点的相对访问次序是不变的,总是先访问左孩子节点,再访问右孩子节点。而层次遍历,就是按照从上到下、从左向右的顺序访问二叉树的每个节点。

    在介绍遍历算法之前,先定义一个二叉树的结构体。使用的是 C++ 语言。

    //filename: BinTreeNode.h
    template <typename T> struct BinTreeNode {
        T data; //数据域
        BinTreeNode * LeftChild; //左孩子节点指针
        BinTreeNode * RightChild; //右孩子节点指针
        BinTreeNode * parent; //父节点指针
    };
    

    先序遍历

    递归

    使用递归,很容易写出一个遍历算法。代码如下:

    //filename: BinTreeNode.h
    template <typename T>
    void travPre_R(BinTreeNode<T> * root) {//二叉树先序遍历算法(递归版)
        if (!root) return;
        cout << root->data;
        travPre_R(root->LeftChild);
        travPre_R(root->RightChild);
    }
    

    迭代

    在之前的文章中,我不止一次地说过,递归是很耗费计算机资源的,所以我们在写程序的时候要尽量避免使用递归。幸运的是,绝大部分递归的代码都有相应的迭代版本。那么我们就试着将上述递归代码改写成迭代的版本。改写之后,代码如下:

    //filename: BinTreeNode.h
    template <typename T>
    void travPre_I1(BinTreeNode<T> * root) {//二叉树先序遍历算法(迭代版#1)
        Stack<BinTreeNode<T>*> s; //辅助栈
        if (root) //如果根节点不为空
            s.push(root); //则令根节点入栈
        while (!s.empty()) { //在栈变空之前反复循环
            root = s.pop(); cout << root->data; //弹出并访问当前节点
    
            //下面左右孩子的顺序不能颠倒,必须先让右孩子先入栈,再让左孩子入栈。
            if (root->RightChild)
                s.push(root->RightChild); //右孩子先入后出
            if (root->LeftChild)
                s.push(root->LeftChild); //左孩子后入先出
        }
    }
    

    下面我们通过一个实例来了解一下该迭代版本是如何工作的。

    PS:黑色的元素表示已经被弹出并访问过。

    结合代码,该二叉树的先序遍历过程如下:

    1. 初始化一个空栈。
    2. 根节点入栈,此时将 a 入栈。
    3. 循环开始,弹出并访问栈顶元素,此时栈顶元素是 a。
    4. 如果 a 有右孩子,则将其右孩子节点入栈;如果 a 有左孩子,则将其左孩子节点入栈。此时栈中有 b、c 两个元素。
    5. 这时进入下一轮循环。弹出并访问栈顶元素,此时栈顶元素是 b。经检查,b 没有右孩子,也没有左孩子,进入下一轮循环。
    6. 弹出并访问栈顶元素,此时栈顶元素是 c。c 的右孩子是 f,左孩子是 d,故分别将 d、f 入栈。进入下一轮循环。
    7. 此时栈中的元素是 d、f。
    8. 弹出并访问栈顶元素,此时栈顶元素是 d。d 的右孩子是 e,d 没有左孩子,故将 e 入栈。进入下一轮循环。
    9. 此时栈中的元素是 e、f。
    10. 弹出并访问栈顶元素,此时栈顶元素是 e。e 没有左右孩子,进入下一轮循环。
    11. 弹出并访问栈顶元素,此时栈顶元素是 f。f 没有左右孩子,进入下一轮循环。
    12. 此时栈为空,退出循环。遍历结束。

    这个迭代的遍历算法非常简明,但是很遗憾,这种算法并不容易推广到我们接下来要研究的中序遍历和后序遍历。因此我问需要寻找另一种策略。

    第 2 种迭代方式

    我们来看一个规模更大、更具一般性的二叉树:

    这个二叉树的先序遍历序列是:idcabhfeglkjnmpo,也就是遵循了下图所示的顺序:

    再进一步,我们把二叉树抽象成下面这个样子,


    L_0 ~ L_d 是二叉树的左侧链上的节点, R_0 ~ R_d 分别是 L_0 ~ L_d 的右孩子,T_0 ~ T_d 分别是 L_0 ~ L_d 的右子树。不难发现,二叉树的先序遍历就是先自上而下访问左侧链上的节点,再自下而上访问左侧链上的节点的右子树。而我们的遍历算法,就是根据这样一个思路来进行设计。

    首先需要实现一个子方法,就是访问二叉树左侧链上的节点:

    //从当前节点出发,沿左分支不断深入,直至没有左分支的节点;沿途节点遇到后立即访问
    template <typename T> //元素类型、操作器
    static void visitAlongLeftBranch ( BinTreeNode<T>* x, Stack<BinTreeNode<T>*>& S ) {
       while ( x ) {
          cout << x->data; //访问当前节点
          if( x->RightChild )
               S.push ( x->RightChild ); //右孩子入栈暂存(可优化:通过判断,避免空的右孩子入栈)
          x = x->LeftChild;  //沿左分支深入一层
       }
    }
    

    然后是主方法,在主方法中,通过迭代,不断地调用上面这个子方法,从而实现完整的二叉树先序遍历。

    template <typename T> //元素类型、操作器
    void travPre_I2 ( BinTreeNode<T>* root) { //二叉树先序遍历算法(迭代版#2)
       Stack<BinTreeNode<T>*> S; //辅助栈
       while ( true ) {
          visitAlongLeftBranch ( root, S ); //从当前节点出发,逐批访问
          if ( S.empty() ) break; //直到栈空
          root = S.pop(); //弹出下一批的起点
       }
    }
    

    中序遍历

    递归

    与先序遍历类似,递归版的中序遍历算法很容易实现,代码如下:

    template <typename T>
    void travIn_R(BinTreeNode<T> * root) {//二叉树先序遍历算法(递归版)
        if (!root)
            return;
        travPre_R(root->LeftChild);
        cout << root->data;
        travPre_R(root->RightChild);
    }
    

    递归代码不仅容易实现,也很好理解,这里不再做过多解释。

    迭代

    参照迭代式先序遍历版本 2 的思路,在宏观上,我们可以将中序遍历的顺序抽象为,先访问二叉树的左侧链上的最底部的节点,然后访问该节点的右子树(如果有的话),然后访问该节点的父节点,然后访问该节点的父节点的右子树(如果有的话)……直至全部节点被访问完毕。如下图所示:

    按照以上思路,可以实现迭代版中序遍历算法如下:

    template <typename T> //从当前节点出发,沿左分支不断深入,直至没有左分支的节点
    static void goAlongLeftBranch ( BinTreeNode<T> * x, Stack<BinTreeNode<T> * >& S ) {
        while (x) { S.push(x); x = x->LeftChild; } //当前节点入栈后随即向左侧分支深入,迭代直到无左孩子
    }
    

    template <typename T> //元素类型、操作器
    void travIn_I(BinTreeNode<T> root) {//二叉树先序遍历算法(迭代版)
    Stack<BinTreeNode<T> > S; //辅助栈
    while ( true ) {
    goAlongLeftBranch ( root, S ); //从当前节点出发,逐批入栈
    if ( S.empty() ) break; //直至所有节点处理完毕
    root = S.pop();
    cout << root->data; //弹出栈顶节点并访问之
    root = root->RightChild; //转向右子树
    }
    }

    也可以对代码稍加改进,将这两个方法写成一个方法:

    template <typename T> //元素类型
    void travIn_I2 ( BinTreeNode<T> root ) { //二叉树中序遍历算法(迭代版#2)
    Stack<BinTreeNode<T>> S; //辅助栈
    while ( true )
    if ( root ) {
    S.push ( root ); //根节点进栈
    root = root->LeftChild; //深入遍历左子树
    } else if ( !S.empty() ) {
    root = S.pop(); //尚未访问的最低祖先节点退栈
    cout << root->data; //访问该祖先节点
    root = root->RightChild; //遍历祖先的右子树
    } else
    break; //遍历完成
    }

    后序遍历

    递归

    与前两个一样,二叉树的后序遍历算法可以很容易地用递归的方式实现。

    template <typename T>
    void travPost_R(BinTreeNode<T> root) {//二叉树先序遍历算法(递归版)
    if (!root)
    return;
    travPost_R(root->LeftChild);
    travPost_R(root->RightChild);
    cout << root->data;
    }

    迭代

    但是要想用迭代的方式实现后序遍历算法,则有一定的难度,因为左、右子树的递归遍历均严格地不属于尾递归。不过,仍可继续套用此前的思路和技巧,考虑一下,后序遍历中,首先访问的是哪个节点?答案就是二叉树的最高最左侧的叶子节点。

    由于最高最左侧的叶子节点 V 可能是左孩子节点,也可能是右孩子节点,所以 V 与其父节点之间的联接用竖直的线表示。考查联接于 V 与树根之间的唯一通路(以粗线示意)。与先序与中序遍历类似地,自底而上地沿着该通路,整个后序遍历序列也可以分解为若干个片段。每一片段,分别起始于通路上的一个节点,并包括三步:访问当前节点,遍历以其右兄弟(若存在)为根的子树,以及向上回溯至其父亲节点(若存在)并转入下一片段。

    基于以上理解,即可写出迭代式后序遍历算法。

    template <typename T> //在以S栈顶节点为根的子树中,找到最高左侧叶节点
    static void gotoHLVFL ( Stack<BinTreeNode<T>>& S ) { //沿途所遇节点依次入栈
    while ( BinTreeNode<T>* x = S.top() ) //自顶而下,反复检查当前节点(即栈顶)
    if ( x->LeftChild ) { //尽可能向左
    if ( x->RightChild ) S.push ( x->RightChild ); //若有右孩子,优先入栈
    S.push ( x->LeftChild ); //然后才转至左孩子
    } else //实不得已
    S.push ( x->RightChild ); //才向右
    S.pop(); //返回之前,弹出栈顶的空节点
    }

    template <typename T>
    void travPost_I ( BinTreeNode<T> root ) { //二叉树的后序遍历(迭代版)
    Stack<BinTreeNode<T>> S; //辅助栈
    if ( root ) S.push ( root ); //根节点入栈
    while ( !S.empty() ) {
    if ( S.top() != root->parent ) //若栈顶非当前节点之父(则必为其右兄),此时需
    gotoHLVFL ( S ); //在以其右兄为根之子树中,找到HLVFL(相当于递归深入其中)
    root = S.pop(); cout << root->data; //弹出栈顶(即前一节点之后继),并访问之
    }
    }

    层次遍历

    在文章开头我们已经对层次遍历做了介绍,层次遍历严格按照自上而下、自左向右的顺序访问树的节点。所以我们需要用队列作为辅助,具体代码如下:

    template <typename T> //元素类型
    void travLevel ( BinTreeNode<T> root ) { //二叉树层次遍历算法
    Queue<BinTreeNode<T>> Q; //辅助队列
    Q.enqueue ( root ); //根节点入队
    while ( !Q.empty() ) { //在队列再次变空之前,反复迭代
    BinTreeNode<T>* x = Q.dequeue(); cout << x->data; //取出队首节点并访问之
    if ( x->LeftChild ) Q.enqueue ( x->LeftChild ); //左孩子入队
    if ( x->RightChild ) Q.enqueue ( x->RightChild ); //右孩子入队
    }
    }

    好了,以上就是二叉树的几种常见的遍历方式。

    展开全文
  • 树-后序遍历(3种解法)

    千次阅读 2018-05-28 21:30:24
    树: 后序遍历:左-右-根 CEFDBHGA1、递归typedef char ElemType;树的数据结构:typedef struct BtNode { BtNode *leftchild; BtNode *rightchild; ElemType data; }BtNode,...

    树:                              

                            

    后序遍历:左-右-根   CEFDBHGA

    1、递归

    typedef char ElemType;
    树的数据结构:
    typedef  struct BtNode
    {
    	BtNode *leftchild;
    	BtNode *rightchild;
    	ElemType data;
    }BtNode,*Binary_Tree;
    void PastOrder(BtNode *ptr)
    {
    	if(ptr!=NULL)
    	{
    		PastOrder(ptr->leftchild);
                    PastOrder(ptr->rightchild);
    		cout<<ptr->data<<" ";
    	}
    }

    2、非递归

    一般非递归我们会想到栈,栈有先进后出的特点。 我们或许觉得只要改变输出节点数据的位置就可以了,但是结果会发生什么呢?



    所以我们需要一个东西来保存   节点D  上一个节点的访问情况,那么我们是不是可以 利用指针来跟踪节点。

    void NicepastOrder(BtNode *ptr)//指针跟踪
    {
    	stack<BtNode *> s;
    	BtNode *tag=NULL;
    	if(ptr==NULL)  return;
    	while(ptr!=NULL || !s.empty())
    	{
    	        while(ptr!=NULL)
    		{
    			s.push(ptr);
    			ptr=ptr->leftchild;
    		}
    		ptr=s.top();
    		s.pop();
    		if(ptr->rightchild==NULL || ptr->rightchild==tag)
    		{
    			cout<<ptr->data<<" ";
    			tag=ptr;
    			ptr=NULL;   //注意如果没有这句,就往栈中重复入C 节点
    		}
    		else
    		{
    		       s.push(ptr);
    		       ptr=ptr->rightchild;
    		}
    	}
    	cout<<endl;
    }

    3、利用结构体解法:


    看下面代码,模拟运行过程就理解了

    struct StKNode
    {
        BtNode *Pnode;
        int popnum;     
    public:
        StKNode(BtNode *p=NULL):Pnode(p),popnum(0)
        {}
    
    };
    void StKNicepastOrder(BtNode *ptr)
    {
            if(ptr==NULL)  return;
    	stack<StKNode>  st;
    	StKNode node;
    	st.push(StKNode(ptr));
    	while(!st.empty())
    	{
    	    node=st.top();
    		st.pop();
    		if(++node.popnum==3)
    		{
    			cout<<node.pnode->data<<" ";
    		}
    		else
    		{
    		        st.push(node);
    			if(node.popnum==1 && node.pnode->leftchild!=NULL)
    			{
    			    st.push(node.pnode->leftchild);
    			}
    			if(node.popnum==2 && node.pnode->rightchild!=NULL)
    			{
    			   st.push(node.pnode->rightchild);
    			}
    		}
    
    	}
    }

             

    展开全文
  • 二叉树(前序、中序、后序遍历图片步骤详解)

    万次阅读 多人点赞 2019-06-08 15:40:59
    首先我们有这么一颗二叉树: 前序遍历:根结点 —>...后序遍历:左子树 —> 右子树 —> 根结点 这棵树的前序遍历为:DGHEBFCA 层次遍历:按层次遍历 这棵树的前序遍历为:ABCDEF...

    首先我们有这么一颗二叉树:
    在这里插入图片描述

    • 前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)

    这棵树的前序遍历为:ABDEGHCF

    • 中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)

    这棵树的中序遍历为:DBGEHACF

    • 后序遍历:左子树 —> 右子树 —> 根结点(最后遍历根节点)

    这棵树的后序遍历为:DGHEBFCA

    • 层次遍历:按层次遍历

    这棵树的层次遍历为:ABCDEFGH

    ps: 所谓的前序、中序、后续,就是对根节点而言的,左右的遍历顺序不变,前序就是根节点最先遍历,然后左右;中序就是把根节点放在中间遍历;后序则是把根节点放在最后遍历。


    • 笔试题:已知二叉树前序遍历为:ABDEGHCF,中序遍历为:DBGEHACF,求后序遍历

    分析:

    1. 首先我们由前序遍历可知根节点为A
    2. 已知根节点为A,由中序遍历可知左子树为DBGEH,右子树为CF

    确定这两点后就很容易推算出原来的二叉树的样子了。
    我们看到右子树节点为CF,中序遍历也是CF,那么就可以推断出现在的二叉树右边是这个样子:
    在这里插入图片描述
    为什么F不是左子树呢,因为如果F在左边,中序遍历的顺序就变成FC了

    由前序遍历AB可以知,A的左子树肯定是B,那么现在的树就是这样的:
    在这里插入图片描述
    再由中序遍历DB可知,D为B的左子树
    在这里插入图片描述

    现在只剩下EGH没确定了
    首先我们要确定的是D肯定没有子树,如果有,中序遍历就不会是DB了
    由前序遍历可知E节点只能是B的右子树了
    在这里插入图片描述
    ,最后由中序遍历GEH可知完整的二叉树为:
    在这里插入图片描述

    推断出整棵树后其他的遍历就都很容易写出来了。

    这种题的关键是确定根节点和左右子树。如果是已知后序遍历,也是一样的最后一个就是根节点。

    展开全文
  • 关于二叉树的前序、中序、后序三种遍历

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

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

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

        

    比如上图二叉树遍历结果

        前序遍历:ABCDEFGHK

        中序遍历:BDCAEHGKF

        后序遍历:DCBHKGFEA

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


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

    万次阅读 多人点赞 2018-11-08 23:03:30
    二叉树的原理及二叉树的三种遍历方式,假设父节点是D,左节点是L,...后序遍历 L-&amp;amp;amp;amp;gt;R-&amp;amp;amp;amp;gt;D 知道中序遍历和后续遍历,如何画出二叉树,并写出前序遍历。要是知道前序和后
  • 二叉树的先序、中序、后序遍历序列

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

    万次阅读 多人点赞 2018-09-14 11:36:18
    二叉树是数据结构中的重要知识点,最近准备笔试的时候总是会有...我们知道,二叉树的遍历有三种,分别是前序遍历、中序遍历和后序遍历,我们来看看这三种遍历的特性: 前序遍历(根--&gt;左--&gt;右)  ...
  • 二叉树顺序存储之 前序,中序 ,后序遍历

    万次阅读 多人点赞 2019-03-21 18:24:56
    二叉树遍历的概念: 二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。 1、前序遍历 先输出当前结点的数据,再依次遍历输出左结点和右结点 如下...
  • [算法] 二叉树的 先序遍历、中序遍历、后序遍历

    万次阅读 多人点赞 2018-02-27 16:28:05
    本文根据清华大学邓俊辉老师课程...二叉树本身并不具有天然的全局次序, 故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序, 间接地定义某种全局次序。 按惯例左兄弟优先于右兄弟, 若记做节点 V ,...
  • 后序遍历非递归算法

    千次阅读 2018-05-15 11:02:33
    后序遍历 方法一: //后序遍历 void PostOrderWithoutRecursion(BTNode* root) { if (root == NULL) return; stack<btnode*> s; //pCur:当前访问节点,pLastVisit:上次访问节点 BTNode* pCur, *...
  • 二叉树后序遍历非递归算法(有问题) 分析: a(flag=1),只遍历完左子树,右子树尚未遍历,则该结点不出栈,利用栈顶结点找到它的右子树,准备遍历 b(flag=2),遍历完右子树,将该结点出栈,并访问它 */ struct ...
  • 二叉树的后序遍历非递归算法

    万次阅读 2019-06-03 11:51:45
    1. 对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用的方法是深度优先遍历树的每一个节点,这些遍历方法都是使用递归函数来进行实现的,在数据量大的情况下是比较低效的,原因在于...
  • 后序遍历中,二叉树的根节点需要其左右子树
  • 二叉树的后序遍历非递归算法 关于 (1)如何利用前序遍历创建二叉树 (2)二叉树的前序、中序、后序递归遍历 (3)二叉树的前序、中序非递归遍历 都已经在之前两篇文章中说过了 利用前序遍历创建二叉树,二叉树的...
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序...
  • 二叉树的三种遍历非递归版本是数据结构
  • 后序遍历非递归算法的实现 这个是在前面的基础上,进行后序遍历非递归算法,这个算法是很多求二叉树路径的基础,比如求根结点到某点的路径,或求两个结点最近的公共祖先等。 代码: #include &lt;iostream&...
  •  后序遍历非递归算法。思路参考来自这里。思路是当当前结点没有左孩子或右孩子或左孩子和右孩子已经被访问的情况下,访问该结点。 具体思路如下: 当前结点左子树不为空且左孩子和右孩子没有被访问过的情况下,...

空空如也

1 2 3 4 5 ... 20
收藏数 74,443
精华内容 29,777
关键字:

后序遍历