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

    千次阅读 2016-04-16 16:47:33
    二叉树的后续遍历的非递归算法二叉树的先序和中序遍历的非递归算法相比稍微复杂一点。 大致思路是:如果当前结点左右子树均为空,则可以访问当前结点,或者左右子树不均为空,但是前一个访问的结点是当前结点的左...

    二叉树的后序遍历的非递归算法与二叉树的先序和中序遍历的非递归算法相比稍微复杂一点。

    大致思路是:如果当前结点左右子树均为空,则可以访问当前结点,或者左右子树不均为空,但是前一个访问的结点是当前结点的左孩子或者右孩子,则也可以访问当前结点,如果前面两种情况均不满足(即,当前结点的左右孩子不均为空,并且前一个访问的结点不是当前结点左右孩子中的任意一个),则若当前结点的右孩子不为空,将右孩子入栈,若当前结点的左孩子不为空,将左孩子入栈。

    代码如下:

    public static void postOrder(TreeNode root) {
    		if(root==null) return;
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		TreeNode current = null;
    		TreeNode pre = null;
    		stack.push(root);
    		while(!stack.isEmpty()) {
    			current = stack.peek();
    			if((current.left==null && current.right==null) || (pre!=null && (pre == current.left || pre == current.right))) {
    				System.out.println(current.val);
    				stack.pop();
    				pre = current;
    			}
    			else {
    				if(current.right!=null) {
    					stack.push(current.right);
    				}
    				if(current.left != null) {
    					stack.push(current.left);
    				}
    			}
    		}
    	}

    参考:http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html


          

    展开全文
  • 主要是前3种遍历的非递归写法。我们知道,用递归写这三种遍历是很简单也很容易理解的,但是非递归算法却有点难度,研究非递归的算法会加深我们对这一问题的理解。那么该怎么写非递归的程序呢,对于这个问题,我们...

    以下代码实现了一个二叉树类,包含了它的4种遍历方法,分别是前序遍历,中序遍历,后序遍历和层序遍历。主要是前3种遍历的非递归写法。我们知道,用递归写这三种遍历是很简单也很容易理解的,但是非递归算法却有点难度,研究非递归的算法会加深我们对这一问题的理解。那么该怎么写非递归的程序呢,对于这个问题,我们看到无论哪种遍历,先访问到的节点总是后输出,因为这个特点,所以可以采用栈来模拟;如果是先访问的先输出,则采用队列来模拟。具体到每种遍历算法,代码本身写得写比较容易看懂,因为是python,所以就像写英文文章一样。其中后序遍历估计比较难看懂,本身也不好写,应该可以优化很多,但我暂时搞不定了。

    后记:算法老师提示用两个栈解决了后序遍历的问题。确实这样代码简单多了,但方法比较难想出来。

    #!/usr/bin/env python

    # -*- coding: utf-8 -*-

    class BinaryTreeNode:

    def __init__(self, data, left, right):

    self.data = data

    self.left = left

    self.right = right

    class BinaryTree:

    def __init__(self):

    self.root = None

    def maketree(self, data, left, right):

    self.root = BinaryTreeNode(data, left, right)

    def create(self):

    #data = input()

    data = testdata.pop()

    if data == 0:

    return None

    else:

    self.maketree(data, BinaryTree(), BinaryTree())

    if not self.root.left.create():

    self.root.left = None

    if not self.root.right.create():

    self.root.right = None

    return True

    def is_empty(self):

    if self.root is None:

    return True

    else:

    return False

    def pre_order(self, r):

    if r.root is not None:

    print r.root.data

    if r.root.left is not None:

    self.pre_order(r.root.left)

    if r.root.right is not None:

    self.pre_order(r.root.right)

    def pre_order_nonrecursion(self):

    stack = []

    # initialize stack

    stack.append(self.root)

    while len(stack) != 0:

    p = stack.pop()

    print p.data

    if p.right is not None:

    stack.append(p.right.root)

    if p.left is not None:

    stack.append(p.left.root)

    def in_order(self, r):

    if r.root is not None:

    if r.root.left is not None:

    self.in_order(r.root.left)

    print r.root.data

    if r.root.right is not None:

    self.in_order(r.root.right)

    def in_order_nonrecursion(self):

    stack = []

    # initialize stack

    stack.append(self.root)

    p = self.root

    while p.left is not None:

    stack.append(p.left.root)

    p = p.left.root

    while len(stack) != 0:

    p = stack.pop()

    print p.data

    if p.right is not None:

    stack.append(p.right.root)

    p = p.right.root

    while p.left is not None:

    stack.append(p.left.root)

    p = p.left.root

    def post_order_nonrecursion_v1(self):

    stack_1 = []

    stack_2 = []

    stack_1.append(self.root)

    while len(stack_1) != 0:

    p = stack_1.pop()

    stack_2.append(p.data)

    if p.left is not None:

    stack_1.append(p.left.root)

    if p.right is not None:

    stack_1.append(p.right.root)

    stack_2.reverse()

    print stack_2

    def level_order(self):

    q = []

    p = self.root

    print p.data

    while p is not None:

    if p.left is not None:

    q.append(p.left.root)

    if p.right is not None:

    q.append(p.right.root)

    if len(q) == 0:

    p = None

    else:

    p = q.pop(0)

    print p.data

    if __name__ == '__main__':

    # build a simplest binary tree.

    r = BinaryTree()

    r.create()

    print 'pre_order:'

    # r.pre_order(r)

    r.pre_order_nonrecursion()

    print 'in_order:'

    # r.in_order(r)

    r.in_order_nonrecursion()

    print 'post_order:'

    #r.post_order(r)

    r.post_order_nonrecursion()

    print 'level_order:'

    r.level_order()

    展开全文
  • 首先非常感谢‘hicjiajia’博文:二叉树后序遍历(非递归) 这篇随笔开启我博客进程,成为万千程序员中一员,坚持走到更远! 折磨了我一下午后序遍历中午得到解决,关键在于标记右子树是否被访问过,考虑过...

    首先非常感谢‘hicjiajia’的博文:二叉树后序遍历(非递归)

    这篇随笔开启我的博客进程,成为万千程序员中的一员,坚持走到更远!

    折磨了我一下午的后序遍历中午得到解决,关键在于标记右子树是否被访问过,考虑过修改二叉树结点的数据结构,增加一个visit域,或者建一个栈存储已访问的结点。都比较麻烦没有调试成功。若将右子树也入栈,如果没有访问标记的话,会改变访问的次序,甚至出现死循环,这是比较危险的情况。从借鉴的博文里,摘录并改写为C的代码,基本上没有改动。后续问题努力写出自己的原创代码。

    二叉树存储的数据类型为int型,用数字0表示子树为空

    输入:1 2 3 0 8 0 0 4 0 0 5 6 0 0 7 0 0

    得到后序遍历结果:83426751

     

     

     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 
     4 #define OK              1
     5 #define ERROR           0
     6 #define MaxSize         100 
     7 
     8 typedef int ElemType;
     9 typedef int Status;
    10 
    11 typedef struct BTNode{
    12     ElemType    data; 
    13     struct BTNode *lchild,*rchild; 
    14 }BTree;
    15 
    16 typedef struct St{
    17     struct BTNode*    data[MaxSize];
    18     int               top;
    19 }Stack; 
    20 //1.按先序次序生成二叉树
    21 BTree* CreateT(){
    22     BTree *BT;
    23     ElemType ch;
    24     scanf("%d",&ch);
    25     if(ch==0)
    26         BT=NULL;
    27     else{
    28         BT=(BTree*)malloc(sizeof(BTree));
    29         if(!BT){exit(OVERFLOW);}        
    30         BT->data=ch;
    31         BT->lchild=CreateT();
    32         BT->rchild=CreateT();
    33     }
    34     return BT;
    35 } 
    36 
    37 //4.后序遍历
    38 Status PostOrder(BTree *BT) {
    39     if(BT){
    40         PostOrder(BT->lchild);
    41         PostOrder(BT->rchild);
    42         printf("%3d",BT->data);
    43         return OK;
    44     }
    45     else return ERROR;
    46 }
    47 //4.后序遍历-非递归 
    48 Status PostOrder2(BTree *BT) {
    49     Stack s,s2;
    50     BTree *T;
    51     int flag[MaxSize]; 
    52     s.top=0;
    53     T=BT;
    54     while(s.top!=0||T){
    55         while(T)
    56         {
    57             s.data[s.top++]=T;
    58             flag[s.top-1]=0;
    59             T=T->lchild;
    60          } 
    61          while(s.top!=0&&flag[s.top-1]==1){
    62              T=s.data[--s.top];
    63              printf("%3d",T->data);
    64          }
    65          if(s.top!=0){
    66              flag[s.top-1]=1;
    67              T=s.data[s.top-1];
    68              T=T->rchild;
    69          }
    70          else   break;
    71     }
    72     return OK;
    73 }
    74 int main(){
    75     BTree *BT;
    76     BT=CreateT();
    77     if(PostOrder(BT)){
    78         printf("\n后序遍历完成!\n");
    79     }    
    80     if(PostOrder2(BT)){
    81         printf("\n非递归后序遍历完成!\n");
    82     }
    83 }

     //-------------------------华丽的分割线-------------------------------------

    下面是我自己写的后序遍历程序

     1 //非递归后序遍历-test
     2 void PostOrder3(BTree *T){
     3     BTree *p=T;Stack s;s.top=-1;
     4     int tag[MaxSize];
     5     while(p||s.top!=-1){
     6         
     7         if(p){
     8             s.data[++s.top]=p;
     9             tag[s.top]=0;
    10             p=p->lchild;
    11         }        
    12         else{
    13             while(tag[s.top]==1){
    14             p=s.data[s.top--];
    15             printf("%d",p->data); 
    16             }
    17             p=s.data[s.top];
    18             p=p->rchild;
    19             tag[s.top]=1;
    20         }
    21         if(s.top==-1) break;
    22     }
    23 } 

     

    转载于:https://www.cnblogs.com/geolike/p/4721799.html

    展开全文
  • 题目描述输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。分析所谓二叉搜索树,也称为二叉搜索树、有序二叉树(ordered ...

    题目描述

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

    分析

    所谓二叉搜索树,也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

    若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

    若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

    任意节点的左、右子树也分别为二叉查找树;

    没有键值相等的节点。

    那么对于二叉搜索树的后序遍历的序列来说,最后一个元素即是它的根节点,序列的前某部分元素全部小于最后一个元素,序列的后某部分元素全大于最后一个元素。然后对于这两部分来说,又分别符合这些特点,可以递归的检查下去。

    递归实现

    function VerifySquenceOfBST(s)

    {

    if(s.length === 0)

    return false;

    return judge(s, 0, s.length-1);

    }

    function judge(a, l, r) {

    if(l >= r)

    return true;

    var p1 = r;

    while(p1 > l && a[p1-1] > a[r]) {

    p1--;

    }

    var p2 = p1-1;

    while(p2 >= l){

    if(a[p2] > a[r])

    return false;

    p2--;

    }

    return judge(a, l, p1-1) && judge(a, p1, r-1);

    }

    非递归实现

    对于一个二叉搜索树来说,根节点的左子树每个节点的值肯定小于右子树每个节点的值,所以可以不断的去去掉序列的最后一个值,并且把剩下的部分分成小于最后一个值和大于最后一个值的两部分,只要能分出来那就说明符合二叉搜索树的定义,否则就不符合。

    function VerifySquenceOfBST(s)

    {

    if(s.length === 0)

    return false;

    var start = 0, end = s.length-1;

    while(end !== 0) {

    while(s[start] < s[end]){

    start++;

    }

    while(s[start] > s[end]){

    start++;

    }

    if(start < end)

    return false;

    end--;

    start = 0;

    }

    return true;

    }

    展开全文
  • 二叉树先序遍历的实现思想是:访问根节点;访问当前节点的左子树;若当前节点无左子树,则访问当前节点的右子树;图 1 二叉树以图 1 为例,采用先序遍历的思想遍历该二叉树的过程为:访问该二叉树的根节点,找到 1;...
  • 用堆栈实现二叉树的前序遍历/中序遍历/后序遍历的非递归算法算法思想中序遍历前序遍历后续遍历 算法思想 借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序...
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序或者后序...
  • 二叉树的后序遍历非递归算法 关于 (1)如何利用前序遍历创建二叉树 (2)二叉树的前序、中序、后序递归遍历 (3)二叉树的前序、中序非递归遍历 都已经在之前两篇文章中说过了 利用前序遍历创建二叉树二叉树的...
  • 二叉树的后序遍历(非递归算法)

    千次阅读 2018-09-11 22:20:49
     后序遍历(非递归算法)  ①先序遍历顺序:根节点-左孩子-右孩子  ②后序遍历顺序:左孩子-右孩子-根节点  ③后序遍历倒过来:根节点-右孩子-左孩子  ①和③对比发现,访问顺序只有左孩子和右孩子颠倒了一下  ...
  • 二叉树的非递归前、中、后序遍历算法详解及代码实现(C语言) 1. 前序遍历和中序遍历非递归算法思路 前序和中序非递归遍历的C代码 2. 后序遍历非递归算法思路 后序非递归遍历的C代码 1. 前序遍历和中序遍历...
  • 用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
  • 二叉树的后序遍历非递归算法

    万次阅读 多人点赞 2019-06-03 11:51:45
    1. 对于树遍历我们最常用三种遍历方法分别是前序遍历、中序遍历和后序遍历,使用方法是深度优先遍历树每一个节点,这些遍历方法都是使用递归函数来进行实现,在数据量大情况下是比较低效,原因在于...
  • 设计并实现基于后序线索二叉树后序遍历的非递归算法。 一、二叉树的创建 我们使用二叉链表得方式进行二叉树存数。每个结构有一个数据域,存放结点的数据,还有两个左右指针,以及两个标志。当标志为0时表示指向...
  • - PAGE PAGE 2 欢迎下载 数据结构实验报告 实验题目...一需求分析 该程序用非递归的方法利用先序和中序建立二叉树然后用后序遍历的方法输出二叉树的元素 1输入的形式和输入值的范围 程序运行时输入二叉树的先序和中序序
  • 二叉树后序遍历(非递归)算法实现--C语言

    万次阅读 多人点赞 2018-12-18 16:14:37
      一直说要写二叉树的后序非递归遍历算法,但是前两天各种事情,今天终于有时间好好写一写二叉树的后序遍历算法。   二叉树的后序遍历算法比先序和中序遍历算法要复杂一些。其出栈条件有两种情况: 栈顶元素...
  • 求一颗树的后序遍历的非递归算法 要求:必须是非递归算法,使用堆栈对象来实现 建树方法采用“先序遍历+空树用0表示”的方法 算法流程: 输入 第一行输入一个整数t,表示有t个测试数据 第二行起输入二叉树先序...
  • 昨天写的前序遍历的递归与非递归算法,在非递归算法中主要还是借用到了栈这一工具,其实在中序遍历和后序遍历中依旧可以理由栈的特性来进行非递归的遍历 操作。 1.中序遍历 1.1 中序遍历的递归算法 二叉树的构造以...
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序...
  • 二叉树的先中后序遍历的非递归算法都和栈有关,栈的相关操作请点此查看。①先序遍历思路一:先将根结点进栈,当栈不为空时,出栈并访问,然后依次将右左结点进栈(栈先进后出,所以先进栈右结点)。顺序栈类型:...
  • 二叉树后序遍历的非递归算法(一)中使用的是一个堆栈,且加了一个额外的信息来说明右孩子是否已经访问 下面是使用两个堆栈来实现后序遍历的非递归算法,理解起来比第一个算法要好理解: ////////////////////...
  • 非递归算法中,后序遍历难度大,很多书上只给出思想或者几段无法直接调试代码,甚至有些书上是错,当时我在研究过程中,就是按着书上错误代码绕了好半天,几预抓狂。好在最终摸索出来了,不禁感叹很多出书...
  • void followvisit(struct ...{//后序遍历的非递归算法 struct btree *p,array[20]; int top=0; p=bt; while(top>=0||p->num) { if(p->num) { array[top++]=*p; p=p->lchild; } else { p=&array[--top];
  • 145. 二叉树的后序遍历非递归)1. 题目描述2.代码如下3.细节 1. 题目描述 给定一个二叉树,返回它 后序 遍历。 示例: 输入: [1,null,2,3] 1 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成...
  • 二叉树的先序,中序遍历的非递归遍历方法比较简单,只要借助一个栈就可以很容易实现。但其后序遍历就有些复杂了,这里借鉴下面这篇文章中的后序非递归遍历算法。... 利用两个栈来实现后序遍历,一个栈用于存储遍历结果...
  • 注:本文截图来自文都考研洪...补上先序遍历的非递归算法(C++): /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) ...
  • 二叉树的前序建立递归算法以及前中后序遍历的递归算法已经是人尽皆知了,递归算法也确实为代码的编写带来了很大的方便。然而,有时我们也确实需要它们的非递归算法。将递归算法转化为非递归算法可以帮助我们深入了解...

空空如也

空空如也

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

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