精华内容
下载资源
问答
  • 二叉树的后序遍历非递归算法

    万次阅读 多人点赞 2019-06-03 11:51:45
    1. 对于树遍历我们最常用三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用方法是深度优先遍历树每一个节点,这些遍历方法都是使用递归函数来进行实现,在数据量大情况下是比较低效,原因在于...

    1. 对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用的方法是深度优先遍历树的每一个节点,这些遍历方法都是使用递归函数来进行实现的,在数据量大的情况下是比较低效的,原因在于系统帮助我们调用了一个栈并且做了诸如保护现场和恢复现场等复杂的操作,才使得遍历可以使用非常简单的代码来实现,所以我们可以模仿系统中调用的栈自己可以来写一下栈,模仿其中的过程就可以完成对于三种遍历算法的实现,使用自定义的栈来代替系统栈可以得到效率上的提升,下面是对于后序遍历的非递归算法的实现

    2. 首先模仿这个系统栈我们需要清楚的是系统栈为我们做了什么事情,下面以一棵二叉树为例来模仿其中的节点入栈与出栈的过程

    创建的二叉树如下:

     

    后序遍历为:5 3 2 4 1

    先序遍历为:1 2 5 3 4

    逆后序遍历为:1 4 2 3 5

    从逆后序遍历与先序遍历的关系中我们可以知道逆后序遍历序列为先序遍历交换左右子树的遍历顺序得到的,所以我们得到了逆后序序列之后然后逆序就可以得到后序遍历的序列了,所以需要两个栈,第一个栈用来存储先序遍历交换左右子树的遍历的中介结果,第二个是存储后序遍历的结果(逆序也就是可以理解为先进后出的意思)

    下面是模仿元素进栈与出栈的过程:

    ① 1节点进栈,在循环中弹出1节点压入到第二个栈中,发现左右节点不为空那么将左右节点压入栈1,这个与先序遍历中将左右子树压入到栈顶的顺序是相反的

    ② 弹出4节点压入到第二个栈中,发现左右孩子都为空那么不进行任何的操作

    ③ 弹出2节点压入到第二个栈中,发现左右节点不为空那么将左右节点压入到栈1中

    ④ 弹出3节点压入到第二个栈中,发现左右孩子都为空不进行任何操作

    ⑤ 弹出5节点压入到第二个栈中,发现左右孩子都为空不进行任何操作

    最后栈为空那么退出循环结束

    3. 具体的代码如下:

    import java.util.Stack;
    public class Main {
    	public static void main(String[] args) {
    		TreeNode<Integer> root = new TreeNode<Integer>(1);
    		TreeNode<Integer> l = new TreeNode<Integer>(2);
    		TreeNode<Integer> r = new TreeNode<Integer>(4);
    		TreeNode<Integer> ll = new TreeNode<Integer>(5);
    		TreeNode<Integer> lr = new TreeNode<Integer>(3);
    		root.left = l;
    		root.right = r;
    		l.left = ll;
    		l.right = lr;
    		postOrder(root);
    	}
    	
    	@SuppressWarnings({ "rawtypes", "unchecked" })
    	private static void postOrder(TreeNode<Integer> root) {
    		Stack<TreeNode> src = new Stack<TreeNode>();
    		Stack<TreeNode> res = new Stack<TreeNode>();
    		src.push(root);
    		while(!src.isEmpty()){
    			TreeNode<Integer> p = src.pop();
    			res.push(p);
    			if(p.left != null){
    				src.push(p.left);
    			}
    			if(p.right != null){
    				src.push(p.right);
    			}
    		}
    		//输出最终后序遍历的结果
    		while(!res.isEmpty()){
    			System.out.print(res.pop().val + " ");
    		}	
    	}
    
    	public static class TreeNode<T>{
    		T val;
    		TreeNode<T> left;
    		TreeNode <T> right;
    		public TreeNode(T val) {
    			super();
    			this.val = val;
    		}
    	}
    }
    

     

    展开全文
  • 二叉树的后序遍历非递归算法 关于 (1)如何利用前序遍历创建二叉树 (2)二叉树的前序、中序、后序递归遍历 (3)二叉树的前序、中序非递归遍历 都已经在之前两篇文章中说过了 利用前序遍历创建二叉树,二叉树的...

    二叉树的后序遍历非递归算法

    关于
    (1)如何利用前序遍历创建二叉树
    (2)二叉树的前序、中序、后序递归遍历
    (3)二叉树的前序、中序非递归遍历
    都已经在之前两篇文章中说过了
    利用前序遍历创建二叉树,二叉树的前序、中序、后序递归遍历
    二叉树的前序、中序非递归遍历

    接下来的代码主要是实现后序非递归遍历,
    这里要用到新的结构体list用来存在栈中

    思维图如下:
    在这里插入图片描述程序执行后,控制台窗口输入
    ABDH##I##E##CF#J##G##
    来构建二叉树
    在这里插入图片描述

    具体代码如下(之前的文章中代码也在):

    #include <iostream>
    #include <stack>
    using namespace std;
    
    typedef char datatype;
    
    //二叉树的左右链表示,也叫做二叉链表表示
    typedef struct node {
    	datatype data;
    	struct node* lchild;
    	struct node* rchild;
    }Node;
    
    typedef Node* Btree;
    
    
    //创建新的结构体list,包含Btree和int,来帮助实现后序非递归算法
    typedef struct list {
    	Btree ptr;
    	int flag;
    }List;
    
    
    Btree preCreateBT() {
    	Btree T;
    	char ch;
    	cin >> ch;
    	if (ch == '#') {
    		T = NULL;
    	}
    	else {
    		T = new node;
    		T->data = ch;
    		T->lchild = preCreateBT();
    		T->rchild = preCreateBT();
    	}
    	return T;
    }
    
    
    //先序遍历
    /*
    void PreOrder(Btree BT) {
    	if (BT != NULL) {
    		cout << BT->data<<endl;
    		PreOrder(BT->lchild);
    		PreOrder(BT->rchild);
    	}
    }
    */
    
    //中序遍历
    /*
    void InOrder(Btree BT) {
    	if (BT != NULL) {
    		InOrder(BT->lchild);
    		cout << BT->data << endl;
    		InOrder(BT->rchild);
    	}
    }
    */
    
    //后序遍历
    /*
    void PostOrder(Btree BT) {
    	if (BT != NULL) {
    		PostOrder(BT->lchild);
    		PostOrder(BT->rchild);
    		cout << BT->data << endl;
    	}
    }
    */
    
    //先序遍历非递归算法
    /*
    void PreOrderNoRecur(Btree root) {
    	stack<Btree> S;
    	while (root != NULL || !S.empty()) {
    		while (root != NULL) {
    			cout << root->data << endl;
    			S.push(root);
    			root = root->lchild;
    		}
    
    		if (!S.empty()) {
    			root = S.top();
    			S.pop();
    			root = root->rchild;
    		}
    	}
    }
    */
    
    //中序遍历非递归算法
    /*
    void InOrderNoRecur(Btree root) {
    	stack<Btree> S;
    	while (root != NULL || !S.empty()) {
    		while (root != NULL) {
    			S.push(root);
    			root = root->lchild;
    		}
    
    		if (!S.empty()) {
    			root = S.top();
    			cout << root->data << endl;
    			S.pop();
    			root = root->rchild;
    		}
    	}
    }
    */
    
    
    //后序遍历非递归算法
    void PostOrderNoRecur(Btree root) {
    	stack<List> newS;
    	while (root != NULL || !newS.empty()) {
    		while (root != NULL) {
    			List element;
    			element.ptr = root;
    			element.flag = 1;
    			newS.push(element);
    			root = root->lchild;
    		}
    		while (!newS.empty() && newS.top().flag == 2) {
    			cout << newS.top().ptr->data << endl;
    			newS.pop();
    		}
    		if (!newS.empty()) {
    			newS.top().flag = 2;
    			root = newS.top().ptr->rchild;
    		}
    	}
     }
    
    int main() {
    	//前序遍历创建树
    	Btree TreeOne = preCreateBT();
    	
    	//先序遍历(递归)
    	//PreOrder(TreeOne);
    
    	//中序遍历(递归)
    	//InOrder(TreeOne);
    
    	//后序遍历(递归)
    	//PostOrder(TreeOne);
    
    	//先序遍历非递归算法
    	//PreOrderNoRecur(TreeOne);
    
    	//中序遍历非递归算法
    	//InOrderNoRecur(TreeOne);
    
    	//后序遍历非递归算法
    	PostOrderNoRecur(TreeOne);
    	
    }
    
    展开全文
  • 作者Blog:http://blog.csdn.net/xuyongfeng/这个是比较好理解一个后序遍历非递归算法,可能是我学是C++缘故。另外有算法里面有flag(或者tag),让人很头晕。。。为了自己理解方便,添加了部分注释。#...
    
    
    这个是比较好理解的一个后序遍历非递归算法,可能是我学的是C++的缘故。另外有的算法里面有flag(或者tag),让人很头晕。。。
    为了自己理解方便,添加了部分注释。

    #include <stack>
    #include <iostream>
    using namespace std;

    template <class T>
    class TreeNode //定义节点类
    {
      public:
        T data;
        TreeNode<T> *left; //left child
        TreeNode<T> *right; //right child
        //构造函数
        TreeNode():left(NULL),right(NULL)
        {
        }

        TreeNode(const T& t):data(t),left(NULL), right(NULL)
        {
        }

        TreeNode(const T& t, TreeNode<T*> left, TreeNode<T*> right):data(t),left(left), right(left)
        {
        }
    };

    /*purpose: 对二叉树进行后序遍历(非递归算法)
      *@param TreeNode<T> *root the root of the binary tree

    */
    template <class T>
    void postOrder(TreeNode<T> *root)
    {
      stack<TreeNode<T>*> st;//定义栈,节点类型为TreeNode
      TreeNode<T> *p = root;
      TreeNode<T> *pre = NULL;//pre表示最近一次访问的结点
     
      while(p || st.size()!=0)
      {
        //沿着左孩子方向走到最左下 。
        while(p)
        {
          st.push(p);
          p = p->left;
        }
        //get the top element of the stack
        p = st.top();
        //如果p没有右孩子或者其右孩子刚刚被访问过
       if(p->right == NULL || p->right == pre)
        {
          //visit this element and then pop it
          cout << "visit: " << p->data << endl;
          st.pop();
          pre = p;
          p = NULL;    
        }
       else
       {
         p = p->right; 
       }
      }//end of while(p || st.size()!=0)

    }

    展开全文
  • stack[top-1]->tag)//如果没有访问栈顶右子树 { t=stack[top-1];//获得栈顶节点 t->tag=1;//标记栈顶节点访问了右节点 t=t->rchild;//进入栈顶右节点 } else { t=stack[--top];//栈顶元素出栈 ...
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    typedef struct node
    {
        int data,tag;
        struct node*lchild,*rchild;
    }tnode,*tree;
    tree creat()
    {
        int x;
        tree t;
        scanf("%d",&x);
        if(x==0)t=NULL;
        else
        {
            t=(tnode*)malloc(sizeof(tnode));
            t->data=x;
            t->lchild=creat();
            t->rchild=creat();
        }
        return t;
    }
    void postorder(tree t)
    {
        tree stack[200];
        int top=0;
        while(top||t)
        {
            if(t)
            {
                t->tag=0;//标记未访问结束
                stack[top++]=t;//入栈保存
                t=t->lchild;//进入左子树
            }
            else if(!stack[top-1]->tag)//如果没有访问栈顶的右子树
            {
                t=stack[top-1];//获得栈顶的节点
                t->tag=1;//标记栈顶的节点访问了右节点
                t=t->rchild;//进入栈顶的右节点
            }
            else
               {
                   t=stack[--top];//栈顶元素出栈
                   printf("%d\n",t->data);//访问完子节点,访问本节点
                   t=NULL;//该节点结束
               }
        }
    }
    void Postorder(tree t)
    {
        tree Stack[200];
        int  TagStack[200],top=0;
        while(t||top)
        {
            if(t)
            {
                Stack[top]=t;
                TagStack[top++]=0;
                t=t->lchild;
            }
            else if(!TagStack[top-1])
            {
                t=Stack[top-1];
                TagStack[top-1]=1;
                t=t->rchild;
            }
            else
            {
                t=Stack[--top];
                printf("%d\n",t->data);
                t=NULL;
            }
        }
    }
    int main()
    {
        tree t=creat();
        Postorder(t);
    }
    

    版权声明:本文为博主原创文章,未经博主允许不得转载。

    转载于:https://www.cnblogs.com/Thereisnospon/p/4768476.html

    展开全文
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序或者后序...
  • 二叉树的后序遍历非递归 算法思想:迭代写法,利用pre记录上一个访问过的结点,与当前结点比较,如果是当前结点的子节点,说明其左右结点均已访问,将当前结点出栈,更新pre记录的对象。** //结构体 typedef ...
  • 问题 G: DS二叉树--后序遍历非递归算法 时间限制: 1 Sec 内存限制: 128 MB 提交: 155 解决: 137 [提交][状态][讨论版] 题目描述 求一颗树的后序遍历的非递归算法 要求:必须是非递归算法,使用堆栈对象来实现 建树...
  • 在前面先后介绍了二叉树先序遍历非递归算法和中序遍历非递归算法,这里则来介绍二叉树后序遍历非递归算法二叉树后序非递归遍历真非常之 重要,因为它具有独特特性(文章结尾会阐述),所以,在很多与二叉树...
  • 数据结构实验报告 实验题目: 创建并遍历二叉树 实验目的熟悉二叉树存储结构熟悉二叉树的三种遍历方法并能用非递归的方法建立并且遍历二叉树 实验内容用先序和中序建立二叉树用后序遍历并输出二叉树要求算法非递归 ...
  • 用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现...2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历非递归算法思路 遍历过程:(如图所示) 图1 前序遍历和中序遍历流程图   ...
  • 这个是在前面基础上,进行后序遍历非递归算法,这个算法是很多求二叉树路径基础,比如求根结点到某点路径,或求两个结点最近公共祖先等。 代码: #include &lt;iostream&gt; #include &lt;...
  • 我们知道,用递归写这三种遍历是很简单也很容易理解,但是非递归算法却有点难度,研究非递归算法会加深我们对这一问题理解。那么该怎么写非递归程序呢,对于这个问题,我们看到无论哪种遍历,先访问到节点...
  • 数据结构与算法二叉树的后序遍历(递归与非递归方法) public class BinaryTree<E> { private TreeNode<E> root; //根节点 private List<TreeNode> nodeList = null; //二叉树节点的链式...
  • 用堆栈实现二叉树的前序遍历/中序遍历/后序遍历非递归算法算法思想中序遍历前序遍历后续遍历 算法思想 借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序...
  • 二叉树的后序遍历(非递归算法)

    千次阅读 2018-09-11 22:20:49
     后序遍历(非递归算法)  ①先序遍历顺序:根节点-左孩子-右孩子  ②后序遍历顺序:左孩子-右孩子-根节点  ③后序遍历倒过来:根节点-右孩子-左孩子  ①和③对比发现,访问顺序只有左孩子和右孩子颠倒了一下  ...
  • 145. 二叉树的后序遍历 递归解法与非递归解法 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? 解法1:递归 ...
  • 昨天写的前序遍历的递归与非递归算法,在非递归算法中主要还是借用到了栈这一工具,其实在中序遍历和后序遍历中依旧可以理由栈的特性来进行非递归的遍历 操作。 1.中序遍历 1.1 中序遍历的递归算法 二叉树的构造以...
  • 二叉树后序遍历(非递归)算法实现--C语言

    万次阅读 多人点赞 2018-12-18 16:14:37
      一直说要写二叉树的后序非递归遍历算法,但是前两天各种事情,今天终于有时间好好写一写二叉树的后序遍历算法。   二叉树的后序遍历算法比先序和中序的遍历算法要复杂一些。其出栈条件有两种情况: 栈顶元素...
  • 设计并实现基于后序线索二叉树的后序遍历非递归算法。 一、二叉树的创建 我们使用二叉链表得方式进行二叉树存数。每个结构有一个数据域,存放结点的数据,还有两个左右指针,以及两个标志。当标志为0时表示指向...
  • (1)假设二叉树采用链接存储方式存储,分别编写一个二叉树先序遍历的递归算法和非递归算法。 (2)一棵完全二叉树以顺序方式存储,设计一个递归算法,对该完全二叉树进 行中序遍历。 3.解题思路 (1)采用...
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序...
  • 以Java方式实现的二叉树前中后序遍历的递归及非递归方式
  • 非递归的前序遍历算法思路可以 /** * 后序遍历 非递归 * * 后序遍历顺序:左右根 -> 变换:先获得根右左遍历顺序,再反转( 根右左顺序可以通过栈即可实现) * * @param root */ private sta...
  • 二叉树的后序遍历-递归和非递归算法

    万次阅读 多人点赞 2018-11-16 15:14:49
    同样,创建算法在先序中有,略去。 后序递归遍历算法 void PostOrder(BiTree bt){ if(bt){ PostOrder(bt-&gt;lchild);... PostOrder(bt-&...后序非递归算法 思想:    先序序列: 1 、2 、3...
  • 前几天回家过中秋,我一直在想二叉树的3种遍历方法,今天在图书馆自习的时候想出来了,现在我跟大家先分享一下二叉树的3种遍历递归算法递归算法很简单,关键在于理解二叉树遍历的核心思想,话不多说,我们直接看...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,533
精华内容 613
关键字:

二叉树的后序遍历非递归算法